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

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>
            亚洲盗摄视频| 激情综合色综合久久| 狠狠色综合色区| 久久久国产精品一区二区三区| 亚洲网站视频福利| 国产精品久久久久久影院8一贰佰 国产精品久久久久久影视 | 狂野欧美激情性xxxx| 久久久久久久综合色一本| 黄色成人在线免费| 蜜臀久久99精品久久久画质超高清| 久久精品国产久精国产思思| **性色生活片久久毛片| 亚洲黄色av| 国产精品国产三级国产专播品爱网 | 欧美国产日韩视频| 欧美精品网站| 亚洲欧美日韩国产一区二区三区 | 亚洲精选大片| 国产精品黄色在线观看| 久久久亚洲国产天美传媒修理工| 久久综合久久综合九色| 中国成人黄色视屏| 亚洲一区视频在线| 亚洲大片一区二区三区| 日韩视频第一页| 国产专区综合网| 欧美国产日韩二区| 欧美激情视频一区二区三区在线播放 | 久久九九国产| 亚洲性图久久| 久久亚洲一区| 午夜综合激情| 欧美二区不卡| 久久久综合网| 国产精品美女一区二区| 欧美激情亚洲一区| 国产日韩精品在线播放| 亚洲美女毛片| 亚洲国产导航| 国内精品久久久久久久影视麻豆 | 欧美在线免费观看亚洲| 一区二区三区 在线观看视频| 亚洲久久成人| 国产精品视频午夜| 久久国产精品久久w女人spa| 久久精品视频在线观看| 在线视频国产日韩| 亚洲国内精品在线| 国产主播精品| 亚洲自拍三区| 国内精品国语自产拍在线观看| 噜噜噜在线观看免费视频日韩| 欧美gay视频激情| 一区二区三区国产| 午夜精品在线视频| 亚洲欧洲午夜| 欧美护士18xxxxhd| 久久一二三区| 夜夜爽99久久国产综合精品女不卡| 亚洲一区在线播放| 一区二区三区在线观看国产| 日韩视频一区二区三区在线播放免费观看| 国产精品稀缺呦系列在线| 欧美α欧美αv大片| 欧美性感一类影片在线播放| 欧美成人dvd在线视频| 欧美一级专区| 亚洲精品乱码视频| 久久男人av资源网站| 欧美日韩亚洲一区二区| 久久免费99精品久久久久久| 欧美午夜片欧美片在线观看| 一本色道久久综合亚洲精品不卡 | 久久精品在线| 欧美亚洲日本国产| 欧美日韩一区免费| 欧美激情第8页| 国产在线精品一区二区夜色| 久久久久久久欧美精品| 影视先锋久久| 亚洲综合国产精品| 中日韩午夜理伦电影免费| 久久久五月婷婷| 性色av一区二区怡红| 欧美日本韩国| 亚洲电影视频在线| 国产精品一区二区久久国产| 亚洲天堂第二页| 亚洲美女黄网| 欧美黑人在线播放| 欧美成人一区二区三区在线观看 | 亚洲影院一区| 亚洲性视频h| 欧美日韩亚洲激情| 99国产精品99久久久久久| 亚洲精品一区在线| 欧美freesex8一10精品| 亚洲欧美电影院| 欧美在线观看网址综合| 欧美日韩一区二区三区免费看| 亚洲第一精品福利| 亚洲三级免费观看| 欧美mv日韩mv国产网站app| 欧美激情久久久久久| 亚洲国产综合视频在线观看| 在线综合亚洲| 午夜天堂精品久久久久| 国产精品看片你懂得| 亚洲男人的天堂在线aⅴ视频| 亚洲一区二区精品在线| 国产精品卡一卡二| 亚洲欧美日韩国产精品| 性久久久久久久久久久久| 国产精品一区毛片| 蜜桃久久精品乱码一区二区| 国产日韩在线播放| 小嫩嫩精品导航| 久久久久一区二区三区| 亚洲国产精品va在线看黑人| 欧美激情第二页| 亚洲视频综合| 久久久免费精品| 国产精品v欧美精品v日韩| 国产精品99久久久久久久vr | 欧美日韩伦理在线免费| 亚洲一级影院| 久久字幕精品一区| 国产精品国产三级国产普通话99| 欧美激情第3页| 午夜精品视频在线观看| 欧美高清视频| 亚洲综合不卡| 在线观看日韩av| 欧美日韩免费观看一区二区三区| 午夜精品福利一区二区蜜股av| 久久久久www| 欧美在线视频在线播放完整版免费观看| 国产在线精品自拍| 欧美日韩一区在线观看| 欧美一区二区日韩| 亚洲国产精品va在线看黑人| 欧美在线视频一区| 一区二区精品在线观看| 国产在线乱码一区二区三区| 久久亚洲春色中文字幕| 亚洲精品一区中文| 欧美一区二区视频在线观看2020| 亚洲国产成人av| 国产日韩欧美精品| 欧美日韩亚洲不卡| 久久永久免费| 先锋影音久久| 午夜一级久久| 亚洲欧洲一区二区三区| 国产午夜亚洲精品不卡| 欧美日韩在线免费观看| 久久日韩粉嫩一区二区三区 | 国产农村妇女精品一区二区| 欧美日本簧片| 久久综合影音| 欧美中文字幕在线播放| 亚洲一区二区三区在线播放| 99精品国产99久久久久久福利| 国产精品系列在线| 欧美私人啪啪vps| 欧美成人综合一区| 久久永久免费| 久久人人爽人人| 久久久久九九九| 午夜伦欧美伦电影理论片| 亚洲电影免费观看高清完整版| 国产精品一区亚洲| 国产精品99一区| 欧美理论在线播放| 欧美成人自拍| 欧美精品97| 欧美精品在线网站| 欧美在线免费观看| 欧美日韩一区二区免费视频| 欧美日韩国产一区二区| 欧美精品入口| 欧美人体xx| 欧美精品日日鲁夜夜添| 欧美日韩欧美一区二区| 欧美成人国产| 国产精品色网| 国产一区二区三区免费在线观看| 国产日韩欧美在线播放| 激情自拍一区| 国产情侣一区| 极品日韩久久| 亚洲精选国产| 中文国产一区| 欧美一区二区在线看| 亚洲自拍16p| 中文在线一区| 欧美亚洲在线视频| 美女日韩欧美| 亚洲人体大胆视频| 99热在线精品观看|