1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #define M 100000 5 #define inf 2139062143 6 using namespace std; 7 struct data 8 { 9 int l,r,w; 10 }a[M]; 11 int q[M],d[M],head[M],next[10*M],u[10*M],v[10*M],cnt=1,n,m,K,ans; 12 int cnt1=1,head1[M],next1[10*M],fro[10*M],u1[10*M],v1[10*M],w1[10*M],f[M],fr[M]; 13 void jia(int a1,int a2,int a3) 14 { 15 cnt++; 16 u[cnt]=a2; 17 v[cnt]=a3; 18 next[cnt]=head[a1]; 19 head[a1]=cnt; 20 } 21 void jia1(int a1,int a2,int a3,int a4) 22 { 23 cnt1++; 24 fro[cnt1]=a1; 25 u1[cnt1]=a2; 26 v1[cnt1]=a3; 27 w1[cnt1]=a4; 28 next1[cnt1]=head1[a1]; 29 head1[a1]=cnt1; 30 } 31 bool bfs() 32 { 33 memset(d,0,sizeof(int)*(2*n)); 34 int h=0,t=1; 35 q[1]=1; 36 d[1]=1; 37 for(;h<t;) 38 { 39 h++; 40 int p=q[h]; 41 for(int i=head[p];i;i=next[i]) 42 if(!d[u[i]]&&v[i]) 43 { 44 d[u[i]]=d[p]+1; 45 if(d[n]) 46 return 1; 47 t++; 48 q[t]=u[i]; 49 } 50 } 51 return 0; 52 } 53 int dinic(int s,int f) 54 { 55 if(s==n) 56 return f; 57 int rest=f; 58 for(int i=head[s];i&&rest;i=next[i]) 59 if(v[i]&&d[u[i]]==d[s]+1) 60 { 61 int now=dinic(u[i],min(rest,v[i])); 62 if(!now) 63 d[u[i]]=0; 64 v[i]-=now; 65 v[i^1]+=now; 66 rest-=now; 67 } 68 return f-rest; 69 } 70 bool spfa() 71 { 72 memset(d,127,sizeof(int)*(2*n)); 73 d[0]=0; 74 f[0]=1; 75 q[1]=0; 76 int h=0,t=1; 77 for(;h<t;) 78 { 79 h++; 80 int p=q[h]; 81 f[p]=0; 82 for(int i=head1[p];i;i=next1[i]) 83 if(v1[i]&&d[u1[i]]>d[p]+w1[i]) 84 { 85 d[u1[i]]=d[p]+w1[i]; 86 fr[u1[i]]=i; 87 if(!f[u1[i]]) 88 { 89 f[u1[i]]=1; 90 t++; 91 q[t]=u1[i]; 92 } 93 } 94 } 95 if(d[n]!=inf) 96 return 1; 97 return 0; 98 } 99 void mcf() 100 { 101 int mx=inf; 102 for(int i=fr[n];i;i=fr[fro[i]]) 103 mx=min(mx,v1[i]); 104 for(int i=fr[n];i;i=fr[fro[i]]) 105 { 106 v1[i]-=mx; 107 v1[i^1]+=mx; 108 ans+=mx*(w1[i]); 109 } 110 } 111 int main() 112 { 113 scanf("%d%d%d",&n,&m,&K); 114 for(int i=1;i<=m;i++) 115 { 116 int a3; 117 scanf("%d%d%d%d",&a[i].l,&a[i].r,&a3,&a[i].w); 118 jia(a[i].l,a[i].r,a3); 119 jia(a[i].r,a[i].l,0); 120 } 121 for(;bfs();) 122 ans+=dinic(1,inf); 123 printf("%d ",ans); 124 for(int i=2;i<=cnt;i+=2) 125 { 126 jia1(a[i/2].l,a[i/2].r,inf,a[i/2].w); 127 jia1(a[i/2].r,a[i/2].l,0,-a[i/2].w); 128 jia1(a[i/2].l,a[i/2].r,v[i],0); 129 jia1(a[i/2].r,a[i/2].l,v[i+1],0); 130 } 131 jia1(0,1,K,0); 132 jia1(1,0,0,0); 133 ans=0; 134 for(;spfa();) 135 mcf(); 136 printf("%d ",ans); 137 return 0; 138 }
一遍最大流，一遍费用流。第一问跑完之后在残余网络建边，单位费用为扩容费用，