.4.8 1532 Drainage Ditches

题意：水从水池流向汇集地，每个管子有限制，求到汇集地的最大量

最大流模板

#include <bits/stdc++.h>using namespace std;#define inf 0x3f3f3f3fint head[210],tot = 0;struct Node{int to,next,w;}edge[200000];int s,t;void add(int x,int y,int z){edge[tot].next = head[x];edge[tot].to = y;edge[tot].w = z;head[x] = tot++;edge[tot].next = head[y];edge[tot].to = x;edge[tot].w = 0;head[y] = tot++;}int dis[210];int n,m,ans = 0;bool bfs(){memset(dis,-1,sizeof(dis));queue<int> q;q.push(s);dis[s] = 0;while(!q.empty()){int u = q.front();q.pop();for(int i = head[u];~i;i = edge[i].next){int v = edge[i].to;if(dis[v]==-1&&edge[i].w>0){dis[v] = dis[u]+1 ;q.push(v);}}}return dis[m]>0;}int dfs(int u,int exp){if(u==t)return exp;int flow = 0,tmp = 0;for(int i = head[u];~i;i = edge[i].next){int v = edge[i].to;if(dis[v]==(dis[u]+1)&&edge[i].w>0){tmp = dfs(v,min(exp,edge[i].w));if(tmp>0){edge[i].w -= tmp;edge[i^1].w += tmp;return tmp;}}}// dis[u] = -1;return 0;}int main(){while(~scanf("%d%d",&n,&m)){memset(head,-1,sizeof(head));ans = 0;tot = 0;for(int i = 0;i<n;i++){int x,y,z;scanf("%d%d%d",&x,&y,&z);add(x,y,z);// add(y,x,0);}s = 1;t = m;int f;while(bfs())while(f=dfs(1,inf))ans+=f;printf("%d\n",ans);}}