CDOJ：1636-梦后楼台高锁，酒醒帘幕低垂（Kruskal+暴力）

梦后楼台高锁，酒醒帘幕低垂

Time Limit: 3000/1000MS (Java/Others)

Memory Limit: 65535/65535KB (Java/Others)

Submit Status

给你一个有n个点和m条边的无向连通图,每条边都有一个权值w.

我们定义，对于一条路径，它的Charm value为该路径上所有边的权值的最大值与最小值的差.

询问从1到n的所有路径的Charm value的最小值.

Input

第一行有两个整数n,m(1≤n≤200,n−1≤m≤1000)n,m(1≤n≤200,n−1≤m≤1000)，表示该图有n个点和m条边.

接下来m行，每行三个整数u,v,w(1≤u,v≤n,1≤w≤1000000)，表示点u和点v之间有一条权值为w的边.

Output

输出一个数，即从1到n的所有路径的Charm value的最小值.

Sample Input

4 4

3 4 1

2 3 2

1 2 4

2 4 3

Sample Output

1

---

解题心得：

1. 比赛的时候遇到这个题，第一个反应是kruskal的最小生成树，写了一会儿发现不太对，1到n这么多的路径，要最大值减最小值最小，怎么弄呢，想了半天发现没啥思路，结果是暴力，天哪。
2. 先按照路径排一个序，然后枚举以每一条路径为起点跑kurskal，当发现1和n已经连接起来的时候就停止，记录一下值，将所有跑出来的结果取一个最小值就可以了。

---

#include<bits/stdc++.h>

using namespace std;

const int maxn = 1000;

struct PATH

{

    int s,e,len;

}path[1000100];

int n,m,father[maxn];

bool cmp(PATH a,PATH b)

{

    return a.len < b.len;

}

void init()

{

    for(int i=0;i<m;i++)

        scanf("%d%d%d",&path[i].s,&path[i].e,&path[i].len);

    sort(path,path+m,cmp);

}

int find(int x)

{

    if(x == father[x])

        return x;

    return father[x] = find(father[x]);

}

void merge(int x,int y)

{

    int fx = find(x);

    int fy = find(y);

    father[fy] = fx;

}

int get_min(int pos)

{

    int Min,Max;

    bool flag = false;

    Min = path[pos].len;

    for(int i=pos;i<m;i++)

    {

        Max = path[i].len;

        merge(path[i].s,path[i].e);

        if(find(1) == find(n))//1和n已经连接起来

            break;

    }

    if(find(1) == find(n))

        flag = true;

    if(flag)

        return Max-Min;

    return 0x3f3f3f3f;

}

int main()

{

    while(scanf("%d%d",&n,&m) != EOF)

    {

        init();

        int Min = 0x7f7f7f7f;

        for(int i=0;i<m;i++)

        {

            for(int i=1;i<=n;i++)

                father[i] = i;

            int temp = get_min(i);//枚举每一个边为起点开始连接路径

            Min = min(Min,temp);

        }

        printf("%d\n",Min);

    }

    return 0;

}