항 저 우 전기 1233(병 찰 집)

아니면 원활 한 공사?
Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 24069    Accepted Submission(s): 10695
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
 
#include #include using namespace std; #define MAXN 100 #define maxn MAXN*(MAXN-1)/2 int father[maxn]; int find(int x) {   return x==father[x]?x:father[x]=find(father[x]); } struct  in {    int start;    int end;    int value; };  
bool cmp(in a,in b) {   return a.value }
 int Union(int a,int b,int c)  {      int num=0;     int x=find(a);     int y=find(b);     printf("a=%d b=%d",x,y);     if(x!=y)        {       father[x]=y;       num=c;        }        return num;  }   int main() {     struct in s[maxn];     int N;     int a,b,c;     while(scanf("%d",&N),N)     {                 for(int i=1;i<=N*(N-1)/2;i++)          father[i]=i;         int sum=0;       for(int i=0;i       {       scanf("%d%d%d",&s[i].start,&s[i].end,&s[i].value);       }       sort(s,s+N*(N-1)/2,cmp);                for(int i=0;i           {             a=s[i].start;             b=s[i].end;             c=s[i].value;           // sum+= Union(a,b,c);                        int x=find(a);int y=find(b);           //  printf("a=%d b=%d",x,y);             if(x!=y)  {  father[x]=y;sum+=c;}                       }           printf("%d",sum);               }     return 0; }