题目链接： http://poj.org/problem?id=1273
题目大意：
N个点，M条边(0<=N<=200,2<=M<=200)的有向图，源点为1,汇点为N，求最大流;
分析：
……注意考虑重边，边权（容量）要进行累加;
代码：
poj1273
1 /*1273 Accepted 340K 0MS C++ 1582B 2012-04-22 21:16:57*/ 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <iostream> 6 #include <algorithm> 7 #include <vector> 8 using namespace std; 9 10 #define mpair make_pair 11 #define pii pair<int,int> 12 #define MM(a,b) memset(a,b,sizeof(a)); 13 typedef long long lld; 14 typedef unsigned long long u64; 15 template<class T> bool up_max(T& a,const T& b){return b>a? a=b,1 : 0;} 16 template<class T> bool up_min(T& a,const T& b){return b<a? a=b,1 : 0;} 17 #define maxn 210 18 #define inf 2100000000 19 20 int n,m,S,T; 21 int g[maxn][maxn]; 22 23 bool vis[maxn]; 24 int que[maxn]; 25 int pre[maxn]; 26 bool bfs(){ 27 int head=0, tail=0; 28 MM( vis, 0 ); 29 que[tail++]= 1; 30 vis[1]= 1; 31 while(head<tail){ 32 int u= que[head++]; 33 for(int i=1;i<=m;++i){ 34 if( g[u][i] && !vis[i] ){ 35 vis[i]= 1; 36 pre[i]= u; 37 if( i==T ) return 1; 38 que[tail++]= i; 39 } 40 } 41 } 42 return 0; 43 } 44 45 int Edmonds_karp(){ 46 int i, ans= 0; 47 while( bfs() ){ 48 int t= inf; 49 for(int i=T; i!=S; i= pre[i]) 50 up_min( t, g[pre[i]][i] ); 51 ans+= t; 52 for(int i=T; i!=S; i= pre[i]) 53 g[pre[i]][i]-= t, g[i][pre[i]]+= t; 54 } 55 return ans; 56 } 57 58 int main() 59 { 60 while( scanf("%d%d", &n, &m) !=EOF ){ 61 MM( g, 0 ); 62 S= 1, T= m; 63 for(int i=0;i<n;++i){ 64 int u,v,w; 65 scanf("%d%d%d", &u, &v, &w); 66 g[u][v]+= w; 67 } 68 printf("%d\n", Edmonds_karp() ); 69 } 70 }