• <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色综合久久天堂| 99久久精品免费国产大片| 久久久噜噜噜久久中文字幕色伊伊| 日韩精品久久久肉伦网站| 狠狠色丁香婷综合久久| 18岁日韩内射颜射午夜久久成人| 成人资源影音先锋久久资源网| 久久99这里只有精品国产| 久久99精品久久久久久野外| 久久婷婷国产剧情内射白浆| 久久久久亚洲AV无码去区首| 亚洲va国产va天堂va久久| 99精品国产99久久久久久97| 久久精品国产影库免费看| 久久天天躁狠狠躁夜夜2020一| A级毛片无码久久精品免费| 久久综合九色综合网站| 久久久久这里只有精品 | 国产亚洲精久久久久久无码77777| 久久人人爽人人爽人人AV东京热| 亚洲国产小视频精品久久久三级 | 亚洲?V乱码久久精品蜜桃| 国产精品久久久久无码av| 精品久久久一二三区| 久久精品国产精品亚洲| www久久久天天com| 99精品久久精品一区二区| 伊人久久大香线蕉AV色婷婷色 | 久久精品国产亚洲Aⅴ香蕉 | 婷婷综合久久狠狠色99h| 2020久久精品国产免费| 少妇内射兰兰久久| 成人午夜精品无码区久久| 7777精品伊人久久久大香线蕉| 久久亚洲AV无码西西人体|