• <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| 久久婷婷五月综合色99啪ak| 2021国产精品久久精品| 久久天天躁狠狠躁夜夜网站| 94久久国产乱子伦精品免费| 久久www免费人成看片| 久久精品国产精品青草app| 久久一区二区免费播放| 久久精品国产一区二区三区日韩| 久久综合狠狠综合久久97色| 久久99国产精品尤物| 一个色综合久久| 久久综合伊人77777| 久久久久久A亚洲欧洲AV冫| 久久综合给久久狠狠97色| 日本精品久久久久影院日本| 91精品国产9l久久久久| 亚洲精品无码久久久久AV麻豆| 国产午夜久久影院| 成人午夜精品无码区久久| 亚洲一区精品伊人久久伊人 | 浪潮AV色综合久久天堂| 麻豆久久久9性大片| 精品久久久久久99人妻| 久久综合九色综合精品| 国内精品久久久久久99蜜桃| 日韩人妻无码一区二区三区久久 | 久久久久久久波多野结衣高潮| 久久se精品一区二区影院| 久久狠狠色狠狠色综合| 国内精品久久久久影院一蜜桃 | 精品熟女少妇a∨免费久久| 东方aⅴ免费观看久久av| 久久免费看黄a级毛片| 久久精品国产色蜜蜜麻豆| 久久精品国产99国产精品导航| 久久精品国产免费观看| 欧洲人妻丰满av无码久久不卡|