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

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>
            欧美一区二区成人6969| 亚洲精品在线一区二区| 中文高清一区| 国产精品日日做人人爱 | 美女脱光内衣内裤视频久久网站| 黄色亚洲精品| 欧美高清视频在线播放| 欧美日韩免费| 久久国产精品亚洲77777| 久久精品中文| 亚洲剧情一区二区| 亚洲一二三级电影| 国产精品家庭影院| 老司机精品视频网站| 欧美国产日韩精品| 亚洲一区二区在线| 久久久精品一区二区三区| 亚洲激情欧美| 亚洲午夜高清视频| 欲色影视综合吧| 99国产一区| 伊人久久男人天堂| 一区二区三区国产盗摄| 黄色成人在线网址| 一本色道久久综合狠狠躁篇的优点 | 久久精品国产一区二区三| 久热精品视频在线观看| 亚洲一区二区三区免费视频| 欧美影院午夜播放| 亚洲午夜久久久久久久久电影院| 欧美在线观看视频在线| av成人免费在线观看| 久久国产婷婷国产香蕉| 一区二区久久久久| 久久久人成影片一区二区三区| 99亚洲精品| 久久久五月天| 久久国产一二区| 欧美视频导航| 亚洲欧洲日韩在线| 狠狠久久五月精品中文字幕| 99精品热6080yy久久| 亚洲激情亚洲| 久久久99久久精品女同性| 亚洲视频网站在线观看| 老巨人导航500精品| 久久久久看片| 国产欧美视频一区二区| 日韩视频一区二区三区在线播放免费观看| 国产在线国偷精品产拍免费yy| 日韩午夜在线电影| 日韩图片一区| 免费成人你懂的| 欧美成人免费全部| 尤妮丝一区二区裸体视频| 亚洲欧美在线磁力| 亚洲欧美激情诱惑| 欧美午夜片在线观看| 亚洲精品国产精品国自产在线 | 国产精品爽黄69| 亚洲一二三级电影| 午夜精品久久久久久久99水蜜桃| 欧美日本不卡| 亚洲精品一区二区在线| 亚洲精品偷拍| 欧美日韩国产999| 日韩视频国产视频| 亚洲午夜在线观看视频在线| 欧美日韩中文字幕综合视频| 日韩视频在线观看免费| 亚洲私人影院| 国产精品日韩欧美| 亚洲欧美在线aaa| 久久精品二区亚洲w码| 国产丝袜美腿一区二区三区| 欧美一区久久| 欧美国产日韩在线| 亚洲美女免费视频| 欧美日韩在线精品| 亚洲一区在线视频| 久久综合导航| 亚洲久久成人| 国产精品草草| 久久久久国产精品一区| 欧美激情一区二区三区四区| 一本色道久久综合亚洲精品不卡 | 欧美亚洲视频一区二区| 美国成人毛片| 日韩亚洲欧美一区二区三区| 欧美日韩中文在线| 欧美一区二区成人| 亚洲国内高清视频| 性娇小13――14欧美| 国产亚洲视频在线| 欧美精品日日鲁夜夜添| 亚洲一区三区在线观看| 久久久久高清| 日韩一级精品| 韩国一区二区三区美女美女秀| 蜜桃久久av一区| 在线综合欧美| 欧美激情自拍| 性色一区二区三区| 亚洲国产欧美国产综合一区| 欧美视频成人| 久久性天堂网| 午夜精品一区二区三区四区| 欧美激情视频网站| 欧美一区二区三区免费看| 亚洲欧洲在线观看| 国产午夜精品一区二区三区视频| 美女免费视频一区| 性做久久久久久久免费看| 亚洲第一综合天堂另类专| 欧美一级午夜免费电影| 亚洲精品国产视频| 国际精品欧美精品| 国产精品sss| 欧美福利一区| 久久综合五月天婷婷伊人| 亚洲欧美日韩系列| 亚洲精品在线视频观看| 欧美大片一区二区| 久久久蜜桃一区二区人| 亚洲综合色自拍一区| 99热这里只有精品8| 亚洲福利久久| 国产一区二区三区无遮挡| 欧美午夜片在线观看| 欧美精品一区二区三区很污很色的| 欧美一区永久视频免费观看| 国产精品99久久99久久久二8| 亚洲国产婷婷香蕉久久久久久| 久久综合久久综合九色| 香蕉成人久久| 亚洲欧美日韩在线观看a三区| 在线性视频日韩欧美| 亚洲精品一级| 亚洲精品偷拍| 亚洲伦理在线| 在线午夜精品| 亚洲一区二区三区国产| 亚洲午夜精品一区二区三区他趣| 亚洲黄色影片| 日韩视频免费在线| 夜夜嗨av一区二区三区网页| 亚洲日本在线观看| 亚洲精品免费在线| 日韩视频一区二区三区| 亚洲精品一区在线观看| 夜夜爽99久久国产综合精品女不卡| 在线观看视频亚洲| 亚洲三级色网| 99亚洲精品| 亚洲欧美日韩成人| 久久成人综合网| 久久综合国产精品| 欧美激情第1页| 亚洲日本欧美天堂| 在线亚洲免费视频| 亚洲欧美不卡| 久久久久99| 女女同性精品视频| 欧美视频精品在线观看| 国产精品一区二区在线| 国内一区二区在线视频观看| 亚洲电影免费观看高清完整版 | 欧美日韩一区二区在线观看视频| 欧美视频不卡| 狠狠色丁香久久婷婷综合_中| 亚洲国产精品久久人人爱蜜臀| 亚洲精品网址在线观看| 亚洲欧美日韩一区在线| 久久久久国产精品一区二区| 亚洲国产1区| 亚洲欧美日韩一区二区在线| 老司机成人网| 国产老女人精品毛片久久| 精品动漫3d一区二区三区免费版 | 最新国产成人av网站网址麻豆| 中文日韩在线视频| 久久中文欧美| 国产精品免费一区二区三区在线观看 | 久久久久久网站| 亚洲精品精选| 先锋影音国产精品| 欧美激情一区二区三区在线| 国产欧美一区二区白浆黑人| 亚洲精品色婷婷福利天堂| 欧美亚洲系列| 日韩一本二本av| 久久欧美中文字幕| 国产精品午夜在线观看| 日韩视频第一页| 蜜桃av一区| 午夜欧美精品| 国产精品久久久久91| 亚洲精品国产拍免费91在线| 久久久久久日产精品| 亚洲网站啪啪|