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

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>
            久久精品日韩一区二区三区| 久久国产一二区| 欧美视频在线观看一区| 亚洲视频观看| 亚洲视屏一区| 国产一区二区激情| 欧美成人嫩草网站| 欧美国产精品va在线观看| 亚洲最快最全在线视频| 一本色道久久加勒比88综合| 国产欧美日韩亚州综合| 久久久91精品国产一区二区三区| 欧美在线视频观看免费网站| 在线精品一区二区| 99国产精品久久久久久久成人热| 国产精品久久9| 久久这里只有精品视频首页| 欧美激情视频免费观看| 欧美一区激情| 嫩草伊人久久精品少妇av杨幂| 在线综合亚洲| 久久久久国产一区二区三区四区| 亚洲日本中文字幕区| 亚洲免费婷婷| 亚洲免费观看高清完整版在线观看熊 | 亚洲国内精品| 一区二区三区不卡视频在线观看| 在线电影欧美日韩一区二区私密| 亚洲国产精品成人精品| 欧美—级高清免费播放| 欧美一区二区视频在线观看| 欧美福利视频网站| 久久婷婷影院| 国产精品萝li| 最新中文字幕一区二区三区| 国内精品视频在线观看| 亚洲午夜伦理| 一区二区三欧美| 蜜臀av国产精品久久久久| 欧美在线视频一区| 欧美日韩国产天堂| 欧美黄色大片网站| 国产一区99| 亚洲一区免费观看| 亚洲视频在线播放| 欧美精品福利在线| 欧美国产乱视频| 一区二区三区亚洲| 性欧美videos另类喷潮| 亚洲制服av| 欧美日韩综合视频网址| 亚洲激情视频| 日韩视频永久免费| 免费不卡亚洲欧美| 男人的天堂成人在线| 国产一区二区欧美日韩| 国产午夜精品一区二区三区欧美 | 亚洲高清视频中文字幕| 国内精品久久久久久久影视麻豆 | 欧美韩日视频| 亚洲国产精品一区二区第一页 | 女仆av观看一区| 欧美激情一区二区三区在线视频观看| 国产亚洲制服色| 久久精品99无色码中文字幕| 久久免费视频观看| 伊人成人在线视频| 久久亚洲免费| 亚洲国产精品久久久久秋霞影院| 在线观看欧美一区| 美女网站在线免费欧美精品| 欧美激情1区2区| 日韩亚洲欧美在线观看| 欧美日韩一区二区国产| 亚洲天堂av电影| 久久久精品999| 伊人色综合久久天天五月婷| 女同性一区二区三区人了人一| 亚洲高清在线| 亚洲欧美日韩精品| 精品va天堂亚洲国产| 欧美.www| 亚洲一区二区黄| 久久亚洲精品视频| 亚洲精品国久久99热| 国产精品大片| 久久青草欧美一区二区三区| 最新精品在线| 久久精品人人做人人爽电影蜜月| 在线成人h网| 欧美性色aⅴ视频一区日韩精品| 亚洲欧美日韩一区二区在线| 老色批av在线精品| 亚洲线精品一区二区三区八戒| 国产精品日韩在线一区| 麻豆国产精品va在线观看不卡| 99re6这里只有精品| 久久久久免费视频| 一区二区av| 一区在线观看| 国产精品高潮呻吟久久| 久久精品五月| 亚洲社区在线观看| 欧美超级免费视 在线| 亚洲深夜福利| 最新亚洲一区| 黄色免费成人| 国产精品三级久久久久久电影| 玖玖国产精品视频| 欧美一级片久久久久久久| 91久久精品国产91久久性色tv| 久久国产精品久久久| 亚洲精品一区二区网址| 国产亚洲综合在线| 国产精品羞羞答答| 欧美女人交a| 久久婷婷国产综合国色天香| 亚洲综合精品自拍| aⅴ色国产欧美| 亚洲电影激情视频网站| 老司机aⅴ在线精品导航| 欧美在线亚洲在线| 亚洲女人av| 亚洲一区自拍| 亚洲少妇在线| 亚洲天堂成人在线观看| 99国产一区二区三精品乱码| 亚洲国产va精品久久久不卡综合| 国产一区二区三区久久久久久久久 | 亚洲私人影院在线观看| 日韩一级二级三级| 亚洲精品1区2区| 亚洲激情成人在线| 亚洲国产午夜| 亚洲国产欧美久久| 亚洲国产欧美不卡在线观看| 亚洲电影第三页| 亚洲国产日韩一区| 亚洲国产裸拍裸体视频在线观看乱了| 免费成人美女女| 欧美成人激情在线| 欧美激情黄色片| 欧美激情一区二区三区在线视频| 欧美黑人在线播放| 亚洲国产影院| 夜夜嗨一区二区三区| 日韩午夜在线电影| 亚洲天堂av综合网| 亚欧成人在线| 久久亚洲精品一区| 欧美精品激情blacked18| 欧美日韩国产综合久久| 欧美日韩一区二区三区在线看 | 欧美日韩一区二区在线视频| 欧美日韩你懂的| 国产精品免费福利| 国产最新精品精品你懂的| 经典三级久久| av不卡在线看| 欧美一区二区三区久久精品| 久久视频国产精品免费视频在线| 美女免费视频一区| 亚洲伦伦在线| 欧美在线免费| 欧美va亚洲va日韩∨a综合色| 欧美日韩免费观看一区二区三区| 欧美午夜一区二区| 国语自产在线不卡| 99国产精品99久久久久久| 亚洲欧美激情视频| 美女主播视频一区| 一本色道久久综合一区| 欧美一乱一性一交一视频| 久久综合久久88| 国产精品久久久久久亚洲毛片| 国内精品一区二区三区| 野花国产精品入口| 久久久亚洲一区| avtt综合网| 久久一区亚洲| 国产精品永久免费在线| 亚洲激情第一区| 久久国产日韩欧美| 亚洲乱码国产乱码精品精天堂| 久久国产精品99国产精| 欧美性开放视频| 亚洲欧洲日韩在线| 久久九九免费视频| 在线视频一区观看| 欧美电影免费观看大全| 好吊成人免视频| 小处雏高清一区二区三区| 最近看过的日韩成人| 久久久久久久999| 国产精品一区一区三区| 亚洲午夜av在线| 亚洲人成毛片在线播放女女| 久久精品国产亚洲一区二区| 国产精品一香蕉国产线看观看| 中文av字幕一区|