Uva 1395 slim span

解題：
Kruskal 變化題：窮舉所有最小邊做Kruskal (從原來邊1~m,2~m,3~m直到無法形成MST(總編數不夠)
Code：

#include<stdio.h>

#include<stdlib.h>

#include<iostream>

#include<algorithm>

#include<queue>

#define MAXN 10005

using namespace std;

typedef pair<int ,int> ii;

priority_queue<ii,vector<ii>,greater<ii> > edges[5000];

int n,m;

int g[MAXN];

int initial()

{

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

    {

        g[i]=i;

    }

}

int Find(int a)

{

    if(a!=g[a])

    {

        g[a]=Find(g[a]);

    }

    return g[a];

}

void Union(int a,int b)

{

    if(Find(a)!=Find(b))

    {

        g[g[a]]=g[b];

    }

}

int kruskal(priority_queue<pair<int,ii> > &pq)

{

    priority_queue<pair<int,ii> > tmpq(pq);

    int diff=10000000;

    int minn=10000000;

    while(!tmpq.empty())

    {

        vector<int> path;

        pair<int,ii> tmptop;

        initial();

        priority_queue<pair<int,ii> > ttt(tmpq);

        while(!ttt.empty())

        {

            pair<int,ii> top=ttt.top();

            ttt.pop();

            int u=top.second.first,v=top.second.second;

            if(Find(u)!=Find(v))

            {

                Union(u,v);

                path.push_back(0-top.first);

            }

            if(path.size()==n-1)

            {

                diff=path.back()-path.front();

                break;

            }

        }

        minn=min(diff,minn);

        tmptop=tmpq.top();

        tmpq.pop();

    }

    return minn;

}

int main()

{

    while(cin>>n>>m && (n!=0||m!=0))

    {

        priority_queue<pair<int,ii> > pq;

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

        {

            int a,b,c;

            cin>>a>>b>>c;

            pq.push(make_pair(0-c,ii(a,b)));

        }

        initial();

        int ans=kruskal(pq);

        if(ans==10000000) cout<<"-1"<<endl;

        else cout<<ans<<endl;

    }

    return 0;

}