1834: [ZJOI2010]network 网络扩容
Time Limit: 3 Sec Memory Limit: 64 MBSubmit: 3735 Solved: 2001
[Submit][Status][Discuss]
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
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
HINT
Source
大水提，第一问就是最大流，dinic跑一下
第二问，我们在残量网络上进行建图，在题目给的那些边都进行连边，流量inf，费用为题目给的费用
dinic跑完的剩下边不用动，费用为0即可，s向1连一条流量为k，费用为0的边 跑一下最小费用最大流即可
#include <bits/stdc++.h>#define ll long long#define inf 1e9+10using namespace std;inline int read(){int x=0;int f=1;char ch=getchar();while(!isdigit(ch)) {if(ch==‘-‘) f=-1;ch=getchar();}while(isdigit(ch)) {x=x*10+ch-‘0‘;ch=getchar();}return x*f;}const int MAXN=1e5+10;struct node{int y,next,back,flow,w;}e[MAXN];int len,linkk[MAXN],head,tail,level[1100],s,t,n,m,x[MAXN],y[MAXN],f[MAXN],c[MAXN],dis[1100],ans,vis[1100],q[MAXN],k;inline void insert(int x,int y,int f,int c){e[++len].y=y;e[len].next=linkk[x];linkk[x]=len;e[len].flow=f;e[len].back=len+1;e[len].w=c;e[++len].y=x;e[len].next=linkk[y];linkk[y]=len;e[len].flow=0;e[len].back=len-1;e[len].w=-c;}namespace dinicc{inline bool getlevel(){head=tail=0;memset(level,-1,sizeof(level));level[s]=0;q[++tail]=s;while(head<tail){int tn=q[++head];for(int i=linkk[tn];i;i=e[i].next){if(level[e[i].y]==-1&&e[i].flow){level[e[i].y]=level[tn]+1;q[++tail]=e[i].y;}}}return level[t]>=0;}inline int getmaxflow(int x,int flow){if(x==t) return flow;int f=0,d;for(int i=linkk[x];i;i=e[i].next){if(e[i].flow&&level[e[i].y]==level[x]+1){if(d=getmaxflow(e[i].y,min(e[i].flow,flow-f))){f+=d;e[i].flow-=d;e[e[i].back].flow+=d;if(f==flow) return f;}}}if(!f) level[x]=-1;return f;}inline int dinic(){int ans=0,d;while(getlevel()){while(d=getmaxflow(s,inf)) ans+=d;}return ans;}}namespace zkww{inline bool getdis(){memset(vis,0,sizeof(vis));memset(dis,10,sizeof(dis));dis[t]=0;deque<int>q;q.push_back(t);while(!q.empty()){int tn=q.front();q.pop_front();for(int i=linkk[tn];i;i=e[i].next){if(dis[tn]-e[i].w<dis[e[i].y]&&e[e[i].back].flow){dis[e[i].y]=dis[tn]-e[i].w;if(!vis[e[i].y]){vis[e[i].y]=1;if(!q.empty()&&dis[e[i].y]<dis[q.front()]) q.push_front(e[i].y);else q.push_back(e[i].y);}}}vis[tn]=0;}return dis[s]<168430090;}inline int getcost(int x,int flow){ ???????int f=0,d;vis[x]=1;if(x==t) return flow;for(int i=linkk[x];i;i=e[i].next){if(e[i].flow&&dis[e[i].y]==dis[x]-e[i].w&&!vis[e[i].y]){if(d=getcost(e[i].y,min(flow-f,e[i].flow))){f+=d;e[i].flow-=d;e[e[i].back].flow+=d;ans+=e[i].w*d;if(f==flow) return f;}}}return f;}inline void zkw(){while(getdis()){vis[t]=1;while(vis[t]){memset(vis,0,sizeof(vis));getcost(s,inf);}}}}void build(){s=0;t=n;insert(s,1,k,0);for(int i=1;i<=m;i++){insert(x[i],y[i],inf,c[i]);}}int main(){using namespace dinicc;using namespace zkww;n=read();m=read();k=read();s=1;t=n;for(int i=1;i<=m;i++){x[i]=read();y[i]=read();f[i]=read();c[i]=read();insert(x[i],y[i],f[i],0);}ans=dinic();cout<<ans<<‘ ‘;build();ans=0;zkw();cout<<ans<<endl;return 0;}
BZOJ 1834 ZJOI2010 network 网络扩容
原文地址：https://www.cnblogs.com/something-for-nothing/p/9012332.html