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

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>
            欧美日韩一区二区三区免费看 | 免费不卡在线观看| 国产丝袜美腿一区二区三区| 先锋影院在线亚洲| 性感少妇一区| 在线电影欧美日韩一区二区私密| 久久综合伊人77777| 欧美寡妇偷汉性猛交| 日韩视频中文| 亚洲专区在线| …久久精品99久久香蕉国产| 亚洲欧洲午夜| 国产精品女人毛片| 欧美成人午夜剧场免费观看| 欧美激情一区在线| 欧美一区视频在线| 欧美a级在线| 性久久久久久久| 麻豆精品传媒视频| 午夜欧美精品久久久久久久| 久久伊人亚洲| 亚洲欧美综合精品久久成人| 久久综合一区| 午夜视频久久久| 免费视频一区| 久久精品免费电影| 欧美日韩国产一区二区| 久久亚洲风情| 久久激情综合| 欧美日韩黄色一区二区| 久久精品国产亚洲一区二区三区| 久久夜色精品国产欧美乱极品| 9i看片成人免费高清| 欧美一区中文字幕| 亚洲欧美日本另类| 欧美激情在线观看| 老司机精品久久| 国产伦精品免费视频| 亚洲娇小video精品| 好吊日精品视频| 亚洲无吗在线| 一区二区三区四区在线| 美女精品在线| 可以看av的网站久久看| 国产欧美日韩综合一区在线观看| 最新日韩中文字幕| 最新国产乱人伦偷精品免费网站| 欧美中文字幕在线播放| 午夜免费在线观看精品视频| 欧美日韩国产色视频| 亚洲国产视频直播| 亚洲国产精品va在线观看黑人| 亚洲午夜小视频| 在线亚洲精品| 欧美日本一区| 亚洲乱码国产乱码精品精98午夜| 亚洲片区在线| 暖暖成人免费视频| 欧美大尺度在线| 1024精品一区二区三区| 久久久久一区二区三区四区| 久久久蜜臀国产一区二区| 国产日韩在线视频| 欧美一区二区女人| 久久久蜜桃精品| 在线观看视频免费一区二区三区| 久久久www成人免费精品| 久久人人97超碰精品888| 国内精品美女在线观看| 久久国产欧美| 免费永久网站黄欧美| 亚洲国产精品一区二区久| 久久综合999| 亚洲品质自拍| 亚洲免费网站| 国产亚洲精品bt天堂精选| 久久aⅴ国产欧美74aaa| 欧美成人69av| 99精品国产热久久91蜜凸| 欧美日韩国产免费观看| 亚洲一区成人| 久久久久久欧美| 亚洲激情欧美| 国产精品不卡在线| 久久99在线观看| 亚洲国产另类久久久精品极度| 一区二区三区日韩欧美| 国产欧美一区二区在线观看| 久久久久国色av免费观看性色| 欧美xx视频| 亚洲一区二区三区精品在线观看| 国产乱肥老妇国产一区二 | 一区二区三区四区在线| 久久精品视频在线看| 亚洲欧洲偷拍精品| 国产精品美女久久久久av超清| 久久精品免费观看| 亚洲免费久久| 久久女同精品一区二区| 99精品国产一区二区青青牛奶| 国产欧美精品在线观看| 欧美99在线视频观看| 午夜在线观看免费一区| 亚洲欧洲日夜超级视频| 久久久噜噜噜| 亚洲一级在线| 亚洲国产高清自拍| 国产欧美日韩视频| 欧美另类高清视频在线| 久久久精品国产免大香伊| 夜夜爽99久久国产综合精品女不卡 | 欧美jizzhd精品欧美巨大免费| 一区二区三区国产盗摄| 欧美a级在线| 久久黄色小说| 亚洲综合色婷婷| 亚洲精品综合精品自拍| 狠狠狠色丁香婷婷综合久久五月| 欧美香蕉大胸在线视频观看| 欧美高潮视频| 久久久久久91香蕉国产| 亚洲欧美成人精品| 日韩网站在线| 亚洲精品一区在线观看| 欧美激情免费在线| 免费日韩av电影| 久久亚洲影音av资源网| 久久成人一区| 欧美在线亚洲| 欧美一区二区三区在| 亚洲免费在线播放| 亚洲综合色噜噜狠狠| 亚洲一级二级在线| 在线视频欧美日韩| 亚洲一区二区三区免费观看| 亚洲免费观看在线视频| 亚洲免费观看高清完整版在线观看熊| 在线看国产日韩| 激情久久一区| 亚洲国产精品久久人人爱蜜臀 | 欧美日韩八区| 欧美片在线播放| 欧美极品在线视频| 欧美精品在欧美一区二区少妇| 欧美成人激情视频免费观看| 欧美v日韩v国产v| 欧美精品999| 欧美日韩另类字幕中文| 欧美视频免费在线| 国产精品久久久久久久久久尿| 欧美午夜在线一二页| 国产精品久久久久久五月尺| 国产精品一区二区视频| 国产午夜久久久久| 在线国产日韩| 亚洲精品黄网在线观看| 欧美在线视频二区| 久久精品色图| 免费在线看成人av| 免费成人av资源网| 欧美全黄视频| 国产精品欧美久久| 激情久久久久久久久久久久久久久久 | 欧美在线资源| 模特精品在线| 国产精品久久久久久久午夜片| 国产欧美91| 亚洲黄页一区| 亚洲一区二区三区在线视频| 欧美在线中文字幕| 亚洲国产mv| 亚洲一区二区三区在线看| 久久精品噜噜噜成人av农村| 欧美另类视频| 国产一区二区三区直播精品电影| 亚洲黄网站在线观看| 亚洲欧美激情四射在线日 | 欧美一区二区啪啪| 免费看亚洲片| 中文高清一区| 免费成人激情视频| 国产女人水真多18毛片18精品视频| 亚洲第一中文字幕在线观看| 亚洲色图在线视频| 欧美成黄导航| 亚洲欧美网站| 欧美日韩国产美女| 在线视频国产日韩| 小处雏高清一区二区三区| 欧美va天堂va视频va在线| 一区二区三区国产| 久久精品日韩一区二区三区| 欧美先锋影音| 99国产精品99久久久久久粉嫩 | 亚洲一区综合| 最新日韩av| 美女免费视频一区| 国语自产在线不卡| 午夜在线播放视频欧美| 亚洲精品免费一区二区三区|