HDU 원활 공사 & & 원활 공사 (차 트 법)

 
   

     1 0 2 998 
    
 
     
 
      Hint 
     
Hint 
    
 
      Huge input, scanf is recommended. 
   
 
   
 
    
#include
using namespace std;
const int maxn=1010;
int s[maxn];
int find(int x)
{
	if(s[x]==-1)	return x;
	return s[x]=find(s[x]);	
}
void join(int x,int y)
{
	int fx=find(x);
	int fy=find(y);
	if(fx!=fy) s[fx]=fy; 
}
int main()
{
	int n,m,a,b;
	while(scanf("%d",&n),n)
	{
		scanf("%d",&m);
		for(int i=1;i<=n;i++) s[i]=-1;
		for(int i=1;i<=m;i++)
		{
			scanf("%d %d",&a,&b);	
			join(a,b);
		}
		int sum=0;
		for(int i=1;i<=n;i++)
			if(s[i]==-1)	sum++;
		printf("%d
",sum-1);
	}
	return 0;
}
  
아니면 원활 한 공사?
Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 48610    Accepted Submission(s): 22164 
Problem Description 
모 성에 서 마을 의 교통 상황 을 조사 하여 얻 은 통계표 에는 임의의 두 마을 간 의 거리 가 열거 되 어 있다.성 정부의 '원활 한 공사' 목 표 는 성 전체의 어느 두 마을 간 에 도 도로 교통 을 실현 할 수 있 도록 하 는 것 이다.가장 작은 도로 의 총 길 이 를 계산 해 주세요.
  
Input 
테스트 입력 은 약간의 테스트 용례 를 포함한다.각 테스트 용례 의 첫 번 째 줄 은 마을 수 N (< 100) 을 드 립 니 다.이 어 N (N - 1) / 2 줄 은 마을 간 의 거리 에 대응 하고 각 줄 은 두 마을 의 번호 와 이 두 마을 간 의 거 리 를 나타 낸다.간단하게 말하자면, 마을 은 1 부터 N 까지 번 호 를 매 긴 다.
N 이 0 일 때 입력 이 끝나 면 이 용례 는 처리 되 지 않 습 니 다.
  
Output 
각 테스트 사례 에 대해 서 는 1 줄 에서 가장 작은 도로 총 길 이 를 출력 한다.
  
Sample Input 
 
     

       3 1 2 1 1 3 2 2 3 4 4 1 2 1 1 3 4 1 4 1 2 3 3 2 4 2 3 4 5 0 
     
 
    
 
    

        
    
 
    
 
    

      Sample Output 
    
 
    
 
     
 
     

       3 5 
      
 
       
 
        Hint 
       
Hint 
      
 
        Huge input, scanf is recommended. 
     
 
    
 
    
#include
#include
using namespace std;
const int maxn=115;
int per[maxn],n,t;
struct node
{
	int x;
	int y;
	int dis;
}s[5000];
void init()
{
	for(int i=1;i<=n;i++)
		per[i]=i;
}
int find(int t)
{
	if(per[t]==t)
	return t;
	return per[t]=find(per[t]);
}
int cmp(node x,node y)
{
	return x.disfy)
		{
			per[fx]=fy;
		} 
		else
		{
			per[fy]=fx;
		}
	}
}
int main()
{
	while(scanf("%d",&n),n)
	{
		t=n*(n-1)/2;
		for(int i=0;i