题目：http://www.lydsy.com/JudgeOnline/problem.php?id=1834
思路：这道题跟道路扩容基本一样，先按照没有扩容的边构图，然后跑一次最大流，然后再将所有边加进去，费用为w，容量为无穷大，在从n连一条边到超级汇，容量为k，费用为0，跑一次从1到超级汇的最小费用流即可。
代码：
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
#define MAXN 1010
#define MAXM 5010
struct edge {
edge *next,*pair;
int t,f,c;
};
edge *head[MAXN];
int n,m,k;
int gap[MAXN],h[MAXN];
int E[MAXM][4];
edge *d[MAXN];
void INSERT(int s,int t,int f,int c){
edge *p=new(edge);
p->t=t;
p->f=f;
p->c=c;
p->next=head[s];
head[s]=p;
p=new(edge);
p->t=s;
p->f=0;
p->c=-c;
p->next=head[t];
head[t]=p;
head[s]->pair=head[t];
head[t]->pair=head[s];
}
int maxflow,mincost;
int sap(int v,int flow){
if (v==n){
return flow;
}
int rec=0;
for (edge *p=d[v];p;p=p->next){
if (h[v]==h[p->t]+1&&p->f){
int ret=sap(p->t,min(flow-rec,p->f));
p->f-=ret;
p->pair->f+=ret;
d[v]=p;
if ((rec+=ret)==flow){
return flow;
}
}
}
if (!(--gap[h[v]])){
h[1]=n;
}
gap[++h[v]]++;
d[v]=head[v];
return rec;
}
int dist[MAXN];
bool f[MAXN];
int aug(int v,int flow){
if (v==n+1){
maxflow+=flow;
mincost+=flow*dist[1];
return flow;
}
f[v]=false;
int rec=0;
for (edge *p=head[v];p;p=p->next){
if (p->f&&f[p->t]&&dist[v]==dist[p->t]+p->c){
int ret=aug(p->t,min(flow-rec,p->f));
p->f-=ret;
p->pair->f+=ret;
if ((rec+=ret)==flow){
return flow;
}
}
}
return rec;
}
bool relabel(){
int delta=0x7fffffff;
for (int i=0;i++<n+1;){
if (!f[i]){
for (edge *p=head[i];p;p=p->next){
if (f[p->t]&&p->f){
delta=min(delta,dist[p->t]-dist[i]+p->c);
}
}
}
}
if (delta==0x7fffffff){
return false;
}
for (int i=0;i++<n+1;){
if (!f[i]){
dist[i]+=delta;
}
}
return true;
}
int main(){
memset(head,0,sizeof(head));
scanf("%d%d%d",&n,&m,&k);
for (int i=0;i++<m;){
scanf("%d%d%d%d",&E[i][0],&E[i][1],&E[i][2],&E[i][3]);
INSERT(E[i][0],E[i][1],E[i][2],0);
}
memset(gap,0,sizeof(gap));
memset(h,0,sizeof(h));
for (int i=0;i++<n;){
d[i]=head[i];
}
gap[0]=n;
maxflow=0;
while (h[1]<n){
maxflow+=sap(1,0x7fffffff);
}
printf("%d ",maxflow);
for (int i=0;i++<m;){
INSERT(E[i][0],E[i][1],0x7fffffff,E[i][3]);
}
INSERT(n,n+1,k,0);
memset(dist,0,sizeof(dist));
maxflow=mincost=0;
do {
do {
if (maxflow==k){
break;
}
memset(f,true,sizeof(f));
} while (aug(1,0x7fffffff));
if (maxflow==k){
break;
}
} while (relabel());
printf("%d\n",mincost);
return 0;
}
