【BZOJ】3397:[Usaco 2009 Feb]Surround the Islands環島垣根(tarjan)

http://www.lydsy.com/JudgeOnline/problem.php?id=3397
明らかにtarjanは点を縮めて、それから各sccを列挙して、それから他の島に費用の最小の辺を続けて、それから最小のものを計算します

#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
#define rep(i, n) for(int i=0; i<(n); ++i)
#define for1(i,a,n) for(int i=(a);i<=(n);++i)
#define for2(i,a,n) for(int i=(a);i<(n);++i)
#define for3(i,a,n) for(int i=(a);i>=(n);--i)
#define for4(i,a,n) for(int i=(a);i>(n);--i)
#define CC(i,a) memset(i,a,sizeof(i))
#define read(a) a=getint()
#define print(a) printf("%d", a)
#define dbg(x) cout << #x << " = " << x << endl
#define printarr2(a, b, c) for1(i, 1, b) { for1(j, 1, c) cout << a[i][j]; cout << endl; }
#define printarr1(a, b) for1(i, 1, b) cout << a[i]; cout << endl
inline const int getint() { int r=0, k=1; char c=getchar(); for(; c<'0'||c>'9'; c=getchar()) if(c=='-') k=-1; for(; c>='0'&&c<='9'; c=getchar()) r=r*10+c-'0'; return k*r; }
inline const int max(const int &a, const int &b) { return a>b?a:b; }
inline const int min(const int &a, const int &b) { return a<b?a:b; }

const int N=505;
int ihead[N], mn[N][N], cnt, FF[N], LL[N], vis[N], tot, q[N], top, p[N], scc, n;
struct ED { int to, next; }e[N*N<<1];
void add(int u, int v) { 
	e[++cnt].next=ihead[u]; ihead[u]=cnt; e[cnt].to=v; 
	e[++cnt].next=ihead[v]; ihead[v]=cnt; e[cnt].to=u; 
}
void tarjan(int u) {
	int v;
	FF[u]=LL[u]=++tot; q[++top]=u; vis[u]=1;
	for(int i=ihead[u]; i; i=e[i].next) {
		v=e[i].to;
		if(!FF[v]) tarjan(v), LL[u]=min(LL[u], LL[v]);
		else if(vis[v]) LL[u]=min(LL[u], FF[v]);
	}
	if(FF[u]==LL[u]) {
		++scc;
		do {
			v=q[top--];
			p[v]=scc;
			vis[v]=0;
		} while(u!=v);
	}
}

int main() {
	read(n);
	for1(i, 1, n) {
		int u=getint(), v=getint();
		add(u, v);
	}
	for1(i, 1, n) if(!FF[i]) tarjan(i);
	CC(mn, 0x3f);
	for1(i, 1, n) for1(j, 1, n) {
		int t=getint(), u=p[i], v=p[j];
		if(u!=v && mn[u][v]>t) mn[u][v]=t;
	}
	int ans=~0u>>1;
	for1(i, 1, scc) {
		int t=0;
		for1(j, 1, scc) if(i!=j)
			t+=mn[i][j];
		ans=min(t, ans);
	}
	print(ans<<1);
	return 0;
}

 
 
 
 
Description
ジョンはカリブ海で不動産を買って、ここのいくつかの島で乳牛を飼うつもりです.だから、彼はすべての島に垣根を囲みます.すべての島は多角形です.彼は島の境界に沿って一つの方向に歩いて、時には船で別の島に行きます.彼は任意の多角形の頂点から垣根を修理する仕事を始めることができます.いずれかの到着した頂点で、彼は船で別の島のある頂点に行くことができますが、その島の垣根を修理したら、彼はすぐにこの出発した島の頂点に戻らなければなりません.任意の2つの頂点の間には汚い線があり、各航路には一定の費用が必要です.ジョンに最小限の費用を計算して、すべての垣根を修理させてください.
Input
1行目にN(3≦N≦500)を入力、全ての島の多角形の個数を表す.
次に、N行毎に2つの整数V 1とV 2(1≦V 1≦N;1≦V 2≦N)を入力、島を構成する線分の2つの端点を表す.次に、N行N列の行列を入力し、2つの頂点間の航行に必要な費用を表す.
Output
 
1つの整数、最低費用.
Sample Input
12
1 7
7 3
3 6
6 10
10 1
2 12
2 9
8 9
8 12
11 5
5 4
11 4
0 15 9 20 25 8 10 13 17 8 8 7
15 0 12 12 10 10 8 15 15 8 8 9
9 12 0 25 20 18 16 14 13 7 12 12
20 12 25 0 8 13 14 15 15 10 10 10
25 10 20 8 0 16 20 18 17 18 9 11
8 10 18 13 16 0 10 9 11 10 8 12
10 8 16 14 20 10 0 18 20 6 16 15
13 15 14 15 18 9 18 0 5 12 12 13
17 15 13 15 17 11 20 5 0 22 8 10
8 8 7 10 18 10 6 12 22 0 11 12
8 8 12 10 9 8 16 12 8 11 0 9
7 9 12 10 11 12 15 13 10 12 9 0
Sample Output
30
HINT

Source
Silver