题意：给出起点是一个池塘，M条沟渠，给出这M条沟渠的最大流量，再给出终点是一条河流，问从起点通过沟渠最多能够排多少水到河流里面去
看的紫书的最大流，还不是很理解，照着敲了一遍
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include <cmath> 5 #include<stack> 6 #include<vector> 7 #include<map> 8 #include<set> 9 #include<queue> 10 #include<algorithm> 11 using namespace std; 12 13 typedef long long LL; 14 const int INF = (1<<30)-1; 15 const int mod=1000000007; 16 const int maxn=10005; 17 int n,m,M; 18 19 struct Edge{ 20 int from,to,cap,flow; 21 Edge(int u,int v,int c,int f) :from(u),to(v),cap(c),flow(f) {} 22 }; 23 24 25 vector<Edge> edges;//存边 26 vector<int> G[maxn];//邻接表 27 int a[maxn];//到起点i的可改进量 28 int p[maxn];//最短 路树上p的入弧编号 29 30 void init(){ 31 for(int i=0;i<n;i++) G[i].clear(); 32 edges.clear(); 33 } 34 35 void addedges(int from,int to,int cap){ 36 edges.push_back(Edge(from,to,cap,0)); 37 edges.push_back(Edge(to,from,0,0));//反向弧 38 m=edges.size(); 39 G[from].push_back(m-2); 40 G[to].push_back(m-1); 41 } 42 43 int Maxflow(int s,int t){ 44 int flow=0; 45 for(;;){ 46 memset(a,0,sizeof(a)); 47 queue<int> q; 48 q.push(s); 49 a[s]=INF; 50 while(!q.empty()){ 51 int x=q.front();q.pop(); 52 for(int i = 0;i < G[x].size(); i++){ 53 Edge& e = edges[G[x][i]]; 54 if(!a[e.to]&&e.cap>e.flow){ 55 p[e.to] = G[x][i]; 56 a[e.to] = min(a[x], e.cap-e.flow); 57 q.push(e.to); 58 } 59 } 60 if(a[t]) break; 61 } 62 if(!a[t]) break; 63 for(int u = t;u !=s ;u=edges[p[u]].from){ 64 edges[p[u]].flow+=a[t]; 65 edges[p[u]^1].flow-=a[t]; 66 } 67 flow+=a[t]; 68 } 69 return flow; 70 } 71 72 int main(){ 73 while(scanf("%d %d",&M,&n)!=EOF){ 74 init(); 75 for(int i=0;i<M;i++){ 76 int u,v,c; 77 scanf("%d %d %d",&u,&v,&c); 78 u--;v--; 79 addedges(u,v,c); 80 } 81 printf("%d ",Maxflow(0,n-1)); 82 } 83 return 0; 84 }
寒假的cf就遇到过最大流的题目，当时不会而且还没有学
现在又遇到了，不能再这样了，先学一点点先吧-----------------------
gooooooooooooooo------------
加油====================