The Unique MST
Time Limit: 1000MS
|
Memory Limit: 10000K
|
Total Submissions: 14582
|
Accepted: 5035
|
题目连接:http://poj.org/problem?id=1679
Description
Given a connected undirectedgraph, tell if its minimum spanning tree is unique.
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 thefollowing 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 thespanning tree that has the smallest total cost. The total cost of T means thesum of the weights on all the
edges in E'.
Input
The first line contains asingle integer t (1 <= t <= 20), the number of test cases. Each caserepresents a graph. It begins with a line containing two integers n and m (1<= n <= 100), the number of nodes and edges. Each of the following m linescontains
a triple (xi, yi, wi), indicating that xi and yi are connected by anedge with weight = wi. For any two nodes, there is at most one edge connectingthem.
Output
For each input, if the MST isunique, print the total cost of it, or otherwise print the string 'NotUnique!'.
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!
Source
POJMonthly--2004.06.27 srbga@POJ
题意:
判断最小生成树是否唯一,即是否有两个一模一样的最小生成树的值
解题思路:
这是一个求次小生成树的题目,可以依照求最小生成树的方法来求,但是求最小生成树的时候要保存该生成树的每一条边,在删除某一条边后在求最小生成树,比较是否相等
代码:
//求次小生成树
/*
首先求出原图最小生成树,记录权值之和为MinST。枚举添加每条不在最小生成树上的边(u,v),
加上以后一定会形成一个环。找到环上权值第二大的边(即除了(u,v)以外的权值最大的边),把
它删掉,计算当前生成树的权值之和。取所有枚举修改的生成树权值之和的最小值,就是次小生
成树。
*/
#include <iostream>
#include<cstdio>
#include<cstring>
#define MAX 200
#define VALUE 0xfffffff
using namespace std;
//存储最小生成树的边
struct des
{
int w;
int s;
int e;
};
int g[MAX][MAX];
int visited[MAX];
des minCost[MAX];
int v,e;
//求最小生成树
int prim()
{
int i;
for(i=0;i<=v;i++)
{
minCost[i].w=VALUE;
minCost[i].s=0;
minCost[i].e=0;
visited[i]=0;
}
minCost[1].w=0;
int res=0;
while(true)
{
int t=-1;
int a=0;
for(i=1;i<=v;i++)
{
if(visited[i]==0 && (t==-1 || minCost[i].w<minCost[t].w))
{
t=i;
minCost[t].e=minCost[i].e;
minCost[t].s=minCost[i].s;
minCost[t].w=minCost[i].w;
}
}
//每条边都遍历完
if(t==-1)
break;
//访问t点
visited[t]=1;
if(minCost[t].w==VALUE)
return -1;//不连通
res+=minCost[t].w;
//printf("%d\t",minCost[t].w);
for(i=1;i<=v;i++)
{
if(minCost[i].w>g[t][i] && g[t][i]!=0)
{
minCost[i].w=g[t][i];
minCost[i].s=t;
minCost[i].e=i;
}
}
}
return res;
}
void secondShortPath()
{
int path1=prim();//最短路径
if(path1==-1 || path1==0)
{
printf("0\n");
return ;
}
int i;
//枚举最小生成树的每一条边,
des tempCost[MAX];
//保存原来的值
for(i=0;i<=v;i++)
{
tempCost[i]=minCost[i];
}
for(i=1;i<=v;i++)
{
if(tempCost[i].s!=0 && tempCost[i].e!=0)
{
//假设最小生成树中某一条边没了,再求最小生成树,看是否还相等
g[tempCost[i].s][tempCost[i].e]=0;//minCost值发生了改变
g[tempCost[i].e][tempCost[i].s]=0;
int path2=prim();
if(path2==-1)//不连通
continue;
if(path1==path2)//最小生成树不唯一
{
printf("Not Unique!\n");
return ;
}
//还原之前删除的边
g[tempCost[i].s][tempCost[i].e]=tempCost[i].w;
g[tempCost[i].e][tempCost[i].s]=tempCost[i].w;
}
}
printf("%d\n",path1);
}
int main()
{
int ts;
scanf("%d",&ts);
while(ts--)
{
memset(g,0,sizeof(g));
scanf("%d%d",&v,&e);
int i;
int start,end,weight;
for(i=0;i<e;i++)
{
scanf("%d%d%d",&start,&end,&weight);
g[start][end]=weight;
g[end][start]=weight;
}
secondShortPath();
}
return 0;
}
分享到:
相关推荐
先利用prim算法求出最小生成树,然后通过往MST里加边来判断新生成的最小生成树是否具有最小的权值,POJ上The Unique MST(1679)题是要求判断最小生成树是否唯一,此题其实根本不用这样做,但是为了练习球次小生成树...
2遍dp poj_3613解题报告 poj_3613解题报告
poj题目2775文件子目录源代码,递归经典题目,
poj典型题目解题思路详解 包含源代码和解题时应注意的问题及题目陷阱设计分析
poj 1699的代码和方法说明,个人原创
C_(POJ_1854)(分治).cpp
poj上第1990题目源码,用到了2个树状数组,这题数据结构是关键,想到了题目就很简单了
D_(POJ_1723)(思维)(sort).cpp
原理为:以数链思想,移动数组中的内容 使数组在没有扩充情况下,达成移动的效果 当然,有更简单的,大牛不要笑哦
D_(POJ_1723)(思维)(第k大数).cpp
O(nlogn)凸包问题 poj2187
POJ 3131 双向BFS解立体八数码问题
poj两道题的c++实现。已经测试过可以通过oj
POJ题目及算法,包括动态规划、深搜广搜等算法。含相关注释。
这是北大在线测试的第1002题,方便记忆的电话号码的解题例程,题目中有一个列表,记录着许多方便记忆的电话号码。不同的方便记忆的电话号码可能对应相同的标准号码,这个程序的任务就是找到它们
问题:求平面上多个矩形的总面积。 算法:线段树(经典的线段树题目)
poj 3310 的代码和方法说明,个人原创
http://poj.grids.cn/problem?id=2774 POJ 2774 木棒加工 木材厂有一些原木,现在想把这些木头切割成一些长度相同的小段木头,需要得到的小段的数目是给定了。当然,我们希望得到的小段越长越好,你的任务是计算能够...
看了测试用例后,大家估计已经明白题目的意思了吧!题目很简单,但是就是很烦。 开始直接是没思路,不知道怎么模拟,但是想了带该半个小时,就搞定了。就是把每个数存到数组里面。
POJ上面题目的解题报告。涵盖挺多的。可作参考。代码都正确。ACM新手入门必下~~ 加油...