【题意】
给定一张航空图， 图中顶点代表城市， 边代表 2 城市间的直通航线。 现要求找出一条满足下述限制条件的且途经城市最多的旅行路线。
(1) 从最西端城市出发，单向从西向东途经若干城市到达最东端城市，然后再单向从东向西飞回起点(可途经若干城市) 。
(2) 除起点城市外， 任何城市只能访问 1 次。
输入文件示例
input.txt
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输出文件示例
output.txt
7
Vancouver
Edmonton
Montreal
Halifax
Toronto
Winnipeg
Calgary
Vancouver
【分析】
只有我这种智障才会想半天 保证 从西向东怎么破吧。。
都知道是怎么做的了。。。
这种回路其实相当于从起点到终点走两次 然后路径不相交。
不相交这一点约束了我们不能把两次路径分开做的。。
点只能走一遍，拆点，流量为1，费用为1.
然后按照原图也建边。（只能从西往东走，双向边事实上只建一条）
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<cmath>
#include<map>
using namespace std;
#define Maxn 2010
#define INF 0xfffffff map<string,int> M;
int n,m; struct node
{
int x,y,f,o,c,next;
}t[Maxn*];int len;
int first[Maxn]; int mymin(int x,int y) {return x<y?x:y;}
int mymax(int x,int y) {return x>y?x:y;} void ins(int x,int y,int f,int c)
{
t[++len].x=x;t[len].y=y;t[len].f=f;t[len].c=c;
t[len].next=first[x];first[x]=len;t[len].o=len+;
t[++len].x=y;t[len].y=x;t[len].f=;t[len].c=-c;
t[len].next=first[y];first[y]=len;t[len].o=len-;
} int st,ed;
queue<int > q;
int dis[Maxn],pre[Maxn],flow[Maxn];
bool inq[Maxn];
bool bfs()
{
while(!q.empty()) q.pop();
memset(dis,-,sizeof(dis));
memset(inq,,sizeof(inq));
q.push(st);dis[st]=;flow[st]=INF;inq[st]=;
while(!q.empty())
{
int x=q.front();
for(int i=first[x];i;i=t[i].next) if(t[i].f>)
{
int y=t[i].y;
if(dis[y]<dis[x]+t[i].c)
{
dis[y]=dis[x]+t[i].c;
pre[y]=i;
flow[y]=mymin(flow[x],t[i].f);
if(!inq[y])
{
inq[y]=;
q.push(y);
}
}
}
inq[x]=;q.pop();
}
if(dis[ed]==-) return ;
return ;
} void output()
{
for(int i=;i<=len;i+=)
printf("%d->%d %d %d\n",t[i].x,t[i].y,t[i].f,t[i].c);
printf("\n");
} void max_flow()
{
int ans=,sum=;
while(bfs())
{
sum+=dis[ed]*flow[ed];
ans+=flow[ed];
int now=ed;
while(now!=st)
{
t[pre[now]].f-=flow[ed];
t[t[pre[now]].o].f+=flow[ed];
now=t[pre[now]].x;
}
}
if(ans<) printf("No Solution!\n");
else
{
printf("%d\n",sum-);
}
} string s[Maxn],ss;
bool vis[Maxn*Maxn];
void dfs(int x,bool qq)
{
if(x==n) return;
if(x<n)
{
if(qq) cout<<s[x]<<endl;
dfs(x+n,qq);
if(!qq) cout<<s[x]<<endl;
return;
}
for(int i=first[x];i;i=t[i].next) if(t[i].f==&&!vis[i])
{
vis[i]=;
dfs(t[i].y,qq);
return;
}
} void init()
{
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)
{
cin>>s[i];
M[s[i]]=i;
}
for(int i=;i<=m;i++)
{
int x,y,tt;
cin>>ss;
x=M[ss];
cin>>ss;
y=M[ss];
if(x==&&y==n) ins(x+n,y,,);
else ins(x+n,y,,);
}
st=;ed=n+n;
ins(,+n,,);ins(n,n+n,,);
for(int i=;i<n;i++) ins(i,i+n,,);
memset(vis,,sizeof(vis));
} int main()
{
init();
max_flow();
dfs(,);
cout<<s[n]<<endl;
dfs(,);
return ;
}
有没有SBJ ，桑心。。。
本机测的最长路径长度是对的，方案懒得看了，应该没什么问题吧。。
2016-11-04 19:39:24