题目描述
给定一张航空图,图中顶点代表城市,边代表 2 城市间的直通航线。
现要求找出一条满足下述限制条件的且途经城市最多的旅行路线。
从最西端城市出发,单向从西向东途经若干城市到达最东端城市,然后再单向从东向西飞回起点(可途经若干城市)。
除起点城市外,任何城市只能访问 1 次。
对于给定的航空图,试设计一个算法找出一条满足要求的最佳航空旅行路线。
拆点+最大费用最大流
题目要求我们从东向西走到终点,再从终点向东走到起点,求最多经过的城市次数,实际上我们只需要从起点向终点走两次就行,但是这题又要求具体走的方案,这个就稍微有点复杂了
建图时:
(1)除起点和终点外,每个点只能被经过1次,并产生1的贡献,因此对于除终点和起点以外的点,拆为入点和出点,并从入点向出点连一条容量为1,费用也为1的边;
(2)对于起点和终点来说,因为我们需要从起点向终点走两遍,因此对于终点和起点,在(1)所述基础上,还需要从入点向出点连一条容量为1,费用为0的边,费用为0是因为重复走过这两个点不会对答案有贡献;
(3)从源点向起点的入点连一条容量为2,费用为0的边,同理从终点的出点向汇点连一条容量为2,费用为0的边;
(4)对于有航线相连的两个城市,从靠左的出点往靠右的入点连一条容量为1,费用为0的边,容量为1是为了方便判断这条边是否被使用过;
(5)这样建完图后,跑一遍最大费用最大流,得到的就是最多经过的城市数量;
(6)但是还没完,这题还要求一个具体方案,我感觉自己求方案的方法比(非)较(常)丑陋,所以就简单说下想法吧,代码就不用看了;
(7)找具体方案时,从起点开始,遍历出点的出边,如果这条边的剩余容量为0,说明这个边是被使用过的,所以出边对应的点也使用过,顺着这个边继续往下走,直到终点为止。我们应该能够找到两条具体路径,任选一条当正向,另一条当反向即可;
C++ 代码
#include<bits/stdc++.h>
using namespace std;
vector<pair<int,int>>edges[100];
int f[1000],w[1000],incf[100],dis[100],vis[100],preb[100],pree[100],idx=-1,n,v,S=0,T=99;
unordered_map<string,int>id;
unordered_map<int,string>name;
vector<vector<int>>path;
void add(int a,int b,int c,int d){
edges[a].push_back({b,++idx}),f[idx]=c,w[idx]=d;
edges[b].push_back({a,++idx}),f[idx]=0,w[idx]=-d;
}
bool spfa(){
queue<int>nodes;
nodes.push(S);
memset(dis,-0x3f,sizeof dis);
memset(incf,0,sizeof incf);
dis[S]=0,incf[S]=0x3f3f3f3f;
while(!nodes.empty()){
int temp=nodes.front();
nodes.pop();
vis[temp]=0;
for(int i=0;i<edges[temp].size();i++){
int t=edges[temp][i].first,e=edges[temp][i].second;
if(f[e]&&dis[t]<dis[temp]+w[e]){
dis[t]=dis[temp]+w[e];
preb[t]=temp,pree[t]=e;
incf[t]=min(f[e],incf[temp]);
if(vis[t]==1) continue;
vis[t]=1;
nodes.push(t);
}
}
}
return incf[T]>0;
}
int ek(){
int res=0;
while(spfa()){
res+=dis[T]*incf[T];
for(int i=T;i!=S;i=preb[i]){
f[pree[i]]-=incf[T];
f[pree[i]^1]+=incf[T];
}
}
return res;
}
void find(int now,vector<int>&temp){
if(now==n) {
path.push_back(temp);
return;
}
temp.push_back(now);
for(int i=0;i<edges[now+n].size();i++){
int a=edges[now+n][i].first,b=edges[now+n][i].second;
if(f[b]!=0||b%2!=0) continue;
find(a,temp);
}
}
int main(){
cin>>n>>v;
for(int i=1;i<=n;i++){
string a;
cin>>a;
id[a]=i;
name[i]=a;
if(i==1||i==n){
add(i,i+n,1,1);
add(i,i+n,1,0);
}
else add(i,i+n,1,1);
}
for(int i=0;i<v;i++){
string a,b;
cin>>a>>b;
if(id[a]<id[b]) add(id[a]+n,id[b],1,0);
else add(id[b]+n,id[a],1,0);
}
add(S,1,2,0);
add(n+n,T,2,0);
int res=ek();
if(res==0) {
cout<<"No Solution!";
return 0;
}
else cout<<res<<endl;
for(int i=0;i<edges[1+n].size();i++){
int a=edges[1+n][i].first,b=edges[1+n][i].second;
if(f[b]!=0||b%2==1) continue;
vector<int>temp;
find(a,temp);
}
cout<<name[1]<<endl;
for(int i=0;i<path[0].size();i++){
cout<<name[path[0][i]]<<endl;
}
cout<<name[n]<<endl;
for(int i=path[1].size()-1;i>=0;i--){
cout<<name[path[1][i]]<<endl;
}
cout<<name[1];
return 0;
}