USACO 4.1 펜스 루프 의 가장 작은 고리

http://ace.delos.com/usacoprob2?a=b8o6p9MDlbr&S=fence6
제목: 그림 의 가장 작은 고 리 를 구 하 는 N 개의 점 이 있 는 그림 을 드 리 겠 습 니 다.N<=100
사고방식: 알고리즘 은 매우 간단 하 다. 바로 O (N ^ 3) 의 Floyd 의 가장 작은 고리 이다.이 문제 가 징 그 러 운 것 은 당신 에 게 그림 의 정 보 를 주 는 것 입 니 다. 그림 속 의 일부 변 과 변 사이 에 붙 어 있 는 정보 입 니 다. 그러면 그림 을 만 드 는 데 번 거 로 움 을 가 져 왔 습 니 다.좋 은 방법 을 생각 하지 못 했 습 니 다. 비교적 어 리 석 은 방법 을 사 용 했 습 니 다. 먼저 각 라인 을 하나의 독립 된 변 (두 개의 독립 된 정점 이 있 습 니 다) 으로 본 다음 에 각 변 의 두 개의 정점 을 차례대로 매 거 했 습 니 다. 그 와 교점 이 있 는 변 의 정점 을 사용 하고 조사 하여 합 친 다음 에 수집 해 야 할 뿌리 가 이런 정점 의 대표 적 인 결점 으로 할 때 다른 정점 은 고려 하지 않 아 도 됩 니 다.이 대표 원 만 생각하면 돼 요. 마지막 으로 그림 을 만 들 고 플 로 이 드 를 한 번 뛰 면 돼 요.복잡 도: O (N ^ 3). 
코드:

/*
ID : chris
LANG :C++
TASK : fence6
*/
#include<stdio.h>
#include<string.h>
const int inf = (1<<28) ;
int N ;
int data[105][2][10] ;
int len[105] ,cnt;
int maze[210][210] ;
int p[210] ;
int num[110] ;

int find(int a){
	if( p[a] != a ){
		p[a] = find( p[a] ) ;
	}
	return p[a] ;
}

void Union(int a, int b){
	int fa = find(a) ;
	int fb = find(b) ;
	if(fa > fb){
		p[fa] = fb ;
	}
	else if(fa < fb){
		p[fb] = fa ;
	}
}
int dis[210][210] ;
int map[210][210] ;
int M ;
bool vis[210] ;

void solve(){
	for(int i=1;i<=2*N;i++){
		for(int j=1;j<=2*N;j++){
			if(i == j)	dis[i][j] = 0 ;
			else		dis[i][j] = inf ;
		}
	}	
	for(int i=1;i<=2*N;i++){
		for(int j=1;j<=2*N;j++){
			int a = find(i) ;
			int b = find(j) ;
			dis[a][b] = dis[b][a] = maze[a][b] ;
		}
	}
	int _min = inf ;
	for(int k=1;k<=2*N;k++){
		for(int i=1;i<k;i++){
			for(int j=i+1;j<k;j++){
				if( _min > dis[i][j] + maze[k][i] + maze[k][j] ){
					_min = dis[i][j] + maze[k][i] + maze[k][j] ;
				}
			}
		}
		for(int i=1;i<=2*N;i++){
			for(int j=1;j<=2*N;j++){
				if(dis[i][j] > dis[i][k] + dis[k][j] ){
					dis[i][j] = dis[i][k] + dis[k][j] ;
				}
			}
		}	
	}
	printf("%d
",_min);
}
int main(){
	freopen("fence6.in","r",stdin);
	freopen("fence6.out","w",stdout);
	int a ,b,c,d ;
	while(scanf("%d",&N) == 1){
		for(int i=1;i<=2*N;i++){
			for(int j=0;j<210;j++){
				if(i == j)	maze[i][j] = 0 ;
				else		maze[i][j] = inf ;
			}
			p[i] = i ;
		}
		for(int i=0;i<N;i++){
			scanf("%d",&a);
			num[i] = a ;
			scanf("%d %d %d",&len[a],&c,&d);
			data[a][0][0] = c ;
			data[a][1][0] = d ;
			for(int j=1;j<=c;j++){
				scanf("%d",&data[a][0][j]);
			}
			for(int j=1;j<=d;j++){
				scanf("%d",&data[a][1][j]);
			}
		}
		
		for(int i=0;i<N;i++){
			a = num[i] ;
			for(int j=1;j<=data[a][0][0];j++){
				int v = data[a][0][j] ;
				int ans = -1;
				for(int k=1;k<=data[v][0][0];k++){
					if(a == data[v][0][k]){
						ans = 2 * v - 1;	break ;
					}
				}	
				if(ans == -1){
					ans = 2 * v ;	
				}
				Union(2*a-1,ans);
			}
			for(int j=1;j<=data[a][1][0];j++){
				int v = data[a][1][j] ;
				int ans = -1 ;
				for(int k=1;k<=data[v][0][0];k++){
					if(a == data[v][0][k]){
						ans = 2 * v - 1;	break ;
					}
				}
				if(ans == -1)	ans = 2 * v  ;
				Union(2*a,ans);
			}
		}
		for(int i=0;i<N;i++){
			c = num[i] ;	
			int a = find(2*c-1) ;
			int b = find(2*c) ;
			maze[a][b] = maze[b][a] = len[c] ;
		}
		
		solve() ;
	}
	return 0 ;
}