poj 1679 The Unique MST (次小生成树模板题)
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!
题目大意:
问最小生成树是否唯一。
次小生成树的模板题。
在普通的prim算法的基础上做一些变化。跑完后额外存储最小生成树的n-1条边used[i][j],每两个点间最长的边mdis[i][j]。具体见代码。
然后遍历所有不在最小生成树中的边。将这种边加进最小生成树中肯定会形成一个环。若该环中还有一条边与该边一样大。则最小生成树不唯一。
#include<cstdio>
#include<algorithm>
#include<cstring> using namespace std; const int maxn=;
const int maxm=;
const int inf=; int to[maxm+];
int w[maxm+];
int nex[maxm+];
int head[maxn+]; int lowc[maxn+];
int from[maxn+];
int mdis[maxn+][maxn+];
int vis[maxn+];
int used[maxn+][maxn+]; int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n,m;
scanf("%d%d",&n,&m);
memset(head,-,sizeof(head));
for(int i=,cnt=,x,y,z;i<m;i++)
{
scanf("%d%d%d",&x,&y,&z);
to[cnt]=y;w[cnt]=z;nex[cnt]=head[x];head[x]=cnt++;
to[cnt]=x;w[cnt]=z;nex[cnt]=head[y];head[y]=cnt++;
} int ans=;
for(int i=;i<=n;i++)
lowc[i]=inf;
memset(vis,,sizeof(vis));
memset(used,,sizeof(used));
for(int i=head[],x,y,z;i!=-;i=nex[i])
{
x=;y=to[i];z=w[i];
lowc[y]=z;
from[y]=x;
}
vis[]=;
for(int i=;i<=n;i++)
{
//更新思路:mdis->vis,used->lowc,from
int x,y=;
for(int i=;i<=n;i++)
if(!vis[i])
{
if(y==||lowc[i]<lowc[y])
y=i;
}
x=from[y];
ans+=lowc[y];
mdis[x][y]=mdis[y][x]=lowc[y];
for(int i=;i<=n;i++)
{
if(vis[i]&&i!=x)
mdis[i][y]=mdis[y][i]=max(mdis[i][x],lowc[y]);
}
vis[y]=;used[x][y]=used[y][x]=;
x=y;
for(int i=head[x],z;i!=-;i=nex[i])
{
y=to[i];z=w[i];
if(lowc[y]>z)
{
lowc[y]=z;
from[y]=x;
}
}
} bool flag=true;
for(int i=;i<=n;i++)
{
for(int j=head[i];j!=-;j=nex[j])
{
int l=to[j];
if(!used[i][l]&&w[j]==mdis[i][l])
{
flag=false;
break;
}
}
if(!flag)
break;
} if(flag)
{
printf("%d\n",ans);
}
else
{
printf("Not Unique!\n");
}
}
return ;
}
最新文章
- memcache/memcached安装教程并应用Tinkphp3.2
- Android开发自学笔记—1.1(番外)AndroidStudio常用功能介绍
- 如何给ZenCart网站livezilla客服系统?
- Jmeter组件3. HTTP Cookie Manager
- [游戏学习23] MFC 画尺子
- CentOS 7 使用经验(更新中)
- C#和SQl 注入字符串的攻击 和 防止注入字符转的攻击
- (六)6.16 Neurons Networks linear decoders and its implements
- ASP.NET中IsPostBack属性研究
- Windows下的多线程
- BZOJ1609: [Usaco2008 Feb]Eating Together麻烦的聚餐
- Unity3D-深入剖析NGUI的游戏UI架构
- $_FILES详解
- php之str_replace具体解释
- R语言︱逻辑运算
- Django中Middleware中间件
- Java的内部类真的那么难以理解?
- Jenkins之定时构建
- 为什么要学习 Spring Boot?
- laravel+阿里大于实现发送验证码短信