AOJ 2269 - Traveling Salesman Problem

問題 : 巡回セールスマン問題

解法 :
与えられたグラフは,(validなものであれば) 問題の制約通り, 有向木に辺をいくつか(最大501本)足したものとなる.
また, 枝分かれや併合・子がある(となる)頂点が, 述べ 1000 個程度より多くあると, validなグラフが構成できない(頂点1から全ての頂点に行く事が不可能であるため).

以上を踏まえて, グラフを縮約することを考える. 縮約したグラフは, 頂点が最大で 1000 個程度なので, 全点対最短距離がO(N^2 log N) で求まる (O(N^3)で求めても間に合う).

(グラフの縮約は, cos さんのやり方を参考にしました.

コード :

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

#define MAX_N (100010)

using namespace std;

typedef long long lint;

struct edge {
	int to, cost;
	edge(int to, int cost) : to(to), cost(cost) {}
	edge(){}
};

vector<edge> g[MAX_N];
bool vis[MAX_N];
int tVertex[MAX_N];
int len[MAX_N], dist[MAX_N], belong[MAX_N];
int par[MAX_N], chi[MAX_N];
int inDeg[MAX_N], outDeg[MAX_N];
int d[1024][1024];
int idx;

void findCompress(int v)
{
	vis[v] = true;
	
	for (int i = 0; i < g[v].size(); i++){
		edge e = g[v][i];
		if (!vis[e.to]){
			findCompress(e.to);
		}
	}
	
	if (!v || inDeg[v] > 1 || outDeg[v] > 1){
		tVertex[v] = idx++;
	}
}

int s;
int makeCompress(int now, int p, int cost, int id)
{
	if (~tVertex[now]){
		belong[now] = -1;
		len[id] = cost;
		d[tVertex[p]][tVertex[now]] = min(cost, d[tVertex[p]][tVertex[now]]);
		cost = 0;
		p = now;
	}
	
	if (vis[now]) return (tVertex[now]);
	if (!~tVertex[now]) belong[now] = id;
	vis[now] = true;
	par[now] = tVertex[p];
	dist[now] = cost;
	
	int r = -1;
	for (int i = 0; i < g[now].size(); i++){
		int nid = id;
		if (~tVertex[now]) nid = ++s;
		r = makeCompress(g[now][i].to, p, cost + g[now][i].cost, nid);
	}
	if (~tVertex[now]) r = tVertex[now];
	
	return (chi[now] = r);
}

int main()
{
	int n, m;
	
	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;
		for (int i = 0; i < g[a].size(); i++){
			if (g[a][i].to == b){
				g[a][i].cost = min(g[a][i].cost, c);
				goto updated;
			}
		}
		
		g[a].push_back(edge(b, c));
		outDeg[a]++; inDeg[b]++;
		updated:;
	}
	
	memset(vis, 0, sizeof(vis));
	memset(tVertex, -1, sizeof(tVertex));
	memset(par, -1, sizeof(par));
	findCompress(0);
	
	if (idx >= 1024) return (!printf("-1\n"));
	for (int i = 0; i < n; i++) if (vis[i] == false) return (!printf("-1\n"));
	
	for (int i = 0; i < 1024; i++){
		for (int j = 0; j < 1024; j++){
			d[i][j] = 1 << 25;
		}
		d[i][i] = 0;
	}
	memset(vis, 0, sizeof(vis));
	makeCompress(0, 0, 0, 0);
	
	for (int k = 0; k < idx; k++){
		for (int i = 0; i < idx; i++){
			for (int j = 0; j < idx; j++){
				d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
			}
		}
	}
	
    for (int i = 0; i < idx; i++){
        for (int j = 0; j < idx; j++){
            if (d[i][j] == 1 << 25) return (!printf("-1\n"));
        }
    }	
	lint res = 0;
	
	for (int i = 0; i < n; i++){
		int from = i, to = (i + 1) % n;
		int fl = belong[from], tl = belong[to];
		int c = chi[from], p = par[to];
		if (fl == tl && dist[from] < dist[to]){
			res += dist[to] - dist[from];
		}
		else {
			res += (!~fl ? 0 : (len[fl] - dist[from])) + d[c][p] + dist[to];
		}
	}
	
	printf("%lld\n", res);
	
	return (0);
}