题目链接：
题目大意：
给出有向图以及边的最大容量，求从1到n的最大流
思路：
传送门：
直接套用模板，用水流来理解网络流
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 using namespace std; 8 const int maxn = 1000; 9 const int INF = 1e9 + 7;10 struct edge11 {12 int from, to, cap, flow;//分别是起点，终点，容量，流量13 edge(int u, int v, int c, int f):from(u), to(v), cap(c), flow(f){}14 };15 int n, m;//n为点数，m为边数16 vector e;//保存所有边的信息17 vector G[maxn];//邻接表，G[i][j]保存节点i的第j条边在e数组里面的编号18 int a[maxn];//每个点目前流经的水量19 int p[maxn];//p[i]从原点s到终点t的节点i的前一条边的编号20 21 void init(int n)22 {23 for(int i = 0; i <= n; i++)G[i].clear();24 e.clear();25 }26 void addedge(int u, int v, int c)27 {28 e.push_back(edge(u, v, c, 0));//正向边29 e.push_back(edge(v, u, 0, 0));//反向边，容量为030 m = e.size();31 G[u].push_back(m - 2);32 G[v].push_back(m - 1);33 }34 int Maxflow(int s, int t)//起点为s，终点为t35 {36 int flow = 0;37 for(;;)38 {39 memset(a, 0, sizeof(a));//从原点s开始放水，最初每个点的水量都为040 queue Q;//BFS拓展队列41 Q.push(s);42 a[s] = INF;//原点的水设置成INF43 while(!Q.empty())44 {45 int x = Q.front();//取出目前水流到的节点46 Q.pop();47 for(int i = 0; i < G[x].size(); i++)//所有邻接节点48 {49 edge& now = e[G[x][i]];50 if(!a[now.to] && now.cap > now.flow)51 //a[i]为0表示i点还未流到52 //now.cap > now.flow 说明这条路还没流满53 //同时满足这两个条件，水流可以流过这条路54 {55 p[now.to] = G[x][i];//反向记录路径56 a[now.to] = min(a[x], now.cap - now.flow);57 //流到下一点的水量为上一点的水量或者路径上还可以流的最大流量，这两者取最小值58 Q.push(now.to);//将下一个节点入队列59 }60 }61 if(a[t])break;//如果已经流到了终点t，退出本次找增广路62 }63 if(!a[t])break;//如果所有路都已经试过，水不能流到终点，说明已经没有增广路，已经是最大流64 for(int u = t; u != s; u = e[p[u]].from)//反向记录路径65 {66 e[p[u]].flow += a[t];//路径上所有正向边的流量增加流到终点的流量67 e[p[u]^1].flow -= a[t];//路径上所有反向边的流量减少流到终点的流量68 }69 flow += a[t];//最大流加上本次流到终点的流量70 }71 return flow;72 }73 int main()74 {75 int M, N;76 while(cin >> M >> N)77 {78 n = N;79 int u, v, c;80 init(n);81 for(int i = 0; i < M; i++)82 {83 scanf("%d%d%d", &u, &v, &c);84 addedge(u, v, c);85 }86 cout<