描述 Description
给定一张有向图，每条边都有一个容量 C 和一个扩容费用 W。这里扩容费用是指将容量扩大 1 所需的费用。求： 1、 在不扩容的情况下，1 到 N 的最大流； 2、 将 1 到 N 的最大流增加 K 所需的最小扩容费用。
输入格式 InputFormat
输入文件的第一行包含三个整数 N,M,K，表示有向图的点数、边数以及所需要增加的流量。接下来的 M 行每行包含四个整数 u,v,C,W，表示一条从 u 到 v，容量为 C，扩容费用为 W 的边。
输出格式 OutputFormat
输出文件一行包含两个整数，分别表示问题 1 和问题 2 的答案。
样例输入 SampleInput
10 20 5
1 7 38 58
7 4 62 61
4 10 50 61
10 5 39 65
9 1 21 45
7 9 76 30
8 7 28 20
9 6 41 2
8 9 12 54
7 5 91 75
3 4 16 22
5 1 33 47
2 3 63 86
1 3 63 95
9 3 33 82
8 10 45 87
6 8 75 19
8 4 49 75
8 1 83 71
8 5 33 69
样例输出 SampleOutput
54 110
原流量零费用建边最大流，然后在残余网络基础上原费用无限流量建边费用流。
#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;
const int inf=0x7fffffff/27.11;
const int maxn=2005;
const int maxm=10005;
int i,j,t,n,m,l,r,k,z,y,x;
struct edge
{
int to,fl,co,nx;
}e[2*maxm];
struct ed
{
int fr,to,fl,co;
}a[maxm];
int head[maxn],dis[maxn],used[maxn],cur[maxn],pre[maxn],flow[maxn];
int cnt,num;
deque <int> q;
inline void read(int &x)
{
x=0;char ch=getchar();
while (ch<'0' || ch>'9') ch=getchar();
while (ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
}
inline void ins(int u,int v,int f,int w)
{
e[num++]=((edge){v,f,w,head[u]});head[u]=num-1;
e[num++]=((edge){u,0,-w,head[v]});head[v]=num-1;
}
inline bool bfs(int s,int t,int tim)
{
int i,u,v,w;
while (!q.empty()) q.pop_front();
dis[s]=0;used[s]=tim;
q.push_back(s);
while (!q.empty())
{
u=q.front();q.pop_front();
for (i=head[u];i!=-1;i=e[i].nx)
{
v=e[i].to;
if (used[v]!=tim && e[i].fl>0)
{
used[v]=tim;
dis[v]=dis[u]+1;
q.push_back(v);
}
}
}
return (used[t]==tim);
}
int dfs(int u,int t,int flow)
{
int i,j,v,w,d,k;
if (u==t) return flow;
d=flow;
for (i=cur[u];i!=-1;i=e[i].nx)
{
v=e[i].to;
if (dis[v]==dis[u]+1 && e[i].fl>0)
{
k=dfs(v,t,min(d,e[i].fl));
e[i].fl-=k;e[i^1].fl+=k;d-=k;
if (d==0) break;
}
}
return flow-d;
}
inline void dinic(int s,int t)
{
int i,j,ans=0;
while (bfs(s,t,++cnt))
{
memcpy(cur,head,sizeof(head));
ans+=dfs(s,t,inf);
}
printf("%d",ans);
}
inline bool spfa(int s,int t,int tim)
{
int i,j,u,v,w;
while (!q.empty()) q.pop_front();
for (i=s;i<=t;i++) dis[i]=inf;
pre[s]=-1;flow[s]=inf;
q.push_back(s);used[s]=tim;dis[s]=0;
while (!q.empty())
{
u=q.front();q.pop_front();used[u]=tim-1;
for (i=head[u];i!=-1;i=e[i].nx)
{
v=e[i].to;
if (dis[v]>dis[u]+e[i].co && e[i].fl>0)
{
dis[v]=dis[u]+e[i].co;
pre[v]=i;
flow[v]=min(flow[u],e[i].fl);
if (used[v]!=tim)
{
used[v]=tim;
if (!q.empty() && dis[v]<q.front()) q.push_front(v);
else q.push_back(v);
}
}
}
}
return (dis[t]!=inf);
}
void inline mcmf(int s,int t)
{
int i,j,ans=0,k;
while (spfa(s,t,++cnt))
{
ans+=flow[t]*dis[t];
for (i=pre[t];i!=-1;i=pre[e[i^1].to]) e[i].fl-=flow[t],e[i^1].fl+=flow[t];
}
printf("%d\n",ans);
}
int main()
{
cnt=num=0;
read(n);read(m);read(k);
for (i=0;i<=n;i++) head[i]=-1;
for (i=1;i<=m;i++) read(a[i].fr),read(a[i].to),read(a[i].fl),read(a[i].co),ins(a[i].fr,a[i].to,a[i].fl,0);
dinic(1,n);
for (i=1;i<=m;i++) ins(a[i].fr,a[i].to,inf,a[i].co);
ins(0,1,k,0);
mcmf(0,n);
return 0;
}