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!

The question : Ask if the minimum spanning tree is unique .

analysis : I want to make a small tree , Infer whether the second smallest spanning tree and the smallest spanning tree are equal .

The steps of finding the next smallest spanning tree :

(1) First use Prime Find the minimum spanning tree MST, stay Prime Using a matrix at the same time mmax[ ][ ] Recorded in the MST Connect two random points in u,v Right in the only path of

The weight of the side with the largest value . practice :Prime Is to add one node at a time t. Use this point to add MST The edge of is joined with its previous one MST Point of mmax Compare the values of .

(2) Enumerate edges other than the minimum spanning tree , And delete the edge with the largest weight on the ring where the edge is located .

(3) The tree with the smallest weight of all spanning trees obtained is the tree to be calculated .

The time complexity of the algorithm is O(n^2).

 #include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
#define maxn 111
#define inf 0x3f3f3f3f int map[maxn][maxn],mmax[maxn][maxn];//map Adjacency matrix is a graph ,mmax In the minimum spanning tree i To j The maximum edge weight of
bool used[maxn][maxn];// Determine whether the edge is added to the minimum spanning tree
int pre[maxn],dis[maxn];//pre be used for mmax The construction of , Put one in before loading MST The node of ,dis Used to build MST void init(int n)
{
for (int i=;i<=n;i++)// Graph initialization
{
for (int j=;j<=n;j++)
{
if (i==j)
{
map[i][j]=;
}
else
{
map[i][j]=inf;
}
}
}
} void read(int m)
{
int u,v,w;
for (int i=;i<m;i++)// Read in the picture
{
scanf("%d%d%d",&u,&v,&w);
map[u][v]=map[v][u]=w;
}
}
int prime(int n)// structure MST
{
int ans=;
bool vis[maxn];
memset(vis,false,sizeof(vis));
memset(used,false,sizeof(used));
memset(mmax,,sizeof(mmax));
for (int i=;i<=n;i++)
{
dis[i]=map[][i];
pre[i]=;//1 Point for the first to put in MST The point of , Let's set it as the leading node of all points
}
pre[]=;
dis[]=;
vis[]=true;
for (int i=;i<=n;i++)
{
int min_dis=inf,k;
for (int j=;j<=n;j++)
{
if (vis[j]==&&min_dis>dis[j])
{
min_dis=dis[j];
k=j;
}
}
if (min_dis==inf)// If there is no minimum spanning tree
{
return -;
}
ans+=min_dis;
vis[k]=true;
used[k][pre[k]]=used[pre[k]][k]=true;// Mark as put in MST The point of
for (int j=;j<=n;j++)
{
if (vis[j])
{
mmax[j][k]=mmax[k][j]=max(mmax[j][pre[k]],dis[k]);// The largest edge of the smallest spanning tree ring
}
if (!vis[j]&&dis[j]>map[k][j])
{
dis[j]=map[k][j];
pre[j]=k;
}
}
}
return ans;// The sum of the weights of the minimum spanning tree
}
int smst(int n,int min_ans)//min_ans Is the sum of the weights of the minimum spanning tree
{
int ans=inf;
for (int i=;i<=n;i++)// Enumerate the edges outside the minimum spanning tree
{
for (int j=i+;j<=n;j++)
{
if (map[i][j]!=inf&&!used[i][j])
{
ans=min(ans,min_ans+map[i][j]-mmax[i][j]);// This side is the second smallest MST A weight of MST Add the edge and subtract the maximum of the ring where the edge is located MST edge
}
}
}
if (ans==inf)
{
return -;
}
return ans;
}
void solve(int n)
{
int ans=prime(n);
if (ans==-)
{
puts("Not Unique!");
return;
}
if (smst(n,ans)==ans)// Minor MST The weight is equal to MST explain MST Is not the only
{
printf("Not Unique!\n");
}
else
{
printf("%d\n",ans);
}
}
int main()
{
int t,n,m; scanf("%d",&t);
while (t--)
{
scanf("%d%d",&n,&m);
init(n);
read(m);
solve(n);
} return ;
}

POJ_1679_The Unique MST( Secondary spanning tree ) More articles about

  1. POJ_1679_The Unique MST( Sub small spanning tree template )

    The Unique MST Time Limit: 1000MS   Memory Limit: 10000K Total Submissions: 23942   Accepted: 8492 D ...

  2. POJ1679 The Unique MST[ Secondary spanning tree ]

    The Unique MST Time Limit: 1000MS   Memory Limit: 10000K Total Submissions: 28673   Accepted: 10239 ...

  3. POJ 1679 The Unique MST ( Secondary spanning tree Determine whether the minimum spanning tree is unique )

    Topic link Description Given a connected undirected graph, tell if its minimum spanning tree is unique. De ...

  4. POJ1679 The Unique MST —— Secondary spanning tree

    Topic link :http://poj.org/problem?id=1679 The Unique MST Time Limit: 1000MS   Memory Limit: 10000K Total S ...

  5. POJ-1679 The Unique MST, Sub small spanning tree template problem

    The Unique MST Time Limit: 1000MS   Memory Limit: 10000K       Description Given a connected undirec ...

  6. POJ 1679 The Unique MST ( Secondary spanning tree )

    Topic link :http://poj.org/problem?id=1679 Yes t Group data , Here you are. n A little bit ,m side , Find out whether there is a minimum spanning tree with the same weight ( The weight of the second smallest spanning tree is equal to the smallest spanning tree ). First, find out the size of the minimum spanning tree , ...

  7. poj1679The Unique MST( Sub small spanning tree template )

    Sub small spanning tree template , Don't forget to judge that there is no minimum spanning tree #include <iostream> #include <cstdio> #include <cstring> ...

  8. POJ 1679 The Unique MST ( Secondary spanning tree kruskal Algorithm )

    The Unique MST The time limit : 10 Sec   Memory limit : 128 MB Submit : 25   solve : 10[ Submit ][ state ][ Discussion board ] Title Description Given a connected undirect ...

  9. poj 1679 The Unique MST ( Secondary spanning tree (sec_mst)【kruskal】)

    The Unique MST Time Limit: 1000MS   Memory Limit: 10000K Total Submissions: 35999   Accepted: 13145 ...

Random recommendation

  1. PHP Process control structure of

    1.break Use break Statement can exit the statement deeply embedded in the nested loop to a specified number of layers or directly exit to the outermost layer ,break It takes an optional numeric parameter to decide how many statements to jump out of .break You can jump out a few sentences .break You can jump a few times ...

  2. Spring MVC 3.0 In depth and detailed explanation of annotations

    The core principle 1.       User sends request to server .url:user.do 2.       The server receives the request . Find out Dispatchservlet Can handle . So call DispatchServlet. 3.  ...

  3. Python Study ( Two ) function Python, compile Python

    No matter what windos still Linux Once installed python, Configured environment variables , Enter... On the command line python This command will go into interactive mode . In this mode, you can do some simple python Code writing . Exit can be used exi ...

  4. docker And docker-compose Quick installation and easy use of

    This article will use DaoCloud Source in Ubuntu It's easy and fast to install docker And docker-compose And added through Dockerfile And docker-compose.yml Use n ...

  5. [JSON] First time to know JSON

    1: What is? json json yes , It's the syntax for storing and exchanging text information , Be similar to xml, But compared to xml smaller , faster , Easier to parse .   2:JSON Grammatical rules JSON in : The data is in key/velue Alignment , The data is separated by a check mark , Huakuo ...

  6. Python Common library Pilow

    Basic usage Static methods PIL.Image.open(fp, mode=’r’) Incoming file path (str), Return to one image object PIL.Image.alpha_composite(im1, im2) mixed ...

  7. maven Study diary ( 3、 ... and )------- Development environment construction (springmvc+hibernate4) Various maven Error summary

    1.maven code gbk Unmapped characters of The way to solve this problem : stay maven Declare the correct character set encoding in the compiler plug-in for —— The character set code used in compilation is the same as that used in code file !! After installing the system , General Chinese system ...

  8. dapper.net Reprint

    Dapper.NET—— Light weight ORM   Dapper.NET Use Contents of this article Dapper.NET Use 1. Why choose Dapper 2. With Dapper(4.0) For example . 2.1 Create several tables in the database . 2 ...

  9. CentOS Deploy Kubernetes1.13 colony -1( Use kubeadm install K8S)

    Reference resources :https://www.kubernetes.org.cn/4956.html 1. Get ready explain : The preparatory work needs to be performed on all the hosts in the cluster 1.1 The system configuration Before installation , We need to do the following preparations first . Three stations CentOS ...

  10. eclipse Download and install and test

    Download address :www.ecplise.org  After downloading, double-click install       After installation , First run eclipse Will pop up Workspace Launcher Dialog box , Requires setting up a workspace to store project documents .   ...