听说这是JSOIDay4
膜了贵省的题目，感到不明觉厉。
T1
咦这是什么题目？
5min过去了。。。听说NiroBC已经AK弃疗了。。。
Orz好像70分是送的。。
那么想一想正解吧。
考虑一条u->v的边，那么这条边被删掉的条件是：存在另一条路径使得u能到v。
那么分块，如果u的出度小于，就枚举u的出边，否则枚举v的入边。
那么问题就转化为判断两点的连通性。
那么只要拓扑+压位就可以辣！
T2
咦这是什么题目？
好吧先yy个20分暴力。
接着Gold_7将此题AC，感到不明觉厉。
正解是：
将正权连源，负权连汇，按照墙的权值建图，跑最小割。
ans=权值绝对值之和-最小割。
正确性在于：假如存在一条源到汇的路径，那么显然：
1、不取正权的点。
2、不取负权的点。
3、用墙将它们隔开。
那么只要把这条路径隔断就可以了。
T3
咦这是什么题目？
好吧先yy个20分暴力。
结果写萎了。。
蛋疼的满分算法如下：
显然最大值的长度len为
那么可以对所有点向后扩展len位，排序，显然答案必定是这些数其中一个。
那么二分，每个点能扩展len位就扩展，否则扩展len-1位。
接着只要判断一下有没有一种扩展方式在扩展了k次的限制下超过了n位就可以辣！
【Codes】
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 | #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);} |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 | #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)
