Luogu P4553 80人环游世界

题目大意

自东向西有 \(n\) 个国家。有 \(m\) 个人，他们可以选择 \(n\) 个国家中任意一个开始，任意一个结束，但路线必须自东向西，且第 \(i\) 个国家必须恰好经过 \(v_i\) 人。已知每个国家到它西方的国家的费用，求最小花费。

最小费用最大流

蒟蒻不会上下界，看了一些大佬写的费用流，想了一下，发表一下自己的理解，希望对大家有帮助。

首先因为对于每个点(国家)都有经过限制，所以将拆点为入点和出点。 \(i\rightarrow (i,i+n)\)

\(s\) 向第 \(i\) 入点连容量 \(v_i\) 费用 \(0\) 的边，因为每个国家必须要有 \(v_i\) 人来，连这条边就相当于这 \(v_i\) 个人进入了该国。

同理，出点向 \(t\) 连容量 \(v_i\)费用 \(0\) 的边，表示有 \(v_i\) 个人到达了这个国家。

对于每条航线 \((u,v)\)，由 \(u\) 的入点向 \(v\) 的出点连容量 \(\infty\) 费用 \(0\) 的边，表示进入国家 \(u\) 的人可以前往国家 \(v\) 并声明到达了国家 \(v\) (即从 \(v\) 的出点到达汇点)。

最后额外再建一个点，由 \(s\) 向它连容量 \(m\) 费用 \(0\) 的边，然后让他向每个出点连容量 \(\infty\) 费用 \(0\) 的边表示这 \(m\) 个人可以随便选出发点。

然后跑最小费用最大流即可。

考虑正确性：因为跑的是最大流，所以每个出点到汇点的边一定会跑满，也就保证了每个国家限定经过次数。

又因为从那个额外点到其他出点的边费用为 \(0\) 所以这些边会被优先选择，也就意味着从源点到额外点着条边一定会跑满，也就意味着这 \(m\) 个人一定会出发(不会有人临阵脱逃)。

Code

#include<bits/stdc++.h>

//#define int long long

#define pair pair<int,int>

using namespace std;

inline void end()

{

	puts("");

	system("pause");

}

inline int read()

{

	int s=0,w=1;

	char ch=getchar();

	while(ch<'0'||ch>'9'){if(ch=='-') w=-1;ch=getchar();}

	while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();

	return s*w;

}

const int N=222,M=2e4+4,inf=0x3f3f3f3f,INF=1e9;

int s,t,maxf,minc;

int first[N],nex[M],to[M],w[M],c[M],num=1;

inline void add(int u,int v,int val,int cos)

{

	nex[++num]=first[u];

	first[u]=num;

	to[num]=v;

	w[num]=val;

	c[num]=cos;

}

inline void Add(int u,int v,int val,int cos)

{

	add(u,v,val,cos);

	add(v,u,0,-cos);

}

int dis[N],vis[N],cur[N];

inline bool SPFA()

{

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

	memset(vis,0,sizeof(vis));

	deque<int> q;

	q.push_back(s);

	vis[s]=1;dis[s]=0;

	while(!q.empty())

	{

		int u=q.front();q.pop_front();vis[u]=0;

		for(int i=first[u];i;i=nex[i])

		{

			int v=to[i];

			if(!w[i]) continue;

			if(dis[v]>dis[u]+c[i])

			{

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

				if(!vis[v])

				{

					vis[v]=1;

					if(q.empty()||dis[v]>dis[q.front()]) q.push_back(v);

					else q.push_front(v);

				}

			}

		}

	}

	if(dis[t]==inf) return 0;

	return 1;

}

int dfs(int u,int in)

{

	if(u==t) return in;

	vis[u]=1;

	int out=0;

	for(int i=cur[u];i;i=nex[i])

	{

		int v=to[i];

		if(!w[i]||vis[v]) continue;

		if(dis[v]==dis[u]+c[i])

		{

			int res=dfs(v,min(w[i],in-out));

			w[i]-=res;

			w[i^1]+=res;

			out+=res;

			minc+=c[i]*res;

			if(in==out) break;

		}

	}

	vis[u]=0;

	if(!out) vis[u]=1;

	return out;

}

void Dinic()

{

	while(SPFA())

	{

		memcpy(cur,first,sizeof(first));

		while(1)

		{

			int detal=dfs(s,1e9);

			if(!detal) break;

			maxf+=detal;

		}

	}

}

int n,m,v[N],ex;

main()

{

	n=read(),m=read();ex=2*n+1;s=0,t=ex+1;

  //ex为额外点

	Add(s,ex,m,0);

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

	{

		v[i]=read();

		Add(i+n,t,v[i],0);

		Add(ex,i+n,INF,0);

	}

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

	{

		Add(s,i,v[i],0);

		for(int j=i+1;j<=n;++j)

		{

			int val=read();

			if(val==-1) continue;

			Add(i,j+n,INF,val);

		}

	}

	Dinic();//最小费用最大流

	printf("%d",minc);

	//end();

	return 0;

}

巴特西

Luogu P4553 80人环游世界

题目大意

最小费用最大流

Code

最新文章

热门文章