题目传送门：【BZOJ 1273】
题目大意：Farmer John 担心他的三叶草被雨淋坏了，于是他修建了许多的排水沟将雨引到附近的一条小溪中。作为一名优秀的工程师，他有办法控制通过排水沟的水量。他不仅知道排水沟每分钟能运走多少水，还清楚它的详细结构。这些排水沟连接着一旁的池塘和小溪。现在，他想问你，这个排水沟将水从池塘引向小溪所允许的最大流量是多少。
输入多组数据，每组数据的第一行包含两个整数 N 和 M，分别代表排水沟的边数和节点数量。1 号节点是池塘，m 号节点是小溪。接下来 N 行，每行三个整数 Si，Ei，Ci，表示水沟从 Si 流向 Ei，以及这条水沟所允许的最大流量 Ci。输出则为从池塘流向小溪的流量的最大值。
题目分析：
一道最大流的模板题。
题目的暗示性已经非常清楚了。将 1 号节点设为源点 S，m 号节点设为汇点 T，Ci 作为每条边的容量。然后直接套最大流的算法即可(Edmonds-Karp，Dinic，ISAP 等)。
下面附上 Dinic 的代码：
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<queue> using namespace std; const int MX=20005; const int INF=0x3f3f3f3f; struct Edge{ int to,cap,next; }; Edge edge[2 * MX]; int n,m,head[MX],now = 1,dis[MX]; void adde(int u,int v,int c){ edge[++now].to = v; edge[now].cap = c; edge[now].next = head[u]; head[u] = now; } bool bfs(int s){ queue<int> q; bool vis[MX] = {0}; q.push(s); dis[s] = 0; vis[s] = true; 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 (!vis[v] && edge[i].cap){ dis[v] = dis[u]+1; vis[v] = true; q.push(v); } } } if (vis[m]) return true; return false; } int dfs(int u,int delta){ if (u == m) return delta; int sum=0; for (int i = head[u];i && delta;i = edge[i].next){ int v = edge[i].to; if (edge[i].cap && dis[v] == dis[u] + 1){ int d = dfs(v, min(edge[i].cap,delta) ); edge[i].cap -= d; edge[i ^ 1].cap += d; delta -= d; sum += d; } } return sum; } int getFlow(){ int ans = 0; while (bfs(1)){ ans += dfs(1,INF); memset(dis,0x3f,sizeof(dis)); } return ans; } int main(){ int Si,Ei,Ci; while (scanf("%d%d",&n,&m) != EOF){ memset(head,0,sizeof(head)); memset(edge,0,sizeof(edge)); memset(dis,0x3f,sizeof(dis)); for (int i = 1;i <= n;i++){ scanf("%d%d%d",&Si,&Ei,&Ci); adde(Si,Ei,Ci); adde(Ei,Si,0); } printf("%d\n",getFlow()); } return 0; }