1834: [ZJOI2010]network 网络扩容
Time Limit: 3 Sec Memory Limit: 64 MBSubmit: 3394 Solved: 1774
[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的边。
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
30%的数据中，N<=100
100%的数据中，N<=1000，M<=5000，K<=10
30%的数据中，N<=100
100%的数据中，N<=1000，M<=5000，K<=10
首先T1打板就好了
本题难点在T2，如何最小费用扩展网络？
其实就是最小费用流嘛
我们对所有的原边再加一条流量无限的费用为w的边，再加一个超级源指向源点，容量K费用0
再跑一遍费用流就好了
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
#define LL long long int
#define REP(i,n) for (int i = 1; i <= (n); i++)
#define Redge(u) for (int k = head[u]; k != -1; k = edge[k].next)
using namespace std;
const int maxn = 1005,maxm = 30005,INF = 1000000000;
inline int RD(){
int out = 0,flag = 1; char c = getchar();
while (c < 48 || c > 57) {if (c == '-') flag = -1; c = getchar();}
while (c >= 48 && c <= 57) {out = (out << 1) + (out << 3) + c - '0'; c = getchar();}
return out * flag;
}
int N,M,K,head[maxn],nedge = 0,d[maxn],cur[maxn],S,T,p[maxn],f[maxn];
bool vis[maxn];
struct EDGE{int from,to,f,w,next;}edge[maxm];
inline void build(int u,int v,int f,int w){
edge[nedge] = (EDGE){u,v,f,w,head[u]}; head[u] = nedge++;
edge[nedge] = (EDGE){v,u,0,-w,head[v]}; head[v] = nedge++;
}
bool bfs(){
queue<int> q;
REP(i,N) vis[i] = false,d[i] = INF;
vis[S] = true; d[S] = 0; q.push(S);
int u,to;
while (!q.empty()){
u = q.front();
q.pop();
Redge(u) if (edge[k].f && !vis[to = edge[k].to]){
d[to] = d[u] + 1;
vis[to] = true;
q.push(to);
}
}
return vis[T];
}
int dfs(int u,int minf){
if (u == T || !minf) return minf;
int flow = 0,f,to;
if (cur[u] == -2) cur[u] = head[u];
for (int& k = cur[u]; k != -1; k = edge[k].next)
if (d[to = edge[k].to] == d[u] + 1 && (f = dfs(to,min(minf,edge[k].f)))){
edge[k].f -= f;
edge[k ^ 1].f += f;
flow += f;
minf -= f;
if (!minf) break;
}
return flow;
}
int maxflow(){
int flow = 0;
while (bfs()){fill(cur,cur + maxn,-2); flow += dfs(S,INF);}
return flow;
}
int mincost(){
int cost = 0,flow = 0;
while (true){
queue<int> q;
for (int i = 0; i <= N; i++) d[i] = INF,vis[i] = false;
d[S] = 0; f[S] = INF; p[S] = 0;
q.push(S);
int to,u;
while (!q.empty()){
u = q.front(); q.pop();
vis[u] = false;
Redge(u) if (edge[k].f && d[to = edge[k].to] > d[u] + edge[k].w){
d[to] = d[u] + edge[k].w; p[to] = k; f[to] = min(f[u],edge[k].f);
if (!vis[to]) q.push(to),vis[to] = true;
}
}
if (d[T] == INF) break;
flow += f[T];
cost += f[T] * d[T];
u = T;
while (u != S){
edge[p[u]].f -= f[T];
edge[p[u] ^ 1].f += f[T];
u = edge[p[u]].from;
}
}
return cost;
}
int main(){
memset(head,-1,sizeof(head));
N = RD(); M = RD(); K = RD(); S = 1; T = N;
int a,b,f,w;
while (M--){
a = RD(); b = RD(); f = RD(); w = RD();
build(a,b,f,w);
}
int ans1 = maxflow(),ans2,E = nedge;
for (int i = 0; i < E; i += 2){
build(edge[i].from,edge[i].to,INF,edge[i].w);
edge[i].w = edge[i ^ 1].w = 0;
}
S = 0; build(S,1,K,0);
ans2 = mincost();
cout<<ans1<<' '<<ans2<<endl;
return 0;
}