Description
给定一张有向图，每条边都有一个容量C和一个扩容费用W。这里扩容费用是指将容量扩大1所需的费用。求： 1、 在不扩容的情况下，1到N的最大流； 2、 将1到N的最大流增加K所需的最小扩容费用。
Input
输入文件的第一行包含三个整数N,M,K，表示有向图的点数、边数以及所需要增加的流量。 接下来的M行每行包含四个整数u,v,C,W，表示一条从u到v，容量为C，扩容费用为W的边。
Output
输出文件一行包含两个整数，分别表示问题1和问题2的答案。
Sample Input
5 8 2
1 2 5 8
2 5 9 9
5 1 6 2
5 1 1 8
1 2 8 7
2 5 4 9
1 2 1 1
1 4 2 1
1 2 5 8
2 5 9 9
5 1 6 2
5 1 1 8
1 2 8 7
2 5 4 9
1 2 1 1
1 4 2 1
Sample Output
13 19
30%的数据中，N<=100
100%的数据中，N<=1000，M<=5000，K<=10
30%的数据中，N<=100
100%的数据中，N<=1000，M<=5000，K<=10
无聊的最大流+费用流
//Serene
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
using namespace std;
const int maxn=1000+10,maxm=3*5000+10,INF=0x3f3f3f3f;
int n,m,k,tu[maxn],S,T; int aa,bb;char cc;
int read() {
aa=0;cc=getchar();bb=1;
while(cc<'0'||cc>'9') {
if(cc=='-') bb=-1;
cc=getchar();
}
while(cc>='0'&&cc<='9') aa=aa*10+cc-'0',cc=getchar();
return aa*bb;
} struct Node{
int x,y,cap,flow,w;
Node(){}
Node(int x,int y,int cap,int w) :x(x),y(y),cap(cap),w(w){}
}node[2*maxm]; int cur[maxn],fir[maxn],nxt[2*maxm],e=1;
void add(int x,int y,int z,int w) {
node[++e]=Node(x,y,z,w); nxt[e]=fir[x];fir[x]=e;
node[++e]=Node(y,x,0,-w); nxt[e]=fir[y];fir[y]=e;
} int zz[maxn],from[maxn],dis[maxn];bool vis[maxn];
bool spfa() {
int s=1,t=0,x,y,z;
memset(dis,0x3f3f3f3f,sizeof(dis));
memset(zz,0,sizeof(zz));
memset(vis,0,sizeof(vis));
zz[++t]=S;vis[S]=1;dis[S]=0;
while(s<=t) {
x=zz[s%maxn];
for(y=fir[x];y;y=nxt[y]) {
z=node[y].y;
if(dis[z]<=dis[x]+node[y].w||node[y].flow>=node[y].cap) continue;
if(!vis[z]) {
t++; zz[t%maxn]=z;
vis[z]=1;
}
from[z]=y;
dis[z]=dis[x]+node[y].w;
}
vis[x]=0;s++;
}
return dis[T]!=INF;
} int MCMF() {
int rs=0,now=k;
while(spfa()&&k) {
now=k;
for(int i=T;i!=S;i=node[from[i]].x) now=min(now,node[from[i]].cap-node[from[i]].flow);
now=min(now,k);k-=now;
for(int i=T;i!=S;i=node[from[i]].x) {
node[from[i]].flow+=now;
node[from[i]^1].flow-=now;
rs+=now*node[from[i]].w;
}
}
return rs;
}
////////////////////////////////////
bool BFS() {
int s=1,t=0,x,y,z;
memset(dis,-1,sizeof(dis));
dis[S]=0;zz[++t]=S;
while(s<=t) {
x=zz[s];s++;
for(y=fir[x];y;y=nxt[y]) {
z=node[y].y;
if(dis[z]!=-1||node[y].flow>=node[y].cap) continue;
zz[++t]=z; dis[z]=dis[x]+1;
}
}
return dis[T]!=-1;
} int DFS(int pos,int maxf) {
if(pos==T||!maxf) return maxf;
int rs=0,now,z;
for(int &y=cur[pos];y;y=nxt[y]) {
z=node[y].y;
if(dis[z]!=dis[pos]+1||node[y].flow>=node[y].cap) continue;
now=DFS(z,min(maxf,node[y].cap-node[y].flow));
rs+=now;maxf-=now;
node[y].flow+=now;
node[y^1].flow-=now;
}
if(!rs) dis[pos]=-1;
return rs;
} int dinic() {
int re=0;
while(BFS()) {
memcpy(cur,fir,sizeof(fir));
re+=DFS(S,INF);
}
return re;
} int ff[3*maxm],ff_tot=0; int main() {
n=read();m=read();k=read();
int x,y,z,w;S=1;T=n;
for(int i=1;i<=m;++i) {
x=read();y=read();z=read();w=read();
add(x,y,z,0);
ff[3*ff_tot+1]=x;ff[3*ff_tot+2]=y;ff[3*(++ff_tot)]=w;
}
printf("%d ",dinic());
for(int i=1;i<=ff_tot;++i) add(ff[i*3-2],ff[i*3-1],INF,ff[i*3]);
printf("%d",MCMF());
return 0;
}
模板拼接