2269-Traveling Salesman Problem

AOJ

問題文

解法

グラフを圧縮する．
入次数と出次数が1のグラフが連続する部分を探す．
ループしている場合に注意する．

実装(C++)

#include <vector>
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <map>
#include <queue>
#include <cstdlib>
using namespace std;
typedef long long Weight;
typedef pair<int,Weight> P;
struct Node{
	vector<P> in,out;//入・出
	bool compressed;//すでに圧縮されているか
	int comp_exit;//圧縮されている場合，次の所
	int comp_start;//圧縮されている場合，開始地点
	int dist_exit;//圧縮されている場合，次の所までの距離
	int dist_start;//圧縮されている場合，開始地点までの距離
	int node_no; //圧縮されていない場合のノード番号
	Node(){compressed=false;}
};
const Weight INF=9999999999999999LL;
int n,m;
Node nodes[100000];
vector<Weight> d[9000];
struct Edge{
	int src,dst;
	Weight weight;
	Weight flow;
	Edge(int f,int t,int c):src(f),dst(t),weight(c){}
};
struct Node2:public vector<Edge>{
	//ここに頂点の情報を記述する
};
bool operator<(const Edge &a,const Edge &b){
	return a.weight!=b.weight?a.weight<b.weight:a.dst==b.dst?a.src<b.src:a.dst<b.dst;
}
bool operator>(const Edge &a,const Edge &b){return b<a;}
typedef vector<Node2> Graph;
typedef vector<vector<Weight> > Matrix;
vector<Weight> dijkstra(const Graph &G,int start){
	typedef pair<int,Weight> P;
	vector<Weight> res(G.size(),INF);
	res[start]=0;
	priority_queue<P,vector<P>,greater<P> > que;
	que.push(P(0,start));
	while(!que.empty()){
		P t=que.top();que.pop();
		if(res[t.second]<t.first)continue;
		for(int i=0;i<(int)G[t.second].size();i++){
			Edge e=G[t.second][i];
			if(res[e.dst]>res[t.second]+e.weight){
				res[e.dst]=res[t.second]+e.weight;
				que.push(P(res[e.dst],e.dst));
			}
		}
	}
	return res;
}

#define CHECK(k) (nodes[k].compressed==true||nodes[k].in.size()!=1||nodes[k].out.size()!=1)
void compress(int v){
	if(CHECK(v))return;//圧縮不能
	int start_,end;
	end=v;start_=v;
	while(1){
		if(CHECK(nodes[end].out[0].first))break;
		end=nodes[end].out[0].first;
		if(end==v){
			cout<<-1<<endl;
			exit(0);
		}
	}
	while(1){
		if(CHECK(nodes[start_].in[0].first))break;
		start_=nodes[start_].in[0].first;
		if(start_==v){
			cout<<-1<<endl;
			exit(0);
		}
	}
	if(start_==end)return;
	v=start_;
	int L=0;
	while(1){
		nodes[v].compressed=true;
		nodes[v].comp_exit=end;
		nodes[v].comp_start=start_;
		nodes[v].dist_start=L;
		if(v==end)break;
		L+=nodes[v].out[0].second;
		v=nodes[v].out[0].first;
	}
	v=start_;
	while(1){
		nodes[v].dist_exit=L-nodes[v].dist_start;
		if(v==end)break;
		v=nodes[v].out[0].first;
	}
	nodes[start_].out.clear();
	nodes[end].in.clear();
	nodes[start_].out.push_back(P(end,L));
	nodes[end].in.push_back(P(start_,L));
}
#undef CHECK

Weight min_dist(int s,int e){
	//まず両方圧縮されている場合のチェック
	if(nodes[s].compressed&&nodes[e].compressed){
		if(nodes[s].comp_exit==nodes[e].comp_exit){
			if(nodes[s].dist_start<nodes[e].dist_start){
				return nodes[e].dist_start-nodes[s].dist_start;
			}
		}
	}
	Weight res=0;
	if(nodes[s].compressed==true){
		res+=nodes[s].dist_exit;
		s=nodes[s].comp_exit;
	}

	if(nodes[e].compressed==true){
		res+=nodes[e].dist_start;
		e=nodes[e].comp_start;
	}
	return res+d[nodes[s].node_no][nodes[e].node_no];
}
int main() {
	nodes[0].compressed=true;
	scanf("%d%d",&n,&m);
	for(int i=0;i<m;i++){
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		--a;--b;
		nodes[a].out.push_back(P(b,(Weight)c));
		nodes[b].in.push_back(P(a,(Weight)c));
	}
	for(int i=0;i<n;i++){
		compress(i);
	}
	for(int i=0;i<n;i++){
		if(nodes[i].in.empty()||nodes[i].out.empty()){
			cout<<-1<<endl;
			return 0;
		}
	}
	nodes[0].compressed=false;
	int k=0;
	for(int i=0;i<n;i++){
		if(nodes[i].compressed){
			if(nodes[i].comp_exit==i||nodes[i].comp_start==i){
				nodes[i].compressed=false;
			}
		}
		nodes[i].node_no=k;
		k+=nodes[i].compressed==false;
	}
	Graph G(k);
	for(int i=0;i<n;i++){
		if(nodes[i].compressed==false){
			int q=nodes[i].node_no;
			for(int j=0;j<(int)nodes[i].out.size();j++){
				G[q].push_back(Edge(q,nodes[nodes[i].out[j].first].node_no,nodes[i].out[j].second));
			}
		}
	}
	if(k>=9000)exit(-1);
	for(int i=0;i<n;i++){
		if(nodes[i].compressed==false){
			d[nodes[i].node_no]=dijkstra(G,nodes[i].node_no);
		}
	}
	Weight res=0;
	for(int i=0;i<n;i++){
		res+=min_dist(i,(i+1)%n);
		if(min_dist(i,(i+1)%n)>=INF){
			cout<<"-1"<<endl;
			return 0;
		}
	}
	cout<<res<<endl;
	return 0;
}