题目描述
给定一张有向图，每条边都有一个容量C和一个扩容费用W。这里扩容费用是指将容量扩大1所需的费用。求： 1、 在不扩容的情况下，1到N的最大流； 2、 将1到N的最大流增加K所需的最小扩容费用。
输入输出格式
输入格式：
输入文件的第一行包含三个整数N,M,K，表示有向图的点数、边数以及所需要增加的流量。 接下来的M行每行包含四个整数u,v,C,W，表示一条从u到v，容量为C，扩容费用为W的边。
输出格式：
输出文件一行包含两个整数，分别表示问题1和问题2的答案。
输入输出样例
输入样例#1： 复制
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： 复制
View Code
View Code
13 19
第一问很简单 跑一遍最大流
然后再加上给每条边加上k容量的花费流 再给n-n+1 加上容量为maxflow+k的容量流
建议全部重建图
#include<bits/stdc++.h> using namespace std; //input by bxd #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i>=(b);--i) #define RI(n) scanf("%d",&(n)) #define RII(n,m) scanf("%d%d",&n,&m) #define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k) #define RS(s) scanf("%s",s); #define ll long long #define pb push_back #define inf 0x3f3f3f3f #define CLR(A,v) memset(A,v,sizeof A) ////////////////////////////////// const int N=1000001; int n,m,S,T,maxflow,mincost,last[N],pre[N],dis[N],flow[N]; bool vis[N]; struct Edge{ int next,to,flow,dis; }edge[N<<1]; int pos=1,head[N]; void init() { pos=1; CLR(head,0); mincost=maxflow=0; } queue <int> q; int id(int x,int y) {return n*(x-1)+y;} void add(int from,int to,int flow,int dis)//flow流量 dis费用 { edge[++pos].next=head[from]; edge[pos].flow=flow; edge[pos].dis=dis; edge[pos].to=to; head[from]=pos; edge[++pos].next=head[to]; edge[pos].flow=0; edge[pos].dis=-dis; edge[pos].to=from; head[to]=pos; } bool spfa(int s,int t) { CLR(dis,0x3f); CLR(flow,0x3f); CLR(vis,0); while (!q.empty()) q.pop(); dis[s]=0; pre[t]=-1; q.push(s); vis[s]=1; int tot=0; while (!q.empty()) { int now=q.front(); q.pop(); vis[now]=0; for (int i=head[now]; i; i=edge[i].next) { int to=edge[i].to; if (edge[i].flow>0 && dis[to]>dis[now]+edge[i].dis) { dis[to]=edge[i].dis+dis[now]; flow[to]=min(edge[i].flow,flow[now]); last[to]=i; pre[to]=now; if (!vis[to]) { q.push(to); vis[to]=1; } } } } return pre[t]!=-1; } void MCMF(int s,int t) { while (spfa(s,t)) { int now=t; maxflow+=flow[t]; mincost+=flow[t]*dis[t]; while (now!=s) { edge[last[now]].flow-=flow[t];//dis . flow edge[last[now]^1].flow+=flow[t]; now=pre[now]; } } } struct node { int u,v,flow,cost; }node[N]; int s,t,k; int main() { RIII(n,m,k); rep(i,1,m) { int x;RII(node[i].u,node[i].v);RII(node[i].flow,node[i].cost); add(node[i].u,node[i].v,node[i].flow,0); } MCMF(1,n); cout<<maxflow; int temp=maxflow+k;//记录最大流 init(); add(n,n+1,temp,0); rep(i,1,m) { add(node[i].u,node[i].v,k,node[i].cost); add(node[i].u,node[i].v,node[i].flow,0); } MCMF(1,n+1); printf(" %d",mincost); // printf(" %d",maxflow); return 0; }
不全部重建图的话
给n-n+1 加上容量为k的容量流！！！
#include<bits/stdc++.h> using namespace std; //input by bxd #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i>=(b);--i) #define RI(n) scanf("%d",&(n)) #define RII(n,m) scanf("%d%d",&n,&m) #define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k) #define RS(s) scanf("%s",s); #define ll long long #define pb push_back #define inf 0x3f3f3f3f #define CLR(A,v) memset(A,v,sizeof A) ////////////////////////////////// const int N=1000001; int n,m,S,T,maxflow,mincost,last[N],pre[N],dis[N],flow[N]; bool vis[N]; struct Edge{ int next,to,flow,dis; }edge[N<<1]; int pos=1,head[N]; void init() { pos=1; CLR(head,0); mincost=maxflow=0; } queue <int> q; int id(int x,int y) {return n*(x-1)+y;} void add(int from,int to,int flow,int dis)//flow流量 dis费用 { edge[++pos].next=head[from]; edge[pos].flow=flow; edge[pos].dis=dis; edge[pos].to=to; head[from]=pos; edge[++pos].next=head[to]; edge[pos].flow=0; edge[pos].dis=-dis; edge[pos].to=from; head[to]=pos; } bool spfa(int s,int t) { CLR(dis,0x3f); CLR(flow,0x3f); CLR(vis,0); while (!q.empty()) q.pop(); dis[s]=0; pre[t]=-1; q.push(s); vis[s]=1; int tot=0; while (!q.empty()) { int now=q.front(); q.pop(); vis[now]=0; for (int i=head[now]; i; i=edge[i].next) { int to=edge[i].to; if (edge[i].flow>0 && dis[to]>dis[now]+edge[i].dis) { dis[to]=edge[i].dis+dis[now]; flow[to]=min(edge[i].flow,flow[now]); last[to]=i; pre[to]=now; if (!vis[to]) { q.push(to); vis[to]=1; } } } } return pre[t]!=-1; } void MCMF(int s,int t) { while (spfa(s,t)) { int now=t; maxflow+=flow[t]; mincost+=flow[t]*dis[t]; while (now!=s) { edge[last[now]].flow-=flow[t];//dis . flow edge[last[now]^1].flow+=flow[t]; now=pre[now]; } } } struct node { int u,v,cost; }node[N]; int s,t,k; int main() { RIII(n,m,k); rep(i,1,m) { int x;RII(node[i].u,node[i].v);RII(x,node[i].cost); add(node[i].u,node[i].v,x,0); } MCMF(1,n); cout<<maxflow; add(n,n+1,k,0); rep(i,1,m) { add(node[i].u,node[i].v,k,node[i].cost); } MCMF(1,n+1); printf(" %d",mincost); return 0; }
因为跑完一遍为残量网络
只要在这个基础上进行操作即可
首先我们记录下来跑完最大流后的残量网络。
考虑对于残量网络中的每条边 (x, y)(x,y)，在图上连一条流量无限，费用为 ww 的边。
然后从 SS 连一条边到 11，容量为 kk，以保证扩容流量正好是 kk。
只要再求一遍 SS 到 nn 的最小费用最大流就好了。