[ZJOI2010 network 网络扩容]费用流

【题目地址】http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1834
【算法分析】
很裸啊。
第一问直接最大流，但是我写得是边权全部为0的费用流= =，方便第二问。。。
第二问的话，就是每条边加多一条容量无限，费用为给定费用的边。
然后加多一个超汇点，n向它连一个maxflow+K的边。
最后输出费用即可。
【其它】1Y，水过留痕。。。
【CODE】
#include #include const int N=1555;
const int E=5555*4;
const int INF=0x7FFFFFFF/2-55;
struct edge{int x,y,c,w;edge *next,*op;}g[E],*ls[N],*fa[N];
int n,m,q,e,flow,cost;
int lx[E],ly[E],lc[E],lw[E],L[N],d[N],v[N];

void add(int x,int y,int c,int w){
g[++e].x=x; g[e].y=y; g[e].c=c; g[e].w=w;
g[e].next=ls[x]; ls[x]=&g[e]; g[e].op=&g[e+1];
g[++e].x=y; g[e].y=x; g[e].c=0; g[e].w=-w;
g[e].next=ls[y]; ls[y]=&g[e]; g[e].op=&g[e-1];
}

void push_back(){
for (int i=2;i<=e;i+=2){
edge *t=&g[i];
t->op->c+=t->c;
t->c=0;
}
}

bool spfa(){
int head=0,tail=1;
for (int i=1;i<=n;i++){
v[i]=0;
d[i]=INF;
}
v[1]=1; d[1]=0; L[1]=1;
while (head!=tail){
head++; if (head>=N) head=0;
for (edge *t=ls[L[head]];t;t=t->next)
if (t->c && d[t->x]+t->w d[t->y]=d[t->x]+t->w;
fa[t->y]=t;
if (!v[t->y]){
v[t->y]=1;
tail++; if (tail>=N) tail=0;
L[tail]=t->y;
}
}
v[L[head]]=0;
}
if (d[n]==INF) return false;
return true;
}

void change(){
int nf=INF;
for (int i=n;i!=1;i=fa[i]->x)
if (fa[i]->c flow+=nf; cost+=d[n]*nf;
for (int i=n;i!=1;i=fa[i]->x){
fa[i]->c-=nf;
fa[i]->op->c+=nf;
}
}

void mincost_maxflow(){
flow=cost=0;
while (spfa()) change();
}

int main(){
scanf("%d%d%d",&n,&m,&q);
for (int i=1;i<=m;i++){
scanf("%d%d%d%d",&lx[i],&ly[i],&lc[i],&lw[i]);
add(lx[i],ly[i],lc[i],0);
}
mincost_maxflow();
printf("%d ",flow);
for (int i=1;i<=m;i++)
add(lx[i],ly[i],INF,lw[i]);
add(n,n+1,flow+q,0);
n++;
push_back();
mincost_maxflow();
printf("%dn",cost);
}