POJ-1679 The Unique MST（サブツリー、最小生成ツリーが一意かどうか判断）

19226 ワード

http://poj.org/problem?id=1679
Description
Given a connected undirected graph，tell if its minimum spanning tree is unique.
Definition 1（Spanning Tree）：Consder a connected、undirected graph G=(V，E).A spanning tree of G is a subgraphh of G，say T=(V'，E')、with the following properties:
1.V'=V.
2.T is connected and acyclic.
Definition 2（Minimm Spanning Tree）：Consder an edge-weighted、connected、undirected graph G=(V，E).The minimum spanning tree T=(V，E')of G is the spanning tree has the smas the smart the costits.s the costit。
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)、thenberginfollable.ingline。indicating that xi and yi are connected by an edge with weight=wi.For any two nodes，there ist one edge connecting them.
Output
For each input、if the MST is unique、print the total cost of it、or other wise prist the string'Not Unique！'
Sample Input

Sample Output

3
Not Unique!

件名:
n点mの辺に重さの辺がないことをあげて、最小の木が唯一かどうかを生成することを求めて、もしこの最小の生成樹は唯一だならば、最小の木の上の権利の和を出力して、唯一のはNot Uniqueを出力するのではありません！
考え方:
次の小さい木を求めて、最小の結果と同じではないです。

サブツリー:
最小生成ツリーの変化によって、「次の小さい」は変化が最小になることによって、ツリー上の1つの辺を生成するだけで実現され、この変化が最小になることが分かります。
素晴らしいブログを提供します。https://blog.csdn.net/qq_27437781/articale/detail/70821413

from:https://blog.csdn.net/u011721440/article/details/38735547
最小生成ツリーが一意かどうかを判断します。
1、図中の各辺に対して、他の辺をスキャンし、同じ値の辺があれば、その辺をマークする。
2、kruskyalまたはprimでMSTを求めます。
3、MSTにマークされたエッジがない場合、MSTは一意である。そうでなければ、MSTでマークのエッジを順次削除して、MSTを求めて、MSTの権利値と元のMSTの権利値が同じであれば、MSTは一意ではない。
from:https://blog.csdn.net/blue_skyrim/articale/detail/51338375
次の小さい木を生成するための求法は、エニュメレート・最小生成樹の各辺の一つを削除し、この二つの点に他の辺を見つけて、残りの辺は最小生成樹を形成する。

クァンビンのブログ：https://www.cnblogs.com/kuangbin/p/3147329.html
考え方:
最小生成ツリーを求める時、配列maxval[i][j]でMSTのiからjまでの最大辺権を表します。求め終わったら、直接エニュメレーションします。MSTの中にないすべての辺を、最大辺権を取り換えます。解答を更新します。注意点の番号は0から始まります。
原理:
最小生成ツリー上の隣接していない2点接続は必ず1つのリングになるので、これらの隣接していない点を列挙して彼らを接続させて、リングの中で最小生成ツリーの最大端に属するものを削除してもいいです。あるいは現在確定されている辺lowval[u]，dpの思想です。これは木の構造を保証するだけでなく、木の変化を最小にすることができます。これらの列挙の中で一番小さい結果は次の小さい生成ツリーです。

  1 #include 
  2 #include <string.h>
  3 #include 
  4 #include <string>
  5 #include 
  6 #include 
  7 #include 
  8 #include 
  9 #include 
 10 #include <set>
 11 #include 
 12 #include 
 13 const int INF=0x3f3f3f3f;
 14 typedef long long LL;
 15 const int mod=1e9+7;
 16 //const double PI=acos(-1);
 17 #define Bug cout< 18 const int maxn=110;
 19 using namespace std;
 20 
 21 int G[maxn][maxn];//     
 22 int vis[maxn];//             
 23 int pre[maxn];//       
 24 int lowval[maxn];//     
 25 int maxval[maxn][maxn];//maxval[i][j]          i j         
 26 int used[maxn][maxn];//                  
 27 int MST;//         
 28 
 29 int Prim(int n,int st)//n      ,st           
 30 {
 31     fill(lowval,lowval+n,INF);
 32     memset(maxval,0,sizeof(maxval));
 33     memset(pre,-1,sizeof(pre));
 34     memset(used,0,sizeof(used));
 35     memset(vis,0,sizeof(vis));
 36     int ans=0;
 37     lowval[st]=0;
 38     vis[st]=1;
 39     for(int i=0;i)
 40     {
 41         if(i!=st&&G[st][i]!=INF)
 42         {
 43             lowval[i]=min(lowval[i],G[st][i]);
 44             pre[i]=st;
 45         }
 46     }
 47     for(int k=0;k1;k++)
 48     {
 49         int MIN=INF;
 50         int t=-1;
 51         for(int i=0;i)
 52         {
 53             if(vis[i]==0&&lowval[i]<MIN)
 54             {
 55                 MIN=lowval[i];
 56                 t=i;
 57             }
 58         }
 59 //        if(MIN==INF)    return -1;
 60         ans+=MIN;
 61         vis[t]=1;
 62         used[t][pre[t]]=used[pre[t]][t]=1;//             
 63         for(int i=0;i)
 64         {
 65             if(vis[i]) 
 66                 maxval[t][i]=maxval[i][t]=max(maxval[i][pre[t]],lowval[t]);
 67             if(i!=t&&!vis[i]&&G[t][i]<lowval[i])
 68             {
 69                 pre[i]=t;
 70                 lowval[i]=G[t][i];
 71             }
 72         }
 73     }
 74     return ans;
 75 }
 76 
 77 int Judge(int n)
 78 {
 79     int MIN=INF;
 80     for(int i=0;i)
 81     {
 82         for(int j=i+1;j)
 83         {
 84             if(G[i][j]!=INF && !used[i][j])//          
 85                 MIN=min(MIN,MST-maxval[i][j]+G[i][j]);
 86         }
 87     }
 88     return MIN;
 89 }
 90 
 91 int main()
 92 {
 93     int T;
 94     scanf("%d",&T);
 95     while(T--)
 96     {
 97         int n,m;
 98         scanf("%d %d",&n,&m);
 99         memset(G,INF,sizeof(G));
100         for(int i=0;i)
101         {
102             int u,v,w;
103             scanf("%d %d %d",&u,&v,&w);
104             u--;v--;//    0   
105             G[u][v]=w;
106             G[v][u]=w;
107         }
108         MST=Prim(n,0);
109         if(MST==Judge(n))//                 
110             printf("Not Unique!
");
111         else
112             printf("%d
",MST);
113     }
114     return 0;
115 }

8-16桁の数字とアルファベットと特殊文字のパスワードにマッチする正規表現

数学の道（マシン学習実践ガイド）-テキストマイニングとNLP（3）