自动搬运

查看原文

来自洛谷，原作者为

	w4p3r I think all our memories, and everything in it. . .can be nothing but the fiction we tell ourselves.

搬运于2025-08-24 21:41:25，当前版本为作者最后更新于2019-01-15 23:11:54，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

思路：

这道题求出答案应该不难，

对于每个点拆成Ai和Bi两个点，两个点之间的容量为1，边权为1，（因为每个点只能选一次，每选一个点可以对答案造成1的贡献） （若i为1或n容量应为2，因为这两个点可以选两次）

对于每条从u到v的边，让Bu向Av建一条容量为1，边权为0的边**（因为每条边只能选一次，选边并不会对答案造成影响）**

最后从源点向A1建一条容量为2，边权为0,的边

从Bn向汇点建一条容量为2，边权为0的边

跑最大费用最大流即可

问题是如何输出城市呢？

我的思路是进行两遍dfs，

第一次dfs找到一条1到n所有边的flow都为0的路径正序输出，

第二次dfs找到另一条1到n所有边的flow都为0的路径倒序输出（这次n不输出）

还是有一定坑点的，具体看代码吧

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<cmath>
#include<queue>
#include<map>
#define inf 0x7fffffff/2
#define eps 1e-6
#define N 100010
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
inline ll read()
{
	char ch=getchar();
	ll s=0,w=1;
	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;
}
int n,m;
map<string,int>ma;
struct edge
{
	int next,to,fl,v;
}e[N<<1];
int head[N],cnt=1;
int dist[N],pre[N],vis[N],minn[N];
queue<int>Q;
int s,t,val,flag[N],check;
string ss[N];
inline void add_edge(int from,int to,int fl,int v){e[++cnt].to=to;e[cnt].next=head[from];e[cnt].fl=fl;e[cnt].v=v;head[from]=cnt;}
void update(int x,int flow)
{
	e[pre[x]].fl-=flow;
	e[pre[x]^1].fl+=flow;
	if(e[pre[x]^1].to)update(e[pre[x]^1].to,flow);
}
inline int spfa()
{
	memset(vis,0,sizeof(vis));while(!Q.empty())Q.pop();
	for(register int i=1;i<=t;i++)dist[i]=-inf;
	minn[s]=inf;dist[s]=0;Q.push(s);vis[s]=1;
	while(!Q.empty())
	{
		int x=Q.front();Q.pop();vis[x]=0;
		for(register int i=head[x];i;i=e[i].next)
		{
			if(dist[e[i].to]<dist[x]+e[i].v&&e[i].fl)
			{
				dist[e[i].to]=dist[x]+e[i].v;
				pre[e[i].to]=i;
				minn[e[i].to]=min(minn[x],e[i].fl);
				if(!vis[e[i].to])
				{
					vis[e[i].to]=1;
					Q.push(e[i].to);
				}
			}
		}
	}
	if(dist[t]==-inf)return -inf;
	update(t,minn[t]);val+=minn[t];
	return minn[t]*dist[t];
}
inline int EK()
{
	int sum=0;
	while(1)
	{
		int x=spfa();
		if(x==-inf)return sum;
		sum+=x;
	}
}//最大费用最大流
void dfs1(int x)
{
	cout<<ss[x]<<endl;//第一遍dfs正序输出
	vis[x]=1;//不让第二次dfs再找到这个点
	for(register int i=head[x];i;i=e[i].next)
	{
		if(e[i].to>n&&e[i].to<=2*n&&e[i].fl==0){dfs1(e[i].to-n);break;}//第一次dfs只找一条路径，找到就break
	}
}
void dfs2(int x)
{
	vis[x]=1;
	for(register int i=head[x];i;i=e[i].next)
	{
		if(e[i].to>n&&e[i].to<=2*n&&e[i].fl==0&&!vis[e[i].to-n]){dfs2(e[i].to-n);}//不走第一次路径走过的点
	}
	cout<<ss[x]<<endl;//第二次dfs倒序输出
}//vis[n]在第一次dfs已经设为1，不会输出第二次
int main()
{
	n=read(),m=read();t=n*2+1;
	for(register int i=1;i<=n;i++)
	{
		cin>>ss[i];ma[ss[i]]=i;
	}
	for(register int i=1;i<=m;i++)
	{
		string s1,s2;
		cin>>s1>>s2;
		int x=ma[s1],y=ma[s2];
		if(x>y)swap(x,y);//让西边的点向东边建边
        if(x==1&&y==n)check=1;//如果有直接1-n的路径
		add_edge(x,y+n,1,0);add_edge(y+n,x,0,0);
	}
	add_edge(s,n+1,inf,0);add_edge(n+1,s,0,0);
	add_edge(n,t,inf,0);add_edge(t,n,0,0);
	for(register int i=1;i<=n;i++)
	{
		if(i!=1&&i!=n)add_edge(i+n,i,1,1),add_edge(i,i+n,0,-1);
		else add_edge(i+n,i,2,1),add_edge(i,i+n,0,-1);
	}
    //对于我的代码,1-n是Bi,n+1-2*n是Ai
	int maxflow=EK();
	if(val==2)printf("%d\n",maxflow-2);//1和n被重复计算，应该减去
	else if(val==1&&check){printf("%d\n",2);cout<<ss[1]<<endl<<ss[n]<<endl<<ss[1]<<endl;return 0;}//如果有1-n直接的路径即使只有1条也是满足条件的
	else {printf("No Solution!\n");return 0;}
	memset(vis,0,sizeof(vis));
	dfs1(1);dfs2(1);//输出城市
	return 0;
}

如果认为我这篇题解对你有帮助的可以给我点一下赞qwq。如果有任何疑问，或者认为我的题解有什么问题的话，请务必私信我，感激不尽！我会努力把我的题解写得最好的!