ZJOI2010 网络扩容

wjh15101051's space

卧薪尝胆，厚积薄发。

ZJOI2010 网络扩容

Date: Wed Nov 14 20:44:43 CST 2018

In Category: NoCategory

Description：

给定一张有向图，每条边都有一个容量 $C$ 和一个扩容费用 $W$ 。这里扩容费用是指将容量扩大 $1$ 所需的费用。求：

$1$ 、在不扩容的情况下， $1$ 到 $N$ 的最大流；

$2$ 、将 $1$ 到 $N$ 的最大流增加 $K$ 所需的最小扩容费用。

$1\leqslant n\leqslant 10^3$

Solution：

先每条边建 $(a,b,f,0)$ ，然后再建一个 $(a,b,\infty,w)$ ，然后第一问就是答案为 $0$ 时的最大流，第二问就是在第一问基础上增广 $k$ 个流的费用，直接 $EK$ 即可。

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cctype>

#include<cstring>

using namespace std;

int n,m,k;

#define MAXN 1010

#define MAXM 5010

struct edge

{

	int to,nxt,f,w;

}e[MAXM << 2];

int edgenum = 0;

int lin[MAXN];

void add(int a,int b,int f,int w)

{

	e[edgenum] = (edge){b,lin[a],f, w};lin[a] = edgenum++;

	e[edgenum] = (edge){a,lin[b],0,-w};lin[b] = edgenum++;

	return;

}

#define INF 0x3f3f3f3f

int d[MAXN],rate[MAXN],pre[MAXN];

bool v[MAXN];

int s,t;

bool SPFA()

{

	memset(d,0x3f,sizeof(d));

	queue<int> q;q.push(s);

	d[s] = 0;rate[s] = INF;

	while(!q.empty())

	{

		int k = q.front();q.pop();

		v[k] = false;

		for(int i = lin[k];i != -1;i = e[i].nxt)

		{

			if(d[e[i].to] > d[k] + e[i].w && e[i].f)

			{

				d[e[i].to] = d[k] + e[i].w;

				pre[e[i].to] = i;

				rate[e[i].to] = min(rate[k],e[i].f);

				if(!v[e[i].to])

				{

					q.push(e[i].to);

					v[e[i].to] = true;

				}

			}

		}

	}

	return (d[t] != INF);

}

pair<int,int> calc()

{

	pair<int,int> res = make_pair(0,0);

	while(SPFA())

	{

		if(d[t] == 0)

		{

			res.first += rate[t];

		}

		else

		{

			if(k >= rate[t])

			{

				k -= rate[t];

				res.second += rate[t] * d[t];

			}

			else

			{

				res.second += d[t] * k;

				break;

			}

		}

		for(int i = t;i != s;i = e[pre[i] ^ 1].to)

		{

			e[pre[i]].f -= rate[t];

			e[pre[i] ^ 1].f += rate[t];

		}

	}

	return res;

}

int main()

{

	memset(lin,-1,sizeof(lin));

	scanf("%d%d%d",&n,&m,&k);

	int a,b,f,w;

	for(int i = 1;i <= m;++i)

	{

		scanf("%d%d%d%d",&a,&b,&f,&w);

		add(a,b,f,0);

		add(a,b,INF,w);

	}

	s = 1;t = n;

	pair<int,int> res = calc();

	cout << res.first << " " << res.second << endl;

	return 0;

}

In tag: 图论-最小费用最大流

wjh15101051