判断生成树的唯一性，唯一则输出权值，不唯一输出Not Unique

次小生成树权值是否等于最小生成树的

一种容易想到的方法是枚举删除最小生成树上的边，再求最小生成树。用kruskal这种算法的复杂度为O(n*elog2e)，当图比较稠密时，复杂度接近O(n^3)。

但有一种更简单的方法：先求最小生成树T，枚举添加不在T中的边，则添加后一定会形成环。找到环上边值第二大的边(即环中属于T中的最大边，新添加进去的肯定最大，毕竟T是最小生成树，T之外的边最大)，把它删掉，计算当前生成树的权值，取所有枚举修改的生成树的最小值，即为次小生成树。

    这种方法在实现时有更简单的方法：首先求最小生成树T，然后从每个结点u遍历最小生成树T，用一个二维数组max[u][v]记录结点u到结点v的路劲上（不是指U到V节点权值是MAX[U][V]，而是U到V路径上（在最小生成树上）最大权值边是max[u][v]）边的最大值(即最大边的值)。然后枚举不在T中的边(u,v)，计算T- max[u][v] + w(u,v)的最小值，即为次小生成树的权值。显然，这种方法的时间复杂度为O(n^2 + e)。

可见，第二种算法将原来的时间复杂度O(n^3)提高到了O(n^2)。

#include <iostream>

#include <algorithm>

#include <queue>

const int INF = 0x7fffffff;

const int MAX = 10001;

int n,m;

int num;

int p[MAX];

int max[101][101];

struct Edge //原始图

{

int from;

int to;

int w;

bool flag;

}e[MAX];

struct Tree //最小生成树

{

int to;

int w;

int next;

}tree[202];

int index[101];

struct Node //生成树的结点

{

int seq; //结点编号

int max; //从某个点到它的路径中的最大边的长度

};

bool cmp(const Edge &a, const Edge &b)

{

return a.w < b.w;

}

void makeSet()

{

for(int i = 0; i <= n; i++)

{

p[i] = i;

}

}

int findSet(int x)

{

if(x != p[x])

p[x] = findSet(p[x]);

return p[x];

}

void addEdge(int from, int to, int w)

{

tree[num].to = to;

tree[num].w = w;

tree[num].next = index[from];

index[from] = num++;

}

int kruscal()

{

int i,j;

int x, y;

int edgeNum = 0;

int result = 0;

makeSet();

std::sort(e,e+m,cmp);

for(i = 0; i < m; i++)

{

x = findSet(e[i].from);

y = findSet(e[i].to);

if(x != y)

{

edgeNum++;

addEdge(e[i].from,e[i].to,e[i].w);

addEdge(e[i].to,e[i].from,e[i].w);

e[i].flag = true;

p[x] = y;

result += e[i].w;

}

}

return edgeNum == n-1 ? result : -1;

}

void bfs(int p)

{

int i,j;

bool used[101];

memset(used,0,sizeof(used));

std::queue<Node> que;

Node now,adj;

now.max = 0;

now.seq = p;

que.push(now);

used[p] = true;

while(!que.empty())

{

Node q = que.front();

que.pop();

for(i = index[q.seq]; i != -1; i = tree[i].next)//在最小生成树上找

{

adj.seq = tree[i].to;

adj.max = tree[i].w;

if(!used[adj.seq])

{

if(q.max > adj.max)

adj.max = q.max;

max[p][adj.seq] = adj.max;

used[adj.seq] = true;

que.push(adj);

}

}

}

}

void second_MST()

{

int i,j;

int mst = kruscal();

for(i = 1; i <= n; i++)

bfs(i);

int smst = INF;

for(i = 0; i < m; i++)

{

if(!e[i].flag)

{

if(mst + e[i].w - max[e[i].from][e[i].to] < smst)

smst = mst + e[i].w - max[e[i].from][e[i].to];

/*

这里，遍历所有不在最小生成树的边。

如果它起点在最小生成树上，而另一个端点不再最小生成树上，那么max[e[i].from][e[i].to] =0，则mst + e[i].w - max[e[i].from][e[i].to] 得到的肯定是偏大的值。

如果他两个端点都不在生成树上，那么同样max[e[i].from][e[i].to] =0。

只有两个端点U,V都在生成树上，且边不属于最小生成树的边，他们的max[e[i].from][e[i].to]不等于0，才有可能mst + e[i].w - max[e[i].from][e[i].to] 最小。对于这种情况，加上之后，树就变成图了，UV之间存在两条路径相连，因此要减去UV上原先在最小生成树的边，从这其中，删除最大的那条

*/

}

}

if(smst == mst)

printf("Not Unique!\n");

else

printf("%d\n",mst);

}

int main()

{

int i,j;

int cases;

int a,b,w;

scanf("%d",&cases);

while(cases--)

{

scanf("%d %d",&n,&m);

for(i = 0; i < m; i++)

{

scanf("%d %d %d",&e[i].from,&e[i].to,&e[i].w);

e[i].flag = false;

}

num = 0;

memset(index,-1,sizeof(index));

second_MST();

}

return 0;

}

mst1679