29 E Quarrel - simezi

問題

A,Bの二人がそれぞれグラフの頂点1,頂点nにいる。
二人は喧嘩しているので、同時に同じ頂点にいることはできない。

Aが頂点nまで、Bが頂点1まで以下の制約を満たしながら移動する。

二人はそれぞれ1秒に1回、グラフの隣の頂点に必ず移動する
同じ頂点を何回通ってもいい
二人は同時に同じ頂点にいてはいけないが、辺上ですれ違うことは可能
二人は同時にゴールする。途中でゴールを通過するのは可能

このとき、二人がゴールにつくまでの最短経路を求めよ。

制約条件

n≦500
m≦10000

方針

明らかに無理な場合は不可能を返す。それ以外全探索。
ただし愚直に全探索すると遅い気がするのでA*探索を使った。

明らかにどうやっても無理なのは、

始点と終点が非連結
始点から終点まで、単純パスが1通りしかない
かつそのパスの長さが偶数長
かつそのパスに長さ2以上の側鎖っぽいのがついてない

この場合だけ無理と事前に判定してやる。
これはmaxFlowを流して、流量が1であることを確認して、側鎖を全部見ることで行った。

無理そうじゃない場合はA*で探索する。
コストの見積もりはmax(Aのゴールまでの距離,Bのゴールまでの距離)
ゴールまでの距離はワーシャルフロイドであらかじめ求めた。

なんか無理矢理な方針な気がする。

ソースコード

maximumFlowの部分は省略。

int n,m,d[500][500];
Graph e;
bool visit[500],use[500][500];
int pa[500][500],pb[500][500],cost[500][500];

int rec(int c){
	visit[c]=1;
	int ret=1;
	fr(i,e[c])if(!visit[i->dst])ret+=rec(i->dst);
	return ret;
}

bool can()
{
	scanf("%d%d",&n,&m);
	e.clear(); e.resize(n);
	rep(i,n)rep(j,n)d[i][j]=i==j?0:1e9;
	rep(i,m){
		int s,t; scanf("%d%d",&s,&t);
		s--; t--;
		e[s].pb(Edge(s,t,1)); e[t].pb(Edge(t,s,1));
		d[s][t]=d[t][s]=1;
	}
	int flow=maximumFlow(e,0,n-1);
	//dbg(flow);
	
	if(flow==0)return 0;
	if(flow>1)return 1;
	
	vi prev(n,-1), path;
	queue<int> q; q.push(0);
	while(!q.empty()){
		int c=q.front(); q.pop();
		visit[c]=1;
		if(c==n-1)break;
		fr(i,e[c])if(prev[i->dst]<0)prev[i->dst]=c, q.push(i->dst);
	}
	int cur=n-1;
	for(;cur!=0;cur=prev[cur])path.pb(cur);
	path.pb(0);
	
	if(path.size()%2==0)return 1;
	
	rep(i,n)visit[i]=0;
	rep(i,path.size())visit[i]=1;
	fr(i,path)fr(j,e[*i])if(!visit[j->dst]){
		int ret=rec(j->dst); //dbg(ret);
		if(ret>1)return 1;
	}
	return 0;
}
void run(){
	if(!can()){
		//cerr<<"cant"<<endl;
		cout<<-1<<endl; return;
	}
	
	rep(k,n)rep(i,n)rep(j,n)d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
	rep(i,n)rep(j,n)pa[i][j]=pb[i][j]=-1, cost[i][j]=1e9, use[i][j]=0;
	
	priority_queue<pair<int,pi> > q;
	q.push(mp(-d[0][n-1],mp(0,n-1)));
	cost[0][n-1]=0;
	
	while(!q.empty()){
		int a=q.top().second.first, b=q.top().second.second;
		//dbg(a); dbg(b);
		q.pop();
		if(use[a][b])continue;
		use[a][b]=1;
		if(a==n-1&&b==0)break;
		
		fr(i,e[a])fr(j,e[b])if(i->dst!=j->dst&&cost[i->dst][j->dst]>cost[a][b]+1)
		pa[i->dst][j->dst]=a, pb[i->dst][j->dst]=b, cost[i->dst][j->dst]=cost[a][b]+1,
		q.push(mp(-max(d[i->dst][n-1],d[j->dst][0])-cost[a][b],mp(i->dst,j->dst)));
	}
	if(cost[n-1][0]==1e9){
		cout<<-1<<endl; return;
	}
	
	vi p,pp;
	int a=n-1,b=0;
	for(;a!=0||b!=n-1;){
		p.pb(a), pp.pb(b);
		int na=pa[a][b], nb=pb[a][b];
		a=na; b=nb;
	}
	p.pb(0); pp.pb(n-1);
	
	reverse(all(p)); reverse(all(pp));
	printf("%d\n",(int)p.size()-1);
	rep(i,p.size())printf("%d ",p[i]+1); puts("");
	rep(i,p.size())printf("%d ",pp[i]+1); puts("");
}