POJ - 1679 The Unique MST(次小生成树)

The Unique MST

Time Limit: 1000MS   Memory Limit: 10000K
Total Submissions: 35193   Accepted: 12860

Description

Given a connected undirected graph, 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 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

The first line contains a single integer t (1 <= t <= 20), the number of test cases. Each case represents 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 lines contains a triple (xi, yi, wi), indicating that xi and yi are connected by an edge with weight = wi. For any two nodes, there is at most one edge connecting them.

Output

For each input, if the MST is unique, print the total cost of it, or otherwise print the string 'Not Unique!'.

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

POJ Monthly--2004.06.27 srbga@POJ

 

          大体意思就是建一个生成树,让其中一个边消耗为0后,求(边两边的城市人口数量总和)/ 生成树总消耗       的最大值;

          这样的话,我们就可以先建出最小生成树,然后枚举每一个边,假如这条边在最小生成树中用到了,那么生成树的最小消耗就是mst-这条边的消耗,如果没有被用到,那么和最小生成树放在一起之后就会形成一个环,那么最小消耗就是mst-这个环里的最长边;

 

         

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define inf 0x3f3f3f3f
double dis[1005];
double Max[1005][1005];
int pre[1005];
double Map[1005][1005];
bool use[1005][1005];
bool vis[1005];
int v[1005];
struct ***
{
	int x, y;
}loca[1005];
int n, m;
double cal(int x, int y)
{
	double len= sqrt((loca[x].x - loca[y].x)*(loca[x].x - loca[y].x) + (loca[x].y - loca[y].y)*(loca[x].y - loca[y].y));
	return len;
}
double prim()
{
	double ans = 0;
	memset(use, 0, sizeof(use));
	memset(vis, 0, sizeof(vis));
	memset(Max, 0, sizeof(Max));
	for (int s = 2; s <= n; s++)
	{
		dis[s] = Map[1][s];
		pre[s] = 1;
	}
	vis[1] = 1;
	pre[1] = 0;
	dis[1] = 0;
	for (int s = 2; s <= n; s++)
	{
		double min_ans = inf*1.0;
		int k;
		for (int s = 1; s <= n; s++)
		{
			if (!vis[s] && min_ans > dis[s])
			{
				min_ans = dis[s];
				k = s;
			}
		}
		if (min_ans == inf)return -1;
		ans += min_ans;
		vis[k] = 1;
		use[k][pre[k]] = use[pre[k]][k] = 1;
		for (int s = 1; s <= n; s++)
		{
			if (vis[s] && s != k)
				Max[s][k] = Max[k][s] = max(Max[s][pre[k]], dis[k]);
			if (!vis[s]&&dis[s]>Map[k][s])
			{
				dis[s] = Map[k][s];
				pre[s] = k;
			}
		}
	}
	return ans;
}
int main()
{
	int te;
	scanf("%d", &te);
	while (te--)
	{
		scanf("%d", &n);
		for (int s = 1; s <= n; s++)
			scanf("%d%d%d", &loca[s].x, &loca[s].y, &v[s]);
		for (int s = 1; s < n; s++)
			for (int w = s + 1; w <= n; w++)
				Map[s][w] = Map[w][s] = cal(s, w);
		double mst = prim();
		double ans = 0;
		for (int s = 1; s < n; s++)
		{
			for (int w = s + 1; w <= n; w++)
			{
			
				if (use[s][w])
				{
					ans = max(ans, (v[s] + v[w])*1.0 / (mst - Map[s][w]));
				}
				else
				{
					ans = max(ans, (v[s] + v[w])*1.0 / (mst - Max[s][w]));
				}
			}
		}
		printf("%.2lf\n", ans);
	}
}

 

全部评论

相关推荐

02-28 17:01
门头沟学院 C++
俊朗的铁猫希望被捞:兄弟如果只想搞钱的话,你这个简历最适合的其实是辅导机构做dai写啥的真的特别赚
点赞 评论 收藏
分享
03-15 00:45
已编辑
高德地图_go开发(实习员工)
问的很简单都秒了,但是面试官没开摄像头,疑似kpi,无后续。--------------------3/14更新,3/12通知给了口头offer,3/13发了意向书,已拒。一面(35min)(25/3/6)(无后续)&nbsp;&nbsp;&nbsp;&nbsp;1、自我介绍&nbsp;&nbsp;&nbsp;&nbsp;2、介绍一下你的那个Python相关项目(本科毕设,web系统+算法模型提供部分接口)&nbsp;&nbsp;&nbsp;&nbsp;3、Java面向对象有哪些特点呢?详细说一下。&nbsp;&nbsp;&nbsp;&nbsp;4、介绍一下hashmap;为什么要把链表转换为红黑树呢?红黑树查找的时间复杂度?1.7和1.8的区别。&nbsp;&nbsp;&nbsp;&nbsp;5、介绍一下concurrentHashmap。&nbsp;&nbsp;&nbsp;&nbsp;6、synchronized锁和Lock锁有什么区别?&nbsp;&nbsp;&nbsp;&nbsp;7、公平锁的一个底层是怎么实现的呢?&nbsp;&nbsp;&nbsp;&nbsp;8、线程池的核心参数、拒绝策略、提交一个任务执行流程?&nbsp;&nbsp;&nbsp;&nbsp;9、spring有哪些特点?(ioc/aop)&nbsp;&nbsp;&nbsp;&nbsp;10、spring中对于循环依赖是怎么解决的?&nbsp;&nbsp;&nbsp;&nbsp;11、MySQL和redis的区别?&nbsp;&nbsp;&nbsp;&nbsp;12、MySQL的索引结构是什么?&nbsp;&nbsp;&nbsp;&nbsp;13、MySQL的事务有哪些特性?怎么保证?&nbsp;&nbsp;&nbsp;&nbsp;14、MySQL的默认隔离级别?可重复读是怎么做到的呢?&nbsp;&nbsp;&nbsp;&nbsp;15、介绍一下MVCC和快照读readview。&nbsp;&nbsp;&nbsp;&nbsp;16、一般在什么场景下会使用redis?&nbsp;&nbsp;&nbsp;&nbsp;17、对于大量的请求,如果此时缓存中还没有写入数据怎么办?&nbsp;&nbsp;&nbsp;&nbsp;18、介绍一下redis实现的分布式锁。&nbsp;&nbsp;&nbsp;&nbsp;19、有用过es和mongo&nbsp;DB吗?(知道,没用过)&nbsp;&nbsp;&nbsp;&nbsp;20、消息中间件用过吗?说一下你的使用场景?&nbsp;&nbsp;&nbsp;&nbsp;21、一个场景,如果说有一个接口响应的比较慢,如果说让你排查,你会怎么去排查?(上下游接口、大key问题,只答了两,后面试官补充)&nbsp;&nbsp;&nbsp;&nbsp;无手撕,反问业务。
胖墩墩的查理在学c语言:哥们我是五号面的 流程差不多
查看21道真题和解析
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务