最大流

 1 #include<stdio.h>
 2 #include<algorithm>
 3 #include<string.h>
 4 #include<queue>
 5 using namespace std;
 6 #define maxm 450000
 7 #define maxn 20005
 8 #define inf 0x3f3f3f3f
 9 queue<int>Q;
10 int cnt,v[maxm<<1],Next[maxm<<1],w[maxm<<1],first[maxn],cur[maxn];
11 int SSS,TTT,dep[maxn];
12 void add(int st,int end,int val){
13     v[cnt]=end;w[cnt]=val;Next[cnt]=first[st];first[st]=cnt++;
14     v[cnt]=st;w[cnt]=0;Next[cnt]=first[end];first[end]=cnt++;
15 }
16 bool bfs(){
17     memset(dep,0,sizeof(dep));
18     dep[SSS]=1;
19     Q.push(SSS);
20     while(!Q.empty()){
21         int x=Q.front();Q.pop();
22         for(int e=first[x];e!=-1;e=Next[e]){
23             if(!dep[v[e]]&&w[e]>0){
24                 dep[v[e]]=dep[x]+1;
25                 Q.push(v[e]);
26             }
27         }
28     }
29     return dep[TTT];
30 }
31 int dfs(int x,int lim){
32     if(x==TTT)return lim;
33     int lim1=lim;
34     for(int e=cur[x];e!=-1;e=Next[e]){
35         if(dep[v[e]]==dep[x]+1&&w[e]>0){
36             int flow=dfs(v[e],min(w[e],lim));
37             cur[x]=e;    
38             w[e]-=flow;w[e^1]+=flow;
39             if((lim-=flow)<=0)break;
40         }
41     }
42     if(lim==lim1)dep[x]=0;
43     return lim1-lim;
44 }
45 int main(){
46     int n,m,a,b,c;
47     scanf("%d%d",&n,&m);
48     SSS=n+1;TTT=n+2;
49     memset(first,-1,sizeof(first));
50     for(int i=1;i<=n;i++){
51         scanf("%d%d",&a,&b);
52         add(SSS,i,a);add(i,TTT,b);
53     }
54     for(int i=1;i<=m;i++){
55         scanf("%d%d%d",&a,&b,&c);
56         add(a,b,c);add(b,a,c);
57     }
58     int ans=0;
59     while(bfs()){
60         memcpy(cur,first,sizeof(first));    
61         ans+=dfs(SSS,inf);
62     }
63     printf("%d\n",ans);
64     return 0;
65 }