BZOJ 1834 Luogu P2604 [ZJOI2010]网络扩容 (最小费用最大流)

题目连接: (luogu) https://www.luogu.org/problemnew/show/P2604

(bzoj) https://www.lydsy.com/JudgeOnline/problem.php?id=1834

题解: 第一问所有的费用全按\(0\)建，跑完了之后很自然想到利用残余网络。

把\(n\)和一个新点\(T\)连边，然后原来的残量网络保留，在此基础上对于原来的每条边流量均按\(+\inf\)建，费用为原始费用再跑一遍即可。

时间复杂度\(O(MaxFlowMinCost(n,m))\)

（然而智障的我不会处理残量网路还想做\(K\)次费用流每次\(+1\)，真是没脑子）

代码

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#define llong long long

using namespace std;

const int N = 1002;

const int M = 10000;

const llong INF = 1000000000000ll;

struct Edge

{

	int u,v,nxt,rev; llong c,w;

} e[(M<<1)+3];

Edge ae[M+3];

int fe[N+3];

int que[N+3];

llong dis[N+3];

bool inq[N+3];

int lst[N+3];

int n,m,en,p,s,t;

llong mf,mc;

void addedge(int u,int v,llong w,llong c)

{

	en++; e[en].u = u; e[en].v = v; e[en].w = w; e[en].c = c;

	e[en].nxt = fe[u]; fe[u] = en; e[en].rev = en+1;

	en++; e[en].u = v; e[en].v = u; e[en].w = 0; e[en].c = -c;

	e[en].nxt = fe[v]; fe[v] = en; e[en].rev = en-1;

}

bool spfa()

{

	for(int i=1; i<=n; i++) dis[i] = INF;

	int head = 1,tail = 2; que[tail-1] = s; dis[s] = 0ll;

	while(head!=tail)

	{

		int u = que[head]; head++; if(head==n+1) head = 1;

		for(int i=fe[u]; i; i=e[i].nxt)

		{

			if(e[i].w>0 && dis[e[i].v]>dis[u]+e[i].c)

			{

				dis[e[i].v] = dis[u]+e[i].c;

				lst[e[i].v] = i;

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

				{

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

					que[tail] = e[i].v; tail++; if(tail==n+1) tail = 1;

				}

			}

		}

		inq[u] = false;

	}

	return dis[t]!=INF;

}

void calcflow()

{

	llong flow = INF;

	for(int i=t; i!=s; i=e[lst[i]].u)

	{

		flow = min(flow,e[lst[i]].w);

	}

	for(int i=t; i!=s; i=e[lst[i]].u)

	{

		e[lst[i]].w -= flow; e[e[lst[i]].rev].w += flow;

	}

	mf += flow; mc += flow*dis[t];

}

void mfmc()

{

	while(spfa())

	{

		calcflow();

	}

}

int main()

{

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

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

	{

		scanf("%d%d%lld%lld",&ae[i].u,&ae[i].v,&ae[i].w,&ae[i].c);

		addedge(ae[i].u,ae[i].v,ae[i].w,0ll);

	}

	s = 1; t = n; mf = mc = 0ll;

	mfmc();

	printf("%lld ",mf);

	n++; addedge(n-1,n,p,0); t = n;

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

	{

		addedge(ae[i].u,ae[i].v,INF,ae[i].c);

	}

	mf = mc = 0ll;

	mfmc();

	printf("%lld\n",mc);

	return 0;

}

巴特西

BZOJ 1834 Luogu P2604 [ZJOI2010]网络扩容 (最小费用最大流)

代码

最新文章

热门文章