第一次寫次小生成樹，沒(méi)想到
思想就是：求一次最小生成樹，記錄所用到的邊，然后不用所有第一次用到的邊嘗試構(gòu)成構(gòu)成最小生成樹。
用Kruskal先求最小生成樹，結(jié)果即為min，把所用到的邊記錄下來(lái)（這里是記錄的對(duì)應(yīng)的下表），然后枚舉這些邊，
每次去掉一個(gè)邊求一次最小生成樹，結(jié)果為tmin，如果能夠成最小生成樹并且tmin==min，則說(shuō)明最小生成樹不唯一
#include<iostream> //poj 1679
#include<cstdio>
#include<algorithm>
using namespace std;
const int MAX = 101;
int n, m;
struct edge
{
int x;
int y;
int len;
}E[MAX*MAX];
int fa[MAX];
int indexEdge[MAX];
int index;
bool cmp(const edge &a, const edge &b)
{
return a.len < b.len;
}
int find(int x)
{
if(fa[x] == x)return x;
return fa[x] = find(fa[x]);
}
int Kruskal(int location) //不用location位置的邊
{
int ans = 0;
int tx, ty;
int cnt = 0;
if (location == -1)index = 0;//location == -1 第一次求最小生成樹，indexEdge[index]紀(jì)錄第index用到的邊的下標(biāo)
for(int k = 1; k <= n; k ++)fa[k] = k;
for(int i = 0; i < m; i ++)
{
if(i == location)continue;
tx = find(E[i].x);
ty = find(E[i].y);
if(tx != ty)
{
fa[tx] = ty;
ans += E[i].len;
cnt ++;
if(location == -1)//第一次最小生成樹的時(shí)候把location置為-1
{
indexEdge[index] = i;
index ++;
}
if(cnt == n - 1)break;
}
}
if(cnt == n - 1)return ans;
return -1;
}
int main()
{
int t, i;
scanf("%d",&t);
while(t --)
{
memset(E, 0, sizeof E);
memset(indexEdge, 0, sizeof indexEdge);
scanf("%d %d",&n, &m);
for(i = 0; i < m; i ++)
scanf("%d %d %d",&E[i].x, & E[i].y , & E[i].len);
sort(E, E + m, cmp);
int min = Kruskal(-1);
int tmin = (1<<20), temp;
//cout << index << endl;
for(i = 0; i < index; i ++)
{
//cout <<i <<' '<< indexEdge[i]<< endl;
temp = Kruskal(indexEdge[i]);
if(temp != -1 && temp < tmin)
tmin = temp;
}
if(tmin == min)
printf("Not Unique!\n");
else printf("%d\n",min);
}
return 0;
}