题目描述

给定一张有向图，每条边都有一个容量C和一个扩容费用W。这里扩容费用是指将容量扩大1所需的费用。

求： 

1、在不扩容的情况下，1到N的最大流； 

2、将1到N的最大流增加K所需的最小扩容费用。

输入

第一行包含三个整数N,M,K，表示有向图的点数、边数以及所需要增加的流量。 

接下来的M行每行包含四个整数u,v,C,W，表示一条从u到v，容量为C，扩容费用为W的边。

N<=1000，M<=5000，K<=10

输出

输出文件一行包含两个整数，分别表示问题1和问题2的答案。

 

第一问没啥可说的，直接最大流就行。第二问显然是求最小费用最大流，第二次加边直接残量网络上把对应边建出来，不用再重新建图，只要把第一次建的边边权赋成INF，就能保证一定走的是第二次加的边。第二次加的边因为不确定每条边容量，所以都设成INF，但又要限制总流量，所以新建一个源点连一条边到原来的源点，容量为k，这样就保证了全图流量。

最后附上代码。

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;queue
            
             Q;int A[5010];int B[5010];int C[5010];int D[5010];int f[5010];int vis[5010];int c[100001];int d[100001];int q[100001];int to[100001];int val[100001];int next[100001];int from[100001];int head[100001];int S,T;int sum;int ans=0;int tot=1;int n,m,k;int max_flow=0;int INF=2147483647;void add(int x,int y,int z,int w){ tot++; next[tot]=head[x]; head[x]=tot; to[tot]=y; c[tot]=z; val[tot]=w; from[tot]=x; tot++; next[tot]=head[y]; head[y]=tot; to[tot]=x; c[tot]=0; val[tot]=-w; from[tot]=y;}int dfs(int x,int maxflow){ if(x==T) { return maxflow; } int used=0; int nowflow; for(int i=head[x];i;i=next[i]) { if(c[i]!=0&&d[to[i]]==d[x]+1) { nowflow=dfs(to[i],min(maxflow-used,c[i])); c[i]-=nowflow; c[i^1]+=nowflow; used+=nowflow; if(nowflow==maxflow) { return maxflow; } } } if(used==0) { d[x]=-1; } return used;}bool bfs(int S,int T){ memset(d,-1,sizeof(d)); memset(q,0,sizeof(q)); d[S]=0; int l=0; int r=0; q[r++]=S; while(l
             
              d[now]+val[i]) { d[to[i]]=d[now]+val[i]; f[to[i]]=i; if(!vis[to[i]]) { Q.push(to[i]); vis[to[i]]=1; } } } } return d[T]!=INF;}void result(){ int now=T; int flow=INF; while(now!=S) { flow=min(flow,c[f[now]]); now=from[f[now]]; } max_flow+=flow; sum+=d[T]*flow; now=T; while(now!=S) { c[f[now]]-=flow; c[f[now]^1]+=flow; now=from[f[now]]; }}void find_min(){ while(SPFA()) { result(); }}int main(){ scanf("%d%d%d",&n,&m,&k); S=1; T=n; for(int i=1;i<=m;i++) { scanf("%d%d%d%d",&A[i],&B[i],&C[i],&D[i]); add(A[i],B[i],C[i],0); } dinic(); printf("%d ",ans); for(int i=1;i<=m;i++) { add(A[i],B[i],INF,D[i]); } S=0; add(S,1,k,0); find_min(); printf("%d",sum);}