听说这是JSOIDay4
膜了贵省的题目，感到不明觉厉。
T1
咦这是什么题目？
5min过去了。。。听说NiroBC已经AK弃疗了。。。
Orz好像70分是送的。。
那么想一想正解吧。
考虑一条u->v的边，那么这条边被删掉的条件是：存在另一条路径使得u能到v。
那么分块，如果u的出度小于[tex]\sqrt n[/tex]，就枚举u的出边，否则枚举v的入边。
那么问题就转化为判断两点的连通性。
那么只要拓扑+压位就可以辣！
T2
咦这是什么题目？
好吧先yy个20分暴力。
接着Gold_7将此题AC，感到不明觉厉。
正解是：
将正权连源，负权连汇，按照墙的权值建图，跑最小割。
ans=权值绝对值之和-最小割。
正确性在于：假如存在一条源到汇的路径，那么显然：
1、不取正权的点。
2、不取负权的点。
3、用墙将它们隔开。
那么只要把这条路径隔断就可以了。
T3
咦这是什么题目？
好吧先yy个20分暴力。
结果写萎了。。
蛋疼的满分算法如下：
显然最大值的长度len为[tex]\left[ {\frac{{n - 1}}{k}} \right] + 1[/tex]
那么可以对所有点向后扩展len位，排序，显然答案必定是这些数其中一个。
那么二分，每个点能扩展len位就扩展，否则扩展len-1位。
接着只要判断一下有没有一种扩展方式在扩展了k次的限制下超过了n位就可以辣！
【Codes】
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
typedef long long ll;
using namespace std;
const int M=200010;
const int N=30010;
int n,m,i,l,r,edgenum,edgenum1,ans;
int head[M],vet[M],next[M],price[M],head1[M],vet1[M],next1[M],x[M],y[M],h[M];
ll f[N][1010];
void addedge(int x,int y){
vet[++edgenum]=y;
next[edgenum]=head[x];
head[x]=edgenum;
price[y]++;
}
void addedge1(int x,int y){
vet1[++edgenum1]=y;
next1[edgenum1]=head1[x];
head1[x]=edgenum1;
price[y]++;
}
int main(){
scanf("%d%d",&n,&m);
for (i=1;i<=m;i++)scanf("%d%d",&x[i],&y[i]),addedge(y[i],x[i]);
for (i=1;i<=n;i++){
if (!price[i])h[++r]=i;
f[i][i/30]=(1<<(i%30));
}
l=1;
while (l<=r){
int u=h[l];
for (int e=head[u];e;e=next[e]){
int v=vet[e];
for (i=0;i<=n/30;i++)f[v][i]|=f[u][i];
price[v]--;
if (!price[v])h[++r]=v;
}
l++;
}
for (i=1;i<=m;i++)addedge1(x[i],y[i]);
for (i=1;i<=m;i++)
if (price[x[i]]<=sqrt(n)){
for (int e=head1[x[i]];e;e=next1[e]){
int v=vet1[e];
if (v==y[i])continue;
if (f[v][y[i]/30]&(1<<(y[i]%30))){ans++;break;}
}
}else{
for (int e=head[y[i]];e;e=next[e]){
int v=vet[e];
if (v==x[i])continue;
if (f[x[i]][v/30]&(1<<(v%30))){ans++;break;}
}
}
printf("%d\n",ans);
}
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int M=400010;
int n,m,i,j,edgenum,source,sink,cnt,ans,x;
int head[M],vet[M],next[M],size[M],h[M],q[M];
int point[210][210];
void addedge(int x,int y,int ch){
vet[++edgenum]=y;
next[edgenum]=head[x];
head[x]=edgenum;
size[edgenum]=ch;
vet[++edgenum]=x;
next[edgenum]=head[y];
head[y]=edgenum;
}
int bfs(){
for (int i=1;i<=M;i++)h[i]=-1;
int l=1,r=1;
q[1]=source,h[source]=0;
while (l<=r){
int u=q[l];
for (int e=head[u];e;e=next[e])
if (size[e]>0&&h[vet[e]]<0){
int v=vet[e];
h[v]=h[u]+1;
q[++r]=v;
}
l++;
}
if (h[sink]<0)return 0;else return 1;
}
int dfs(int u,int aug){
if (u==sink)return aug;
int flow=0;
for (int e=head[u];e;e=next[e])
if (size[e]>0&&h[vet[e]]==h[u]+1){
int v=vet[e];
int tmp=dfs(v,min(aug-flow,size[e]));
size[e]-=tmp;
size[e^1]+=tmp;
flow+=tmp;
if (flow==aug)return flow;
}
if (!flow)h[u]=-1;
return flow;
}
int main(){
scanf("%d%d",&n,&m);
source=1,sink=n*m+2,cnt=1,edgenum=1;
for (i=1;i<=n;i++)
for (j=1;j<=m;j++){
scanf("%d",&x);
point[i][j]=++cnt;
if (x>0)addedge(source,point[i][j],x),ans+=x;else if (x<0)addedge(point[i][j],sink,-x),ans-=x;
}
for (i=1;i<n;i++)
for (j=1;j<=m;j++){
scanf("%d",&x);
addedge(point[i][j],point[i+1][j],x);
addedge(point[i+1][j],point[i][j],x);
}
for (i=1;i<=n;i++)
for (j=1;j<m;j++){
scanf("%d",&x);
addedge(point[i][j],point[i][j+1],x);
addedge(point[i][j+1],point[i][j],x);
}
while (bfs())ans-=dfs(source,1000000007);
printf("%d\n",ans);
}
评论 (0)
