题目描述
给定一张有向图，每条边都有一个容量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<cmath>
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
queue<int>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<r)
{
int now=q[l];
for(int i=head[now];i;i=next[i])
{
if(d[to[i]]==-1&&c[i]!=0)
{
d[to[i]]=d[now]+1;
q[r++]=to[i];
}
}
l++;
}
if(d[T]!=-1)
{
return true;
}
return false;
}
void dinic()
{
while(bfs(S,T)==true)
{
ans+=dfs(S,INF);
}
}
bool SPFA()
{
for(int i=0;i<=T;i++)
{
d[i]=INF;
}
d[S]=0;
Q.push(S);
vis[S]=1;
while(!Q.empty())
{
int now=Q.front();
Q.pop();
vis[now]=0;
for(int i=head[now];i;i=next[i])
{
if(!c[i])
{
continue;
}
if(d[to[i]]>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);
}