• <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)  編輯 收藏 引用 所屬分類: 圖論
            亚洲精品NV久久久久久久久久| 99久久国产热无码精品免费| 久久久久久国产精品无码下载 | 久久99九九国产免费看小说| 欧美激情精品久久久久久久九九九| 久久天天躁夜夜躁狠狠| 久久99精品久久久久久hb无码 | 无码人妻精品一区二区三区久久久| 国产亚洲婷婷香蕉久久精品| 中文字幕久久亚洲一区| 国产综合久久久久久鬼色| 欧美国产成人久久精品| 国内精品人妻无码久久久影院| 欧美国产精品久久高清| 久久99国产精品二区不卡| 亚洲国产成人精品女人久久久| 国产成人精品久久二区二区| 亚洲AV无码久久精品狠狠爱浪潮| 久久高潮一级毛片免费| 久久久久久久尹人综合网亚洲 | 亚洲伊人久久大香线蕉苏妲己| 国内精品久久久久影院薰衣草| 国产精品激情综合久久| 狠色狠色狠狠色综合久久 | 狠狠色婷婷久久一区二区三区| 精品久久久一二三区| 久久综合给合综合久久| 国产精品成人无码久久久久久| 久久精品国产69国产精品亚洲| 亚洲精品白浆高清久久久久久| 久久天天躁狠狠躁夜夜不卡| 亚洲国产成人精品女人久久久| 久久久免费观成人影院| 久久国产精品免费一区二区三区| 久久久久国产精品| 久久综合久久久| 久久97久久97精品免视看秋霞| 国产午夜福利精品久久| 久久国产亚洲精品麻豆| 亚洲精品午夜国产va久久| 久久久久久久精品妇女99|