【最小生成樹-Kruskal】POJ 3522 Slim Span

POJ 3522 Slim Span

• 題意：給一幅圖，要求找到其中一顆生成樹使這個生成樹上的最大邊權和最小邊權的內插補點最小。
• 思路：核心是用Kruskal算法找最小生成樹。

1. 我們先将所有邊的邊權排序，我們要構成樹，并且要使得樹的最大最小邊權內插補點盡量小，是以我們在排好序的邊中取盡可能連續的V-1條邊來構成樹。
2. E條邊，最多最多我們隻能有E-(V-1)+1=E-V+2棵樹。我們依次周遊一遍找最小內插補點即可。
3. 需要注意的是，排好序後的邊，前面可以構成一棵樹，但是越往後可能就不能構成樹，是以我們找最小內插補點的時候要注意是不是存在樹，是以我們要加上判斷條件再來存最小內插補點。
4. 還有就是，如果ans并沒有更新，也就是說E-V+2<0，也就是給出的條件不能構成樹。如果Kruskal(1)==-1也就是說給出的邊雖然滿足了E-V+2<0，但仍然一棵樹都不能構成。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstring>
#include <string>
#include <vector>
#include <set>
#include <stack>
#include <list>
#include <map>
#define P(x) x>0?x:0
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int maxV=105;
const int maxE=5e3;
int V,E;
int root[maxV],high[maxV],size[maxV];
int Find(int x) { return root[x]==x ? x : root[x]=Find(root[x]); }
int Same(int x,int y) { return Find(x)==Find(y); }
void Merge(int x,int y)
{
    x=Find(x);
    y=Find(y);
    if(high[x]<high[y]||size[x]<size[y])
    {
        root[x]=y;
        size[y]+=size[x];
    }
    else
    {
        root[y]=x;
        size[x]+=size[y];
        if(high[x]==high[y]) high[x]++;
    }
}
struct node{
    int u,v,w;
    node(int a=0,int b=0,int c=0):u(a),v(b),w(c){}
    friend bool operator < (node n1,node n2) { return n1.w<n2.w; }
}ve[maxE];
void init()
{
    for(int i=1;i<=V;i++) { root[i]=i; high[i]=0; size[i]=1; }
}
int Kruskal(int x)
{
    init();
    int begin=ve[x].w,edge_num=0;
    for(int i=x;i<=E;i++)
    {
        if(!Same(ve[i].u,ve[i].v))
        {
            Merge(ve[i].u,ve[i].v);
            edge_num++;
            if(edge_num==V-1)
                return ve[i].w-begin;
        }
    }
    return -1;
}
int main()
{
    while(~scanf("%d%d",&V,&E) && (V||E))
    {
        init();
        for(int i=1;i<=E;i++)
        {
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            ve[i]=node(a,b,c);
        }
        sort(ve+1,ve+E+1);
        int ans=INF;
        for(int i=1;i<=E-V+2;i++)
            if(Kruskal(i)!=-1)
                ans=min(ans,Kruskal(i));
        if(ans==INF||Kruskal(1)==-1) printf("-1\n");
        else printf("%d\n",ans);
    }
    return 0;
}
           

【吐槽POJ】

今天上午交的題，哎呀媽呀，從八點多鐘就開始炸，一直wating交不了，等了一天(⊙﹏⊙)