[题目链接]
http://poj.org/problem?id=1273
[算法]
最大流
[代码]
#include <algorithm> #include <bitset> #include <cctype> #include <cerrno> #include <clocale> #include <cmath> #include <complex> #include <cstdio> #include <cstdlib> #include <cstring> #include <ctime> #include <deque> #include <exception> #include <fstream> #include <functional> #include <limits> #include <list> #include <map> #include <iomanip> #include <ios> #include <iosfwd> #include <iostream> #include <istream> #include <ostream> #include <queue> #include <set> #include <sstream> #include <stdexcept> #include <streambuf> #include <string> #include <utility> #include <vector> #include <cwchar> #include <cwctype> #include <stack> #include <limits.h> using namespace std; #define MAXN 210 const int inf = 2e9; struct edge { int to,w,nxt; } e[MAXN << 1]; int i,tot,n,m,u,v,w,maxflow,flow; int head[MAXN],depth[MAXN]; inline void addedge(int u,int v,int w) { tot++; e[tot] = (edge){v,w,head[u]}; head[u] = tot; tot++; e[tot] = (edge){u,0,head[v]}; head[v] = tot; } inline bool bfs() { int i,l,r,u,v,w; static int q[MAXN]; q[l = r = 1] = 1; memset(depth,0,sizeof(depth)); depth[1] = 1; while (l <= r) { u = q[l]; l++; for (i = head[u]; i; i = e[i].nxt) { v = e[i].to; w = e[i].w; if (w && !depth[v]) { depth[v] = depth[u] + 1; if (v == n) return true; q[++r] = v; } } } return false; } inline int dinic(int u,int flow) { int i,v,w,rest = flow,k; if (u == n) return flow; for (i = head[u]; i && rest; i = e[i].nxt) { v = e[i].to; w = e[i].w; if (w && depth[v] == depth[u] + 1) { k = dinic(v,min(rest,w)); if (!k) depth[v] = 0; e[i].w -= k; e[i ^ 1].w += k; rest -= k; } } return flow - rest; } int main() { while (scanf("%d%d",&m,&n) != EOF) { tot = 1; memset(head,0,sizeof(head)); for (i = 1; i <= m; i++) { scanf("%d%d%d",&u,&v,&w); addedge(u,v,w); } maxflow = 0; while (bfs()) { while (flow = dinic(1,inf)) maxflow += flow; } printf("%d ",maxflow); } return 0; }