P2740 [USACO4.2]草地排水Drainage Ditches
最大流模板
1 #include<cstdio> 2 #include<algorithm> 3 using namespace std; 4 #define maxn 10000 5 #define inf 100000000 6 int n,m,src,dec,cur[maxn],ans,lev[maxn],front[maxn],head,tail,que[maxn],tot; 7 8 struct node{ 9 int to,next,cap; 10 }e[maxn]; 11 inline void add(int u,int v,int w) 12 { 13 e[++tot].to=v; e[tot].next=front[u]; e[tot].cap=w; front[u]=tot; 14 e[++tot].to=u; e[tot].next=front[v]; e[tot].cap=0; front[v]=tot; 15 } 16 17 inline bool bfs() 18 { 19 for(int i=src;i<=dec;i++) lev[i]=-1,cur[i]=front[i]; 20 head=tail=0; 21 que[tail++]=src; lev[src]=0; 22 while(head<tail) 23 { 24 for(int i=front[que[head]];i;i=e[i].next) 25 if(e[i].cap>0&&lev[e[i].to]==-1) 26 { 27 lev[e[i].to]=lev[que[head]]+1; 28 que[tail++]=e[i].to; 29 if(e[i].to==dec) return true; 30 } 31 head++; 32 } 33 return false; 34 } 35 inline int dinic(int u,int flow) 36 { 37 if(u==dec) return flow; 38 int res=0,delta; 39 for(int i=cur[u];i;i=e[i].next) 40 { 41 if(e[i].cap>0&&lev[e[i].to]>lev[u]) 42 { 43 delta=dinic(e[i].to,min(e[i].cap,flow-res)); 44 if(delta) 45 { 46 e[i].cap-=delta; e[i^1].cap+=delta; 47 res+=delta; if(res==flow) break; 48 } 49 } 50 } 51 if(res!=flow) lev[u]=-1; 52 return res; 53 } 54 55 int main() 56 { 57 scanf("%d%d",&n,&m); 58 for(int i=1;i<=n;i++) 59 { 60 int u,v,w; 61 scanf("%d%d%d",&u,&v,&w); 62 add(u,v,w); 63 } 64 src=1; dec=m; 65 while(bfs()) 66 ans+=dinic(src,inf); 67 printf("%d ",ans); 68 return 0; 69 }