转化为最小割，dinic
1 #include<cstdio> 2 #include<cstring> 3 #include<vector> 4 #include<queue> 5 6 using namespace std; 7 8 const int maxn=20000+5; 9 const int inf=0x3f3f3f3f; 10 const int s=0; 11 int t; 12 13 inline int min(const int x,const int y) 14 { 15 return x<y?x:y; 16 } 17 18 struct Edge 19 { 20 int to,cap,rev; 21 }; 22 vector<Edge>edge[maxn]; 23 int level[maxn]; 24 int iter[maxn]; 25 26 void addedge(int from,int to,int cap) 27 { 28 edge[from].push_back((Edge){to,cap,edge[to].size()}); 29 edge[to].push_back((Edge){from,0,edge[from].size()-1}); 30 } 31 32 void build_graph(int n,int m) 33 { 34 t=n+1; 35 for(int i=0;i<=t;i++) 36 { 37 edge[i].clear(); 38 } 39 int u,v,w; 40 for(int i=1;i<=n;i++) 41 { 42 scanf("%d%d",&u,&v); 43 addedge(i,t,u); 44 addedge(s,i,v); 45 } 46 for(int i=1;i<=m;i++) 47 { 48 scanf("%d%d%d",&u,&v,&w); 49 addedge(u,v,w); 50 addedge(v,u,w); 51 } 52 } 53 54 void bfs() 55 { 56 memset(level,-1,sizeof level); 57 level[s]=1; 58 queue<int>que; 59 while(!que.empty()) 60 que.pop(); 61 que.push(s); 62 while(!que.empty()) 63 { 64 int u=que.front(); 65 que.pop(); 66 for(int i=0;i<edge[u].size();i++) 67 { 68 Edge &e=edge[u][i]; 69 if(e.cap>0&&level[e.to]<0) 70 { 71 level[e.to]=level[u]+1; 72 que.push(e.to); 73 } 74 } 75 } 76 } 77 78 int dfs(int u,int f) 79 { 80 if(u==t) 81 return f; 82 for(int &i=iter[u];i<edge[u].size();i++) 83 { 84 Edge &e=edge[u][i]; 85 if(e.cap>0&&level[e.to]>level[u]) 86 { 87 int d=dfs(e.to,min(f,e.cap)); 88 if(d>0) 89 { 90 e.cap-=d; 91 edge[e.to][e.rev].cap+=d; 92 return d; 93 } 94 } 95 } 96 return 0; 97 } 98 99 int max_flow() 100 { 101 int ret=0; 102 while(1) 103 { 104 bfs(); 105 if(level[t]<0) 106 return ret; 107 memset(iter,0,sizeof iter); 108 int f; 109 while(f=dfs(s,inf)) 110 { 111 ret+=f; 112 } 113 } 114 } 115 116 int main() 117 { 118 int n,m; 119 while(~scanf("%d%d",&n,&m)) 120 { 121 build_graph(n, m); 122 printf("%d ",max_flow()); 123 } 124 return 0; 125 }