航空路线问题_牛客博客

题目描述
给定一张航空图，图中顶点代表城市，边代表 2 城市间的直通航线。现要求找出一条满足下述限制条件的且途经城市最多的旅行路线。

(1)从最西端城市出发，单向从西向东途经若干城市到达最东端城市，然后再单向从东向西飞回起点(可途经若干城市)。

(2)除起点城市外，任何城市只能访问 1 次。

对于给定的航空图，试设计一个算法找出一条满足要求的最佳航空旅行路线。

输入格式
第 1 行有 2 个正整数 N 和 V，N 表示城市数，N<100，V 表示直飞航线数。

接下来的 N 行中每一行是一个城市名，可乘飞机访问这些城市。城市名出现的顺序是从西向东。也就是说，设 i,j 是城市表列中城市出现的顺序，当 i>j 时，表示城市 i 在城市 j 的东边，而且不会有 2 个城市在同一条经线上。城市名是一个长度不超过15 的字符串，串中的字符可以是字母或阿拉伯数字。例如，AGR34 或 BEL4。

再接下来的 V 行中，每行有 2 个城市名，中间用空格隔开，如 city1 city2 表示 city1到 city2 有一条直通航线，从 city2 到 city1 也有一条直通航线。

输出格式
件第 1 行是旅行路线中所访问的城市总数 M。接下来的 M＋1 行是旅行路线的城市名，每行写 1 个城市名。首先是出发城市名，然后按访问顺序列出其它城市名。注意，最后 1 行（终点城市）的城市名必然是出发城市名。如果问题无解，则输出“No Solution!”。

输入输出样例
输入 #1 复制
8 9
Vancouver
Yellowknife
Edmonton
Calgary
Winnipeg
Toronto
Montreal
Halifax
Vancouver Edmonton
Vancouver Calgary
Calgary Winnipeg
Winnipeg Toronto
Toronto Halifax
Montreal Halifax
Edmonton Montreal
Edmonton Yellowknife
Edmonton Calgary
输出 #1 复制
7
Vancouver
Edmonton
Montreal
Halifax
Toronto
Winnipeg
Calgary
Vancouver

考虑问题：

除起点外，每个点只经过一次。
经过的城市最多。
最后能回到起点。

我们可以用费用流来做。

对于第一个问题直接拆点即可。
对于第二个问题，我们用费用流，经过一个城市的费用为1，跑费用最大流就能保证经过城市最多了。
对于第三个问题，因为是无向边，所以S -> T -> S 等价于两次 S -> T，所以跑两次最大流即可。

怎么输出答案呢？两次dfs处理残量网络即可，如果有流量过去，那么当前的流量肯定被流光了，dfs过去即可。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int inf=0x3f3f3f3f;
const int N=1010,M=100010;
int n,m,s,t,e[N],v[N],d[N],maxflow,res,flag;
int head[N],nex[M],to[M],w[M],flow[M],tot=1;
map<string,int> mp;
map<int,string> pt;
inline void ade(int a,int b,int c,int d){
	to[++tot]=b; w[tot]=d; flow[tot]=c; nex[tot]=head[a]; head[a]=tot;
}
inline void add(int a,int b,int c,int d){
	ade(a,b,c,d);	ade(b,a,0,-d);
}
int spfa(){
	memset(d,0xcf,sizeof d); queue<int> q;	q.push(s); d[s]=0;
	int vis[N]={0};	vis[s]=1;
	while(q.size()){
		int u=q.front();	q.pop();	vis[u]=0;
		for(int i=head[u];i;i=nex[i]){
			if(flow[i]&&d[to[i]]<d[u]+w[i]){
				d[to[i]]=d[u]+w[i];
				v[to[i]]=u;	e[to[i]]=i;
				if(!vis[to[i]])	q.push(to[i]),vis[to[i]]=1;
			}
		}
	}
	return d[t]!=0xcfcfcfcf;
}
void EK(){
	while(spfa()){
		int mi=inf;
		for(int i=t;i!=s;i=v[i])	mi=min(mi,flow[e[i]]);
		for(int i=t;i!=s;i=v[i])	flow[e[i]]-=mi,flow[e[i]^1]+=mi;
		res+=d[t]*mi;	maxflow+=mi;
	} 
}
void out1(int x){
	cout<<pt[x]<<endl;	if(x==n)	return ;
	for(int i=head[x+n];i;i=nex[i]){
		if(!flow[i]){
			out1(to[i]);	flow[i]=1; break;
		}	
	}
}
void out2(int x){
	if(x==n)	return ;
	for(int i=head[x+n];i;i=nex[i]){
		if(!flow[i]){
			out2(to[i]);	break;
		}
	}
	cout<<pt[x]<<endl;
}
signed main(){
	cin>>n>>m;	s=0; 	t=2*n+2;
	for(int i=1;i<=n;i++){
		string str;	cin>>str;	mp[str]=i;	pt[i]=str;	add(i,i+n,1,0);
	}
	add(s,1,2,0);	add(n+n,t,2,0);	add(1,1+n,1,0);	add(n,n+n,1,0);
	while(m--){
		string a,b;	cin>>a>>b;	int c=mp[a];	int d=mp[b];
		if(c>d)	swap(c,d);	add(c+n,d,1,1);	if(c==1&&d==n)	flag++;
	}
	EK();
	if(maxflow!=2){
		if(!flag)	return puts("No Solution!"),0;
		else	cout<<2<<endl;
		cout<<pt[1]<<endl<<pt[n]<<endl<<pt[1]<<endl;	return 0;
	}	
	cout<<res<<endl;
	out1(1);	out2(1);
	return 0;
}