青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

posts - 7,comments - 3,trackbacks - 0
Slim Span
Time Limit: 5000MSMemory Limit: 65536K
Total Submissions: 4023Accepted: 2116

Description

Given an undirected weighted graph G, you should find one of spanning trees specified as follows.

The graph G is an ordered pair (VE), where V is a set of vertices {v1v2, …, vn} and E is a set of undirected edges {e1e2, …, em}. Each edge e ∈ E has its weight w(e).

A spanning tree T is a tree (a connected subgraph without cycles) which connects all the n vertices with n − 1 edges. The slimness of a spanning tree T is defined as the difference between the largest weight and the smallest weight among the n − 1 edges of T.


Figure 5: A graph G and the weights of the edges

For example, a graph G in Figure 5(a) has four vertices {v1v2v3v4} and five undirected edges {e1e2e3e4e5}. The weights of the edges are w(e1) = 3, w(e2) = 5, w(e3) = 6, w(e4) = 6, w(e5) = 7 as shown in Figure 5(b).


Figure 6: Examples of the spanning trees of G

There are several spanning trees for G. Four of them are depicted in Figure 6(a)~(d). The spanning tree Ta in Figure 6(a) has three edges whose weights are 3, 6 and 7. The largest weight is 7 and the smallest weight is 3 so that the slimness of the tree Ta is 4. The slimnesses of spanning trees TbTc and Td shown in Figure 6(b), (c) and (d) are 3, 2 and 1, respectively. You can easily see the slimness of any other spanning tree is greater than or equal to 1, thus the spanning tree Td in Figure 6(d) is one of the slimmest spanning trees whose slimness is 1.

Your job is to write a program that computes the smallest slimness.

Input

The input consists of multiple datasets, followed by a line containing two zeros separated by a space. Each dataset has the following format.

nm
a1b1w1
ambmwm

Every input item in a dataset is a non-negative integer. Items in a line are separated by a space. n is the number of the vertices and m the number of the edges. You can assume 2 ≤ n ≤ 100 and 0 ≤ m ≤ n(n − 1)/2. ak and bk (k = 1, …, m) are positive integers less than or equal to n, which represent the two vertices vak and vbk connected by the kth edge ekwk is a positive integer less than or equal to 10000, which indicates the weight of ek. You can assume that the graph G = (VE) is simple, that is, there are no self-loops (that connect the same vertex) nor parallel edges (that are two or more edges whose both ends are the same two vertices).

Output

For each dataset, if the graph has spanning trees, the smallest slimness among them should be printed. Otherwise, −1 should be printed. An output should not contain extra characters.

Sample Input

4 5
1 2 3
1 3 5
1 4 6
2 4 6
3 4 7
4 6
1 2 10
1 3 100
1 4 90
2 3 20
2 4 80
3 4 40
2 1
1 2 1
3 0
3 1
1 2 1
3 3
1 2 2
2 3 5
1 3 6
5 10
1 2 110
1 3 120
1 4 130
1 5 120
2 3 110
2 4 120
2 5 130
3 4 120
3 5 110
4 5 120
5 10
1 2 9384
1 3 887
1 4 2778
1 5 6916
2 3 7794
2 4 8336
2 5 5387
3 4 493
3 5 6650
4 5 1422
5 8
1 2 1
2 3 100
3 4 100
4 5 100
1 5 50
2 5 50
3 5 50
4 1 150
0 0

Sample Output

1
20
0
-1
-1
1
0
1686
50

Source



題目就是生成一棵樹,要求邊權最大減最小的差最小。
根據Kruskal思想,把邊排序,之后枚舉一下就行了。

代碼:

#include <cmath>
#include 
<cstdio>
#include 
<cstdlib>
#include 
<cstring>
#include 
<iostream>
#include 
<algorithm>
using namespace std;

const int M = 5005;
const int INF = 1 << 29;

struct edge
{
    
int st, ed, w;
    
bool operator < (edge a) const
    {
        
return w < a.w;
    }
} e[M];

int n, m, ans, num, temp;
int f[105], rank[105];

void makeset()
{
    
for (int i = 1; i <= n; ++i)
        f[i] 
= i;
    memset(rank, 
0sizeof(rank));
}

int find(int x)
{
    
while (f[x] != x) x = f[x];
    
return x;
}

void unionset(int a, int b)
{
    
int p = find(a);
    
int q = find(b);
    
if (rank[p] > rank[q])
        f[q] 
= p;
    
else
    
if (rank[p] < rank[q])
        f[p] 
= q;
    
else
    {
        f[p] 
= q;
        rank[q]
++;
    }
}

void kruskal()
{
    ans 
= INF;
    
for (int i = 0; i < m - n + 2++i)
    {
        makeset();
        temp 
= -1;
        num 
= 0;
        
for (int j = i; j < m; ++j)
        {
            
if (find(e[j].st) != find(e[j].ed))
            {
                num
++;
                unionset(e[j].st, e[j].ed);
                
if (num == n - 1)
                {
                    temp 
= e[j].w - e[i].w;
                    
break;
                }
            }
        }
        
if (temp == -1break;
        
if (temp != -1 && temp < ans) ans = temp;
    }
    
if (ans >= INF) printf("-1\n");
    
else printf("%d\n", ans);
}

int main()
{
    
while (scanf("%d%d"&n, &m), n || m)
    {
        
for (int i = 0; i < m; ++i)
            scanf(
"%d%d%d"&e[i].st, &e[i].ed, &e[i].w);
        sort(e, e 
+ m);
        kruskal();
    }
    
return 0;
}
posted on 2011-10-17 15:54 LLawliet 閱讀(381) 評論(0)  編輯 收藏 引用 所屬分類: 圖論
青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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>
            亚洲桃花岛网站| 国内偷自视频区视频综合| 亚洲人成在线观看网站高清| 亚洲福利电影| 麻豆av一区二区三区久久| 亚洲国产精品嫩草影院| 亚洲看片网站| 欧美日韩国产三级| 午夜精品亚洲一区二区三区嫩草| 亚洲影院污污.| 在线精品视频一区二区| 亚洲人成绝费网站色www| 国产精品99一区| 久久久九九九九| 欧美高清视频在线| 欧美一区二区高清| 久久尤物视频| 日韩亚洲欧美成人| 午夜国产欧美理论在线播放| 亚洲国产高清自拍| 一区二区欧美精品| 亚洲国产三级网| 亚洲欧美视频在线观看| 最新国产の精品合集bt伙计| 亚洲一区在线看| 亚洲精品国产系列| 欧美一区二粉嫩精品国产一线天| 亚洲国产高清在线| 亚洲欧美日本国产专区一区| 亚洲日本免费电影| 亚洲男人的天堂在线| 日韩视频免费大全中文字幕| 欧美亚洲一区二区在线| 9l视频自拍蝌蚪9l视频成人| 欧美中文字幕在线播放| 宅男噜噜噜66一区二区66| 久久久av网站| 性欧美精品高清| 欧美精品色一区二区三区| 久久五月婷婷丁香社区| 国产精品美女黄网| 亚洲精品乱码久久久久久蜜桃91 | 免费日韩视频| 国产日韩精品在线观看| 一本久道久久久| 日韩视频一区二区三区在线播放| 久久高清免费观看| 午夜久久资源| 国产精品videosex极品| 亚洲区第一页| 日韩一级欧洲| 欧美丰满高潮xxxx喷水动漫| 免费亚洲电影| 影音先锋国产精品| 久久不射网站| 欧美综合激情网| 国产精品久久久久久一区二区三区| 91久久久久久久久| 日韩一级成人av| 久久亚洲精品欧美| 免费看的黄色欧美网站| 在线观看亚洲精品| 久久久亚洲一区| 欧美电影在线免费观看网站| 在线国产精品播放| 久久一二三四| 亚洲国产成人精品久久久国产成人一区 | 亚洲麻豆av| 在线亚洲高清视频| 国产精品mm| 亚洲小说春色综合另类电影| 香蕉乱码成人久久天堂爱免费| 国产精品成人久久久久| 亚洲无线视频| 久久久久久9| 亚洲国产成人精品久久| 欧美大片免费久久精品三p | 久久精品亚洲一区二区| 黑人一区二区三区四区五区| 另类酷文…触手系列精品集v1小说| 欧美高清视频一区二区| 日韩一区二区久久| 国产精品国产三级国产aⅴ9色| 亚洲一区二区三区四区在线观看| 欧美一区二区三区视频在线观看| 国产在线欧美| 欧美激情视频一区二区三区免费| 99在线精品免费视频九九视| 久久精品国产第一区二区三区最新章节 | 最近看过的日韩成人| 欧美激情中文字幕在线| 亚洲视频一区| 欧美大片一区| 午夜一区二区三视频在线观看 | 欧美精品一区在线发布| 亚洲一区二区三区四区五区黄| 久久综合色综合88| 亚洲天堂成人| 激情综合亚洲| 国产精品久99| 欧美成人三级在线| 欧美一区二区视频在线| 亚洲精品乱码久久久久久| 久久久久久久高潮| av成人免费观看| 激情久久综合| 国产精品网站视频| 欧美福利精品| 久久久精品日韩欧美| 日韩午夜中文字幕| 欧美成人免费在线观看| 亚洲欧美中文日韩在线| 99re热精品| 在线观看国产欧美| 国产乱码精品一区二区三区av | 午夜一区二区三区在线观看| 亚洲精品久久久蜜桃| 免费中文日韩| 久久精品一区二区三区四区 | 亚洲美女av网站| 一区免费在线| 国产一区二区三区在线观看视频| 欧美午夜三级| 欧美日韩免费视频| 欧美激情精品| 欧美暴力喷水在线| 噜噜噜躁狠狠躁狠狠精品视频| 欧美中文在线视频| 先锋影音国产精品| 亚洲欧美日韩天堂| 亚洲综合电影| 亚洲欧美日韩精品久久奇米色影视| 99精品国产福利在线观看免费| 亚洲成色www8888| 欧美激情免费观看| 欧美国产日韩a欧美在线观看| 狂野欧美激情性xxxx欧美| 久久久五月婷婷| 久久综合久久88| 可以免费看不卡的av网站| 久久亚洲精品一区| 欧美成人国产一区二区| 欧美成人综合一区| 亚洲观看高清完整版在线观看| 欧美va天堂va视频va在线| 蜜桃av一区二区在线观看| 欧美xxx在线观看| 亚洲高清视频在线观看| 91久久久久久国产精品| 99国产精品视频免费观看| 国产精品99久久久久久久女警 | 99精品国产高清一区二区| 一区二区三区久久久| 亚洲制服av| 欧美一区二区三区在线观看视频| 久久精品观看| 欧美激情精品久久久久久免费印度 | 亚洲第一视频网站| 日韩视频中文| 午夜视频一区二区| 久久综合色婷婷| 欧美日韩午夜精品| 国产欧美精品一区二区色综合| 好吊妞**欧美| 日韩午夜av在线| 欧美一区网站| 欧美激情精品久久久久久| 99精品欧美一区二区三区综合在线| 亚洲婷婷综合色高清在线| 欧美一级专区免费大片| 欧美成人午夜免费视在线看片 | 欧美在线一级视频| 欧美精品一区二区三区久久久竹菊 | 亚洲欧美国产77777| 久久一区二区三区av| 欧美不卡在线视频| 国产精品久久久久天堂| 亚洲电影毛片| 午夜国产精品视频| 亚洲第一中文字幕| 香蕉av福利精品导航| 毛片基地黄久久久久久天堂| 国产精品v欧美精品v日本精品动漫 | 国产精品永久免费视频| 亚洲激情第一页| 久久久久久久久伊人| 99国产一区| 久热综合在线亚洲精品| 国产精品网站视频| 一道本一区二区| 六月婷婷久久| 午夜精品视频在线观看一区二区| 欧美黄色成人网| 伊人激情综合| 久久精品女人的天堂av| 中文国产亚洲喷潮| 欧美人与性动交a欧美精品| 亚洲二区视频| 麻豆精品视频在线观看| 西瓜成人精品人成网站|