青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

posts - 7,comments - 3,trackbacks - 0
The Unique MST
Time Limit: 1000MS
Memory Limit: 10000K
Total Submissions: 11943
Accepted: 4112

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@P

代碼:
#include <iostream>
#include 
<cstdio>
#include 
<cstring>
#include 
<algorithm>
using namespace std;

typedef 
struct
{
    
int x, y, w;
} edge;

edge s[
10010];
int top, t[10010];

bool cmp(edge a, edge b)
{
    
return a.w < b.w;
}

int kru(int n, int m, int x)
{
    
int i, j, a, b, tag[110], tem, sum, k;
    
for (i = 0; i < n; ++i)
    {
        tag[i] 
= i;
    }
    k 
= 1, j = 0, sum = 0;
    
while (k < n)
    {
        a 
= s[j].x - 1;
        b 
= s[j].y - 1;
        
if (j == x)
        {
            j
++;
            
continue;
        }
        
if (tag[a] != tag[b])
        {
            
if (x == -1)
            {
                t[top] 
= j;
                top
++;
            }
            tem 
= tag[b];
            k
++, sum += s[j].w;
            
for (i =  0; i < n; ++i)
            {
                
if (tag[i] == tem)
                {
                    tag[i] 
= tag[a];
                }
            }
        }
        j
++;
    }
    
return sum;
}
int main()
{
    
int p, n, m, cmin;
    scanf(
"%d"&p);
    
while (p--)
    {
        
int flag = 1;
        scanf(
"%d%d"&n, &m);
        
for (int i = 0; i < m; ++i)
            scanf(
"%d%d%d"&s[i].x, &s[i].y, &s[i].w);
        sort(s, s 
+ m, cmp);
        top 
= 0;
        
int min = kru(n, m, -1);
        
int key = top;
        
for (int l = 0; l < key; ++l)
        {
            cmin 
= kru(n, m, t[l]);
            
if (cmin == min)
            {
                flag 
= 0;
                printf(
"Not Unique!\n");
                
break;
            }
        }
        
if (flag)
        printf(
"%d\n", min);
    }
    
return 0;
}
posted on 2011-10-17 21:07 LLawliet 閱讀(265) 評論(0)  編輯 收藏 引用 所屬分類: 圖論
青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            亚洲免费一区二区| avtt综合网| 久久精品最新地址| 欧美一级午夜免费电影| 经典三级久久| 欧美jizz19hd性欧美| 欧美成人国产| 亚洲影视九九影院在线观看| 亚洲一级影院| 禁久久精品乱码| 亚洲精品1区2区| 国产精品99免视看9| 久久黄色小说| 欧美a级片网| 亚洲小说欧美另类社区| 欧美一区高清| 亚洲美洲欧洲综合国产一区| 亚洲视频一起| 在线成人小视频| 日韩午夜激情| 狠狠色狠狠色综合| 亚洲人成网站在线观看播放| 国产精品美女视频网站| 欧美96在线丨欧| 国产精品久久看| 欧美ab在线视频| 国产精品一区二区欧美| 欧美大片免费| 国产精品私房写真福利视频 | 国产欧美一区二区三区沐欲| 久久综合色婷婷| 欧美色图麻豆| 亚洲东热激情| 国产曰批免费观看久久久| 91久久久久| 在线观看日韩www视频免费| 夜夜嗨av色一区二区不卡| 精品88久久久久88久久久| 一区二区三区鲁丝不卡| 亚洲国产另类久久久精品极度| 一区二区三区四区五区精品| 91久久精品国产91性色tv| 香蕉久久一区二区不卡无毒影院| 91久久精品国产91久久| 久久国产主播精品| 欧美一二区视频| 欧美日韩国产成人在线91| 另类尿喷潮videofree| 国产精品婷婷| 一本色道久久88综合日韩精品| 亚洲第一视频网站| 久久精品五月婷婷| 久久激情网站| 国产色婷婷国产综合在线理论片a| 亚洲精品在线电影| 亚洲精品久久久久久久久久久| 久久精品国内一区二区三区| 欧美在线网址| 国产精品视频第一区| 中日韩美女免费视频网站在线观看| 亚洲日本电影| 久久久精品日韩| 久久五月婷婷丁香社区| 国产一区久久| 久久狠狠婷婷| 免费的成人av| 在线不卡视频| 久久野战av| 欧美高清视频一区二区三区在线观看 | 亚洲欧洲精品一区二区三区不卡| 伊人久久大香线蕉综合热线 | 亚洲国产精品美女| 日韩视频精品在线观看| 欧美h视频在线| 欧美激情网友自拍| 亚洲人成人77777线观看| 美女久久网站| 日韩视频免费在线观看| 亚洲视频在线免费观看| 国产精品国产a级| 亚洲资源在线观看| 久久久久久久欧美精品| 国产自产在线视频一区| 久久亚洲私人国产精品va| 亚洲国产精品久久精品怡红院| 9i看片成人免费高清| 欧美三区美女| 欧美在线视频不卡| 亚洲欧洲日本专区| 午夜久久一区| 亚洲承认在线| 欧美精品国产精品| 亚洲一二三区精品| 久久综合久久久| 亚洲精品久久久久久久久久久| 欧美日产国产成人免费图片| 亚洲一区网站| 欧美电影打屁股sp| 午夜精彩视频在线观看不卡| 国产在线精品成人一区二区三区 | 性欧美暴力猛交另类hd| 免费日韩av| 亚洲欧美日韩第一区| 伊人狠狠色j香婷婷综合| 欧美激情一区二区三区在线| 亚洲欧美日韩高清| 亚洲黄色视屏| 久久男女视频| 亚洲欧美另类久久久精品2019| 国产小视频国产精品| 欧美国产一区二区| 欧美一站二站| 亚洲精品视频在线播放| 欧美专区亚洲专区| 亚洲人成亚洲人成在线观看| 国产精品美女诱惑| 欧美理论电影在线播放| 久久国产手机看片| 亚洲特级毛片| 91久久精品网| 欧美夫妇交换俱乐部在线观看| 午夜精品剧场| 亚洲小说欧美另类婷婷| 亚洲人成在线播放| 尤物yw午夜国产精品视频明星| 国产精品理论片| 欧美精品99| 可以免费看不卡的av网站| 午夜精品99久久免费| 99在线精品视频在线观看| 亚洲国产精品第一区二区三区| 久久视频在线看| 久久九九免费| 欧美一级在线播放| 亚洲影院在线| 亚洲一区尤物| 在线视频欧美日韩| 99re6热只有精品免费观看| 亚洲成人自拍视频| 亚洲丁香婷深爱综合| 精品成人免费| 伊人久久亚洲美女图片| 韩国三级在线一区| 狠狠爱成人网| 经典三级久久| 1000部国产精品成人观看| 在线欧美视频| 亚洲国产老妈| 亚洲精品久久久久久下一站 | 国产精品mv在线观看| 欧美午夜国产| 国产精品久久久久av免费| 国产精品久久毛片a| 国产精品久久久久9999吃药| 国产精品视频观看| 国内精品模特av私拍在线观看| 狠狠综合久久av一区二区老牛| 国内自拍一区| 亚洲精品麻豆| 在线视频日韩| 久久精品亚洲一区二区| 麻豆精品在线观看| 亚洲国产裸拍裸体视频在线观看乱了中文 | 老鸭窝91久久精品色噜噜导演| 免费欧美在线视频| 欧美视频一区二区三区在线观看| 国产精品久久久免费| 好吊一区二区三区| 日韩小视频在线观看| 亚洲一区三区在线观看| 久久婷婷成人综合色| 亚洲欧洲三级| 亚洲一区二区伦理| 久久男人资源视频| 欧美日韩亚洲综合| 国产一区二区高清| 亚洲激情视频在线| 午夜国产不卡在线观看视频| 久久亚洲精品欧美| 99riav1国产精品视频| 欧美一区激情| 欧美老女人xx| 好男人免费精品视频| 亚洲少妇中出一区| 免费一区二区三区| 亚洲一区一卡| 欧美精品97| 精品不卡一区二区三区| 亚洲影院免费观看| 亚洲第一区在线| 亚洲欧美日韩在线高清直播| 蜜桃av一区二区三区| 国产欧美日韩免费| 宅男噜噜噜66一区二区| 麻豆成人av| 欧美一区在线看| 国产精品美女久久久久久2018| 亚洲国产精品久久久久秋霞影院| 亚洲女人天堂成人av在线| 欧美国产精品中文字幕|