圖論測試題（一）第一題：longest

第一題：longest

烏托邦有n個城市，某些城市之間有公路連接。任意兩個城市都可以通過公路直接或者間接到達，并且任意兩個城市之間有且僅有一條路徑（What does this imply? A tree!）。

每條公路都有自己的長度，這些長度都是已經測量好的。

小修想從一個城市出發開車到另一個城市，并且她希望經過的公路總長度最長。請問她應該選擇哪兩個城市？這個最長的長度是多少？

?

Input format：

第一行n（n<=1000）。

以下n-1行每行三個整數a, b, c。表示城市a和城市b之間有公路直接連接，并且公路的長度是c(c<=10000)。

Output format：

僅一個數，即最長長度。

Sample：

Longest.in

5

1 2 2

2 3 1

2 4 3

1 5 4

?

Longest.out

9

?

說明：從城市4到城市5，經過的路徑是4-2-1-5，總長度是9。

?

裸的kruskal吧= =沒什么好說的，模板題

上代碼o(〃'▽'〃)o

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m;
struct node{int u;int v;int value;
}e[1001];
int father[1001];
bool cmp(node e1,node e2)
{return e1.value>e2.value;
}
void read()
{scanf("%d",&n);m=0;for(int i=1;i<n;i++){m++;int u,v,w;scanf("%d%d%d",&u,&v,&w);e[m].u=u;e[m].v=v;e[m].value=w;}sort(e+1,e+m+1,cmp);
}
int find(int x)
{if(father[x]==x) return x;else return father[x]=find(father[x]);
}
void merge(int x,int y)
{if(father[x]!=father[y]) father[father[x]]=father[y];
}
void kruskal()
{int sum=0;int ans=0;for(int i=1;i<=n;i++) father[i]=i;for(int i=1;i<=m;i++){if(find(e[i].u)!=find(e[i].v)){sum++;ans+=e[i].value;merge(e[i].u,e[i].v);}if(sum==n-2){printf("%d",ans);return ;}}printf("%d",-1);
}
int main()
{read();kruskal();return 0;
}

?