大家好，又见面了，我是全栈君。
| Time Limit: 1000MS | Memory Limit: 10000K | |
| Total Submissions: 19941 | Accepted: 6999 |
Description
Definition 1 (Spanning Tree): Consider a connected, undirected graph G = (V, E). A spanning tree of G is a subgraph of G, say T = (V’, E’), with the following properties:
1. V’ = V.
2. T is connected and acyclic.
Definition 2 (Minimum Spanning Tree): Consider an edge-weighted, connected, undirected graph G = (V, E). The minimum spanning tree T = (V, E’) of G is the spanning tree that has the smallest total cost. The total cost of T means the sum of the weights on all the edges in E’.
Input
Output
Sample Input
2 3 3 1 2 1 2 3 2 3 1 3 4 4 1 2 2 2 3 2 3 4 2 4 1 2
Sample Output
3 Not Unique!
这道题就是要你推断是否为唯一的最小生成树。。
这也是我第一道次小生成树的题。。那个PDF资料真是太好了。。我用的是Kruskal。。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<cmath>
using namespace std;
const int max1 = 105;
const int max2 = 10005;
struct node
{
int u, v, w;//边的顶点以及权值
int r;//用于记录边的序号
int used;//用于记录边是否被使用过
}edge[max2];//边的数组
int parent[max1];//顶点i所在集合相应树中的根节点
int n, m;//顶点数，边的个数
int cas;
void start()//初始化
{
for(int i=1; i<=n; i++)
parent[i] = i;
}
int find (int x)//查找并返回节点x所属集合的根节点
{
return parent[x] == x ? x : parent[x] = find ( parent[x] );}bool cmp ( node a, node b )//按权值从小到大排序{ return a.w < b.w;}int Kruskal()//第一次求最小生成树{ sort( edge+1, edge+m+1, cmp ); int ans = 0; for(int i=1; i<=m; i++) { int e = edge[i].r; int x = find( edge[i].u ); int y = find( edge[i].v ); if( x!=y ) { parent[y] = x; ans += edge[i].w; edge[e].used = 1; } } return ans;}int Kruskal_again(int tt)//求次小生成树{ sort( edge+1, edge+m+1, cmp ); int ans = 0; for(int i=1; i<=m; i++) { if( tt==edge[i].r ) continue; int x = find( edge[i].u ); int y = find( edge[i].v ); if( x!=y ) { parent[y] = x; ans += edge[i].w; } } return ans;}bool judge()//推断是否能就得最小生成树，即看是否有孤立的点{ for(int i=1; i<=n; i++) if( find(i) != find(1) ) return false; return true;}int main(){ scanf("%d", &cas); while( cas-- ) { scanf("%d%d", &n, &m); start(); for(int i=1; i<=m; i++) { scanf("%d%d%d", &edge[i].u, &edge[i].v, &edge[i].w); edge[i].used = 0; edge[i].r = i; } int flag = 0; int ans1 = Kruskal(); for(int i=1; i<=m; i++)//一一枚举求最小生成树。。 { if( !edge[i].used ) continue; start(); int ans2 = Kruskal_again(i);//求除去此边的最小生成树 if( ans1 == ans2 && judge() ) { flag = 1;//标记结论 break; } } if( flag ) printf("Not Unique!\n"); else printf("%d\n", ans1); } return 0;}
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/115989.html原文链接：https://javaforall.net
