• <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>
            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 閱讀(256) 評論(0)  編輯 收藏 引用 所屬分類: 圖論
            色播久久人人爽人人爽人人片AV| 中文国产成人精品久久不卡| 亚洲综合精品香蕉久久网97| 日本加勒比久久精品| 久久无码AV中文出轨人妻| 色婷婷久久综合中文久久蜜桃av| 日本精品久久久久中文字幕8| 久久久久久极精品久久久| 亚洲va久久久噜噜噜久久男同| 日韩亚洲欧美久久久www综合网| 亚洲午夜精品久久久久久app| 国产精品一久久香蕉国产线看观看| 91久久精品视频| 久久精品黄AA片一区二区三区| 久久强奷乱码老熟女网站| 久久99国产综合精品女同| 午夜精品久久久久久久无码| 97r久久精品国产99国产精| 国产精品成人久久久| 久久精品一区二区三区中文字幕| 2021久久精品国产99国产精品| 亚洲午夜福利精品久久| 久久九九免费高清视频| 91久久九九无码成人网站| 久久久久久国产精品无码超碰| 久久久久久久女国产乱让韩| 九九热久久免费视频| 亚洲国产精品婷婷久久| 精品久久久久久| 97久久精品人妻人人搡人人玩| 18岁日韩内射颜射午夜久久成人| 久久久精品日本一区二区三区| 国内精品久久久久久不卡影院| 91亚洲国产成人久久精品| 99久久精品国产高清一区二区| 人妻无码久久一区二区三区免费 | 亚洲国产精品久久电影欧美| 人人狠狠综合88综合久久| 麻豆久久久9性大片| 性色欲网站人妻丰满中文久久不卡| 久久国语露脸国产精品电影|