BZOJ1834 [ZJOI2010]network 网络扩容【最大流，费用流】

2022-11-28 16:16:16

1834: [ZJOI2010]network 网络扩容

Time Limit: 3 Sec Memory Limit: 64 MB

Submit: 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

Sample Output

13 19

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;

}

码农公寓