网络流模板

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstdlib>
 4 #include<cstring>
 5 #include<algorithm>
 6 #include<cmath>
 7 #include<queue>
 8 #define maxn 10002
 9 #define maxm 100002
10 #define inf 1e9
11 using namespace std;
12 int n,m,cur[maxn],tot=1,head[maxn];
13 int S,T,ans,d[maxn];
14 struct node
15 {
16     int cap,nex,v;
17 }e[maxm*2];
18 void lj(int t1,int t2,int t3){
19     e[++tot].v=t2;e[tot].cap=t3;e[tot].nex=head[t1];head[t1]=tot;
20 }
21 bool BFS()
22 {
23     queue<int>q;
24     for(int i=1;i<=n;i++)d[i]=inf;
25     q.push(S);d[S]=0;
26     while(!q.empty())
27     {
28         int x=q.front();q.pop();cur[x]=head[x];
29         for(int i=head[x];i;i=e[i].nex){
30             if(d[e[i].v]>d[x]+1&&e[i].cap>0){
31                 d[e[i].v]=d[x]+1;
32                 q.push(e[i].v);
33             }
34         }
35     }
36     return d[T]!=inf; 
37 }
38 int lian(int k,int a)
39 {
40     if(k==T||!a)return a;
41     int f,flow=0;
42     for(int &i=cur[k];i;i=e[i].nex){
43         if(d[e[i].v]==d[k]+1&&(f=lian(e[i].v,min(a,e[i].cap)))>0)
44         {
45             e[i].cap-=f;e[i^1].cap+=f;
46             a-=f;flow+=f;
47         }
48         if(!a)break;
49     }
50     return flow;
51 }
52 int main(){
53     cin>>n>>m>>S>>T;
54     for(int i=1,t1,t2,t3;i<=m;i++){
55         scanf("%d%d%d",&t1,&t2,&t3);
56         lj(t1,t2,t3);lj(t2,t1,0);
57     }
58     while(BFS())ans+=lian(S,inf);
59     printf("%d\n",ans);
60     return 0;
61 }

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstdlib>
 4 #include<cstring>
 5 #include<algorithm>
 6 #include<cmath>
 7 #include<queue>
 8 #define maxn 5005
 9 #define inf 1e9
10 using namespace std;
11 int flag[maxn],d[maxn],head[maxn],cur[maxn],tot=1;
12 int n,m,S,T,ans; 
13 struct node{
14     int v,nex,cap,w;
15 }e[maxn*20];
16 void add(int t1,int t2,int t3,int t4){
17     e[++tot].v=t2;e[tot].cap=t3;e[tot].w=t4;e[tot].nex=head[t1];head[t1]=tot;
18 }
19 bool spfa(){
20     for(int i=1;i<=n;i++)d[i]=inf,flag[i]=0;
21     queue<int>q;q.push(S);d[S]=0;flag[S]=1;
22     while(!q.empty()){
23         int k=q.front();q.pop();
24         for(int i=head[k];i;i=e[i].nex){
25             if(e[i].cap&&d[e[i].v]>d[k]+e[i].w){
26                 d[e[i].v]=d[k]+e[i].w;
27                 if(!flag[e[i].v]){
28                     flag[e[i].v]=1;q.push(e[i].v);
29                 }
30             }
31         }
32         flag[k]=0;
33     }
34     return d[T]!=inf;
35 }
36 int lian(int k,int a){
37     flag[k]=1;
38     if(k==T||!a)return a;
39     int flow=0;
40     for(int &i=cur[k];i;i=e[i].nex){
41         if(d[e[i].v]==d[k]+e[i].w&&e[i].cap&&!flag[e[i].v]){
42             int f=lian(e[i].v,min(e[i].cap,a));
43             e[i].cap-=f;e[i^1].cap+=f;    
44             flow+=f;a-=f;
45             ans+=f*e[i].w;
46         }if(!a)break;
47     }
48     return flow;
49 }
50 int main(){
51     cin>>n>>m>>S>>T;
52     for(int i=1,t1,t2,t3,t4;i<=m;i++){
53         scanf("%d%d%d%d",&t1,&t2,&t3,&t4);
54         add(t1,t2,t3,t4);add(t2,t1,0,-t4);
55     }
56     int F=0;
57     while(spfa()){
58         flag[T]=1;
59         while(flag[T]){
60             for(int i=1;i<=n;i++)flag[i]=0,cur[i]=head[i];
61             F+=lian(S,inf);
62         }
63     }
64     cout<<F<<‘ ‘<<ans<<endl;
65     return 0;
66 }