• <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)  編輯 收藏 引用 所屬分類: 圖論
            久久精品国产亚洲精品2020| 少妇人妻综合久久中文字幕| 国产精品久久久久久久久久影院| 国产2021久久精品| 四虎亚洲国产成人久久精品| 久久精品国产亚洲av麻豆蜜芽 | 国产99久久久国产精免费| 99久久成人18免费网站| 综合网日日天干夜夜久久| 国产精品99久久久久久猫咪 | 精品一区二区久久| 久久久久亚洲AV成人网人人网站 | 亚洲午夜久久久精品影院| 综合久久精品色| 国内精品欧美久久精品| 国产精品福利一区二区久久| 久久人与动人物a级毛片| 国产精品久久久久久搜索| 久久激情亚洲精品无码?V| 久久久久久久99精品免费观看| 天天爽天天狠久久久综合麻豆| 中文字幕无码久久精品青草| 国产精品久久久久影院色| 伊人热热久久原色播放www| 女人香蕉久久**毛片精品| 久久亚洲精精品中文字幕| 亚洲va国产va天堂va久久| 亚洲精品乱码久久久久久不卡| 国产精品视频久久久| 97久久国产露脸精品国产| 亚洲第一永久AV网站久久精品男人的天堂AV | 久久久这里有精品中文字幕| 久久不射电影网| 国产精品久久久久无码av| 久久久一本精品99久久精品66 | 欧美成a人片免费看久久| 情人伊人久久综合亚洲| 国产一级持黄大片99久久| 国产精品视频久久| 香港aa三级久久三级| 久久AAAA片一区二区|