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

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>
            国产精品日韩欧美综合| 中日韩午夜理伦电影免费| 亚洲欧美成人一区二区在线电影| 欧美理论视频| 一区二区日韩欧美| 一区二区日韩欧美| 国产精品影视天天线| 欧美在线视频一区二区三区| 欧美在线你懂的| 尤物yw午夜国产精品视频明星| 欧美成人在线免费观看| 欧美成人69av| 亚洲综合第一| 久久久久久国产精品mv| 亚洲日本国产| 亚洲女性喷水在线观看一区| 狠狠色狠狠色综合日日五| 欧美国产日韩在线观看| 欧美午夜宅男影院| 麻豆成人在线| 欧美色中文字幕| 美女在线一区二区| 欧美视频官网| 欧美成在线视频| 欧美视频一二三区| 另类天堂av| 国产精品久久久久毛片软件| 毛片一区二区| 国产精品欧美久久| 欧美成人精品一区二区三区| 国产精品成av人在线视午夜片| 久久久免费观看视频| 欧美精品一区二区高清在线观看| 久久aⅴ国产紧身牛仔裤| 欧美高清在线精品一区| 久久久亚洲国产天美传媒修理工 | 亚洲区一区二区三区| 欧美日韩高清在线播放| 久久色在线播放| 国产精品久久久久久久久免费| 欧美成人影音| 狠狠色丁香婷婷综合影院 | 蜜臀va亚洲va欧美va天堂| 国产精品v亚洲精品v日韩精品 | 亚洲欧美在线看| 欧美大片一区| 欧美电影免费| 狠狠色综合日日| 午夜精品久久久久久久男人的天堂 | 午夜精品一区二区三区在线| 在线一区二区三区四区| 免费观看国产成人| 玖玖玖免费嫩草在线影院一区| 国产精品日本一区二区| 一区二区日韩欧美| 亚洲午夜高清视频| 欧美日韩在线看| 日韩视频免费| 一区二区三区 在线观看视频| 欧美电影免费观看高清完整版| 久久亚洲国产精品一区二区 | 欧美激情精品久久久久久| 欧美激情一区二区三区蜜桃视频| 激情懂色av一区av二区av| 亚洲欧美日韩一区二区| 欧美一区日本一区韩国一区| 国产精品电影在线观看| 亚洲午夜视频| 午夜精品成人在线视频| 国产免费成人| 久久国产一二区| 鲁大师影院一区二区三区| 亚洲电影免费在线| 欧美激情精品久久久久久蜜臀 | 欧美不卡在线视频| 亚洲激情一区| 欧美日韩欧美一区二区| 中国女人久久久| 午夜欧美精品| 极品少妇一区二区三区| 久热精品在线| 亚洲三级性片| 亚洲欧美日韩国产综合精品二区| 国产精品毛片va一区二区三区 | 亚洲影院免费观看| 久久一区中文字幕| 日韩一区二区久久| 国产精品毛片大码女人| 久久五月婷婷丁香社区| 亚洲欧洲视频| 欧美亚洲一区二区在线| 在线不卡视频| 欧美系列精品| 久久久中精品2020中文| 亚洲免费观看高清在线观看| 欧美影院成年免费版| 在线欧美不卡| 国产精品乱码一区二区三区 | 亚洲天堂免费在线观看视频| 久久综合狠狠| 亚洲午夜国产成人av电影男同| 国产综合久久久久久| 欧美精品一区在线观看| 香蕉久久夜色精品国产使用方法| 欧美激情在线免费观看| 欧美一级久久久| 亚洲精品欧美日韩| 国产亚洲一级| 欧美午夜欧美| 欧美国产精品中文字幕| 性感少妇一区| 一区二区三区www| 欧美电影在线播放| 久久久99国产精品免费| 亚洲香蕉在线观看| 亚洲日韩欧美视频| 一区视频在线播放| 国产精品视频专区| 欧美日韩一卡二卡| 美女诱惑黄网站一区| 欧美一区二区三区在线观看视频| 日韩一级黄色av| 91久久久在线| 欧美激情亚洲视频| 快she精品国产999| 久久久久久尹人网香蕉| 亚洲欧美视频| 亚洲一区视频在线观看视频| 亚洲欧洲一区二区三区在线观看| 韩国三级电影一区二区| 国产日韩欧美一区在线| 国产精品毛片高清在线完整版| 欧美精品在线视频| 欧美精品v日韩精品v国产精品| 久久九九99| 久久久久久电影| 久久影院午夜论| 久久手机免费观看| 噜噜噜91成人网| 免费日韩av| 欧美精品系列| 老司机67194精品线观看| 91久久国产综合久久| 狠狠久久婷婷| 国产伦精品一区二区三区视频黑人 | 午夜伦理片一区| 亚洲欧美文学| 欧美尤物一区| 久久天堂av综合合色| 久久一区精品| 欧美国产一区在线| 欧美色一级片| 国产欧美日韩在线观看| 国产亚洲欧美一区| 在线欧美福利| 99视频一区二区| 亚洲免费视频中文字幕| 久久aⅴ国产紧身牛仔裤| 久久婷婷激情| 亚洲国产一二三| 一区二区冒白浆视频| 亚洲一区视频| 麻豆九一精品爱看视频在线观看免费| 玖玖玖国产精品| 欧美日韩三级一区二区| 国产精品一区久久| 亚洲电影视频在线| 一区二区免费在线视频| 久久不见久久见免费视频1| 噜噜爱69成人精品| 亚洲毛片在线观看| 久久er精品视频| 欧美激情成人在线视频| 国产精品久久久久久久久久免费看| 国产区二精品视| 亚洲国产欧美不卡在线观看| 亚洲欧美成人在线| 欧美成ee人免费视频| 亚洲综合精品一区二区| 久久久www免费人成黑人精品| 欧美韩日一区二区三区| 亚洲永久精品大片| 欧美成人一区二区三区| 国产精品一区二区视频| 亚洲福利av| 99精品国产高清一区二区| 久久国产一区| 99精品热6080yy久久| 久久久亚洲成人| 国产精品日韩久久久久| 亚洲国产91| 久久精品一区二区三区中文字幕| 亚洲激情专区| 夜夜嗨一区二区三区| 毛片一区二区| 国产一区二区欧美日韩| 亚洲一区二区三区在线播放| 亚洲第一狼人社区| 久久国产一二区| 国产精品夫妻自拍|