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

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>
            欧美激情女人20p| 模特精品在线| 在线亚洲成人| 国产精品乱人伦一区二区| 亚洲一区视频在线观看视频| 99精品福利视频| 国产欧美日韩另类视频免费观看| 久久精视频免费在线久久完整在线看| 久久国产黑丝| 亚洲精品国产精品久久清纯直播| 亚洲精品午夜| 国产亚洲精品bt天堂精选| 久久一区二区三区av| 欧美a级片网| 亚洲欧美日韩在线高清直播| 欧美伊人影院| 亚洲靠逼com| 午夜亚洲激情| 亚洲巨乳在线| 性欧美超级视频| 亚洲免费av片| 欧美在线免费看| 日韩一二三在线视频播| 亚洲欧美视频在线观看| 亚洲国产精品成人综合| 国产精品99久久久久久有的能看 | 亚洲欧美激情视频| 亚洲电影第1页| 中文欧美字幕免费| 亚洲国产视频直播| 午夜精品三级视频福利| 亚洲精品免费网站| 久久精品国产69国产精品亚洲 | 亚洲成人资源网| 亚洲手机成人高清视频| 亚洲黄色免费| 欧美在线3区| 亚洲欧美日韩在线一区| 欧美精品系列| 欧美福利一区二区| 国产一区观看| 亚洲午夜一二三区视频| 99在线精品免费视频九九视| 久久精品国产综合精品| 亚洲欧美国产三级| 欧美日韩国产三级| 亚洲三级免费电影| 在线观看精品| 久久国产精品亚洲va麻豆| 午夜视频一区二区| 国产精品久久久久久久9999| 亚洲激情在线观看视频免费| 在线日韩中文| 久久亚洲春色中文字幕| 久久九九免费| 国产一区二区黄| 亚洲欧美一区二区原创| 香蕉乱码成人久久天堂爱免费| 欧美日韩在线精品| av成人国产| 亚洲一区视频在线| 国产精品久久久久久久久久ktv | 久久国产88| 久久在线免费观看| 今天的高清视频免费播放成人| 欧美在线三级| 另类亚洲自拍| 亚洲国产婷婷| 欧美成人网在线| 日韩系列在线| 欧美一级午夜免费电影| 国产欧美午夜| 久久免费视频网站| 亚洲电影免费观看高清完整版| 亚洲人成亚洲人成在线观看| 欧美激情2020午夜免费观看| 91久久久精品| 亚洲自拍偷拍麻豆| 国产日韩欧美一区在线| 久久国产直播| 最新国产の精品合集bt伙计| 亚洲午夜久久久| 国产日产亚洲精品| 久久久www成人免费精品| 亚洲成色最大综合在线| 9国产精品视频| 国产欧美精品| 久久中文精品| aaa亚洲精品一二三区| 欧美中文字幕在线观看| 一区二区三区在线高清| 欧美精品福利在线| 亚洲欧美变态国产另类| 欧美1区2区视频| 亚洲视频视频在线| 国产一区二区三区四区老人 | 亚洲精选视频在线| 久久久www成人免费无遮挡大片| 一区二区亚洲精品国产| 欧美激情第3页| 欧美一进一出视频| 亚洲日本va在线观看| 羞羞漫画18久久大片| 91久久久久久久久| 国产精品视频免费观看| 亚洲美女少妇无套啪啪呻吟| 国产精品亚发布| 欧美成年人在线观看| 亚洲男人第一网站| 亚洲精品国久久99热| 久久视频在线看| 亚洲午夜视频在线| 亚洲激情欧美| 国产一区深夜福利| 国产精品xnxxcom| 美女爽到呻吟久久久久| 午夜精品一区二区三区在线播放 | 一本色道久久综合狠狠躁篇的优点| 国产伦精品一区二区三区在线观看 | 亚洲一区二区三区在线观看视频 | 久久综合五月天婷婷伊人| 亚洲一卡久久| 黑人巨大精品欧美一区二区小视频| 欧美激情欧美激情在线五月| 午夜精品久久久久久久99水蜜桃| 亚洲国产视频一区二区| 久久亚洲美女| 欧美在线啊v一区| 亚洲永久网站| 一区二区三区四区国产| 亚洲精品老司机| 亚洲福利视频一区| 狠狠综合久久av一区二区小说| 国产精品日日摸夜夜添夜夜av| 欧美另类69精品久久久久9999| 美国十次了思思久久精品导航| 欧美一区国产一区| 亚洲欧美在线看| 亚洲国产视频一区| 伊人久久大香线蕉综合热线 | 欧美激情性爽国产精品17p| 久久午夜视频| 久久久精品999| 久久久久久一区二区| 久久国产精彩视频| 久久精品国产综合精品| 久久激情五月激情| 久久久91精品国产一区二区精品| 香蕉乱码成人久久天堂爱免费| 亚洲一区激情| 欧美在线视频免费| 久久精品综合| 久久亚洲国产精品日日av夜夜| 久热精品在线视频| 欧美不卡三区| 欧美激情一二区| 欧美日韩免费高清一区色橹橹| 欧美视频在线视频| 国产精品综合不卡av| 国产一区视频网站| 亚洲激情婷婷| 亚洲主播在线观看| 久久久精品日韩欧美| 女人天堂亚洲aⅴ在线观看| 欧美激情亚洲视频| 亚洲精选视频在线| 午夜性色一区二区三区免费视频| 久久国产精品99久久久久久老狼| 久久久久久电影| 欧美不卡激情三级在线观看| 欧美日韩精品免费| 国产一区二区三区丝袜| 亚洲日韩中文字幕在线播放| 亚洲一区二区成人| 久久综合一区| 99视频在线精品国自产拍免费观看 | 伊人影院久久| 亚洲精品一区在线| 欧美一区二区三区免费观看| 美女网站久久| 一本久久知道综合久久| 欧美亚洲综合网| 久久精品国产亚洲5555| 欧美www在线| 亚洲伊人色欲综合网| 久久伊伊香蕉| 国产精品网红福利| 亚洲精品偷拍| 亚洲欧美精品在线| 欧美激情黄色片| 小嫩嫩精品导航| 欧美剧在线观看| 在线免费观看视频一区| 午夜亚洲一区| 99视频精品免费观看| 美女视频黄a大片欧美| 国产一区二区看久久| 亚洲欧美日韩第一区| 亚洲欧洲日韩综合二区| 久久久五月婷婷|