「CODEVS1993」草地排水
题目描述 Description
在农夫约翰的农场上，每逢下雨，Bessie最喜欢的三叶草地就积聚了一潭水。这意味着草地被水淹没了，并且小草要继续生长还要花相当长一段时间。因此，农夫约翰修建了一套排水系统来使贝茜的草地免除被大水淹没的烦恼（不用担心，雨水会流向附近的一条小溪）。作为一名一流的技师，农夫约翰已经在每条排水沟的一端安上了控制器，这样他可以控制流入排水沟的水流量。
农夫约翰知道每一条排水沟每分钟可以流过的水量，和排水系统的准确布局（起点为水潭而终点为小溪的一张网）。需要注意的是，有些时候从一处到另一处不只有一条排水沟。
根据这些信息，计算从水潭排水到小溪的最大流量。对于给出的每条排水沟，雨水只能沿着一个方向流动，注意可能会出现雨水环形流动的情形。
输入描述 Input Description
第1行: 两个用空格分开的整数N (0 <= N <= 200) 和 M (2 <= M <= 200)。N是农夫John已经挖好的排水沟的数量，M是排水沟交叉点的数量。交点1是水潭，交点M是小溪。
第二行到第N+1行: 每行有三个整数，Si, Ei, 和 Ci。Si 和 Ei (1 <= Si, Ei <= M) 指明排水沟两端的交点，雨水从Si 流向Ei。Ci (0 <= Ci <= 10,000,000)是这条排水沟的最大容量。
输出描述 Output Description
输出一个整数，即排水的最大流量。
样例输入 Sample Input
样例输出 Sample Output
50
代码
抄抄代码画画图就懂了
|
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 |
#include<iostream> using namespace std; int cap[201][201],flow[201][201]; int res[201],father[201]; int u,v,f; int m,n; int ek(int x,int y) { int q[201]; while(1) { int t=0,w=1; memset(res,0,sizeof(res)); res[x]=0x7fffffff; q[t]=x; while(t<w) { u=q[t];t++; for(v=1;v<=n;v++) { if(res[v]==0&&cap[u][v]>flow[u][v]) { father[v]=u; q[w++]=v; res[v]=min(res[u],cap[u][v]-flow[u][v]); } } } if(res[y]==0)return f; for(u=y;u!=x;u=father[u]) { flow[father[u]][u]+=res[y]; flow[u][father[u]]-=res[y]; } f+=res[y]; } } int main() { scanf("%d%d",&m,&n); while(m--) { int x,y,z; scanf("%d%d%d",&x,&y,&z); cap[x][y]+=z; } printf("%d",ek(1,n)); return 0; } |
打了个边表的
|
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 |
#include<iostream> #include<cstdio> #include<cstring> #define inf 0x7fffffff using namespace std; int n,m,ans,cnt=1; int head[501],q[501],h[501]; struct data{int to,next,v;}e[501]; void ins(int u,int v,int w) { cnt++;e[cnt].to=v;e[cnt].next=head[u]; head[u]=cnt;e[cnt].v=w; } void insert(int u,int v,int w) {ins(u,v,w);ins(v,u,0);} bool bfs() { memset(h,-1,sizeof(h)); int t=0,w=1,now; q[t]=1;h[1]=0; while(t!=w) { now=q[t];t++;if(t==501)t=0; for(int i=head[now];i;i=e[i].next) { if(e[i].v&&h[e[i].to]==-1) { h[e[i].to]=h[now]+1; q[w++]=e[i].to;if(w==501)w=0; } } } if(h[x]==-1)return 0; return 1; } int dfs(int x,int f) { if(x==n)return f; int w,used=0; for(int i=head[x];i;i=e[i].next) { if(e[i].v&&h[e[i].to]==h[x]+1) { w=dfs(e[i].to,min(f-used,e[i].v)); used+=w;e[i].v-=w;e[i^1].v+=w; if(used==f)return f; } } if(!used)h[n]==-1; return used; } void dinic(){while(bfs())ans+=dfs(1,inf);} int main() { scanf("%d%d",&m,&n); for(int i=1;i<=m;i++) { int u,v,w; scanf("%d%d%d",&u,&v,&w); insert(u,v,w); } dinic(); printf("%d",ans); return 0; } |
计数器 9786213
OI 课件=>
OI 课件=>
请问：if(!used)h
==-1;在第二份代码49行的里边儿没有作用吧
写错了
第二个的49行应该是
h[x] = -1;吧？