bzoj 1834[ZJOI2010]network 网络扩容

本文主要是介绍bzoj 1834[ZJOI2010]network 网络扩容，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description

给定一张有向图，每条边都有一个容量C和一个扩容费用W。这里扩容费用是指将容量扩大1所需的费用。
求：
1、在不扩容的情况下，1到N的最大流；
2、将1到N的最大流增加K所需的最小扩容费用。

Input

第一行包含三个整数N,M,K，表示有向图的点数、边数以及所需要增加的流量。
接下来的M行每行包含四个整数u,v,C,W，表示一条从u到v，容量为C，扩容费用为W的边。
N<=1000，M<=5000，K<=10

Output

输出文件一行包含两个整数，分别表示问题1和问题2的答案。

Sample Input

Sample Output

13 19

Solution

第一问显然可以用最大流直接解决
第二问，因为k不大于10，于是，跑k遍费用流，可以非常暴力的对每条流量为0的边加1流量，如果是第一次加，加入费用，如果是第二次加，给反向边加上负的费用。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;#define N 1010
#define M 5050
#define INF 0x7ffffffstruct edge 
{int x,d,y,w,c,next;
};edge side[M*2];
int last[N],dis[N],t[N],pre[N];
int n,m,k,l=1,s,e;void add(int x,int y,int w,int c)
{l++;side[l].x=x;side[l].y=y;side[l].w=w;side[l].c=c;side[l].d=0;side[l].next=last[x];last[x]=l;
}void init()
{scanf("%d%d%d",&n,&m,&k);int x,y,c,w;for (int i=1;i<=m;i++){scanf("%d%d%d%d",&x,&y,&w,&c);add(x,y,w,c);add(y,x,0,-c);}
}queue<int> Q;bool bfs()
{memset(dis,0,sizeof(dis));dis[1]=1;Q.push(1);while (!Q.empty()){int now=Q.front(); Q.pop();for (int i=last[now];i!=0;i=side[i].next){int j=side[i].y;if (side[i].w==0 || dis[j]!=0) continue;dis[j]=dis[now]+1;Q.push(j);}}if (dis[n]==0) return false;else return true;
}int dfs(int x,int maxf)
{if (x==n || maxf==0) return maxf;int ret=0;for (int i=last[x];i!=0;i=side[i].next){int j=side[i].y;if (side[i].w==0 || dis[x]+1!=dis[j]) continue;int f=dfs(j,min(maxf-ret,side[i].w));side[i].w-=f;side[i^1].w+=f; ret+=f;if (ret==maxf) break;}return ret;
}void dinic()
{int ans=0;while (bfs()) ans+=dfs(1,INF);printf("%d ",ans);
}void spfa()
{for (int i=1;i<=n;i++)dis[i]=INF;memset(t,0,sizeof(t));memset(pre,0,sizeof(pre));Q.push(1);dis[1]=0; t[1]=1;while (!Q.empty()){int now=Q.front(); Q.pop();for (int i=last[now];i!=0;i=side[i].next){if (side[i].w<=0) continue;int j=side[i].y;if (dis[j]>dis[now]+side[i].d){dis[j]=dis[now]+side[i].d;pre[j]=i;if (t[j]==0){Q.push(j);t[j]=1;}}}if (now!=1) t[now]=0;}//printf("%d\n",dis[n]);
}int find()
{spfa();int s=0;for (int i=pre[n];;i=pre[side[i].x]){side[i].w-=1;side[i^1].w+=1;if (side[i].w==0){side[i].w=1;if (side[i].d==side[i].c) side[i^1].d=side[i^1].c;side[i].d=side[i].c;}if (side[i].x==1) break;}return dis[n];
}int main()
{init();dinic();for (int i=2;i<=l;i+=2)if (side[i].w==0){side[i].w=1;side[i].d=side[i].c;}int ans=0;for (int i=1;i<=k;i++)ans+=find();printf("%d\n",ans);return 0;
}