竹園論壇

標題: a129 - 最小生成樹 [打印本頁]

---

作者: Sylveon    時間: 2014-5-9 08:13
標題: a129 - 最小生成樹
原題：http://zerojudge.tw/ShowProblem?problemid=a129
AC：http://zerojudge.tw/Submissions?problemid=a129&account=lfs92002

這題是我一年級在TOI時自己在宿舍研究出來的，一開始的版本用的是Priority Queue，結果呢隔天模考就考MST(連結)，爽賺一題！我自己還滿喜歡MST這系列的題目，貪心加邊的方法可以轉換成數種模型，其MST的變化題也很多，我之後再一一貼出，至少有一種會出在T16第二次留社考，好好加油吧。
這題是MST的裸題，可以參考我社課講義 MST 篇，我有圖解了算法，只是一部分是我用投影片的螢光筆畫的，沒有保留，將就一下吧！
http://forum.tfcis.org/forum.php?mod=viewthread&tid=91

正常寫法
/**********************************************************************************/
/*  Problem: a129 "最小生成樹" from                                          */
/*  Language: CPP (1177 Bytes)                                                    */
/*  Result: AC(0.6s, 3.1MB) judge by this@ZeroJudge                               */
/*  Author: lfs92002 at 2013-03-17 22:11:37                                       */
/**********************************************************************************/


#include<algorithm>
#include<string.h>
#include<cstdio>
#include<iostream>
using namespace std;

int uni_data[100000];
int group;
void init(int size)
{
        for(int a=0;a<size;a++)uni_data[a]=a;
        group=size;
}

int find(int n)
{
        if(uni_data[n]==n)return n;
        uni_data[n]=find(uni_data[n]);
        return uni_data[n];
}

int same(int a,int b)
{
        return find(a)==find(b);
}

int _union(int a,int b)
{
        uni_data[find(b)]=find(a);
        group--;
}


struct _edge{
        int s,e,w;
        _edge(int _s=0,int _e=0,int _w=0):s(_s),e(_e),w(_w){
        }
};
bool operator< (const _edge &a,const _edge &b)
{
        return a.w<b.w;
}

//priority_queue<_edge> edge;

_edge edge[200000];
int tn;

long long kruskal()
{
        long long MinCost=0;
        int i=0;
        while(i<tn)
        {
                if(!same(edge[i].s,edge[i].e))
                {
                        _union(edge[i].s,edge[i].e);
                        MinCost+=edge[i].w;
                }
                ++i;
        }
        if(group!=1)return -1;
        return MinCost;
}


int main()
{
        int d,e,s,n,w;
        while(~scanf("%d%d",&d,&e))
        {
                tn=e;
                init(d);
                for(int a=0;a<e;a++)
                {
                        scanf("%d%d%d",&edge[a].s,&edge[a].e,&edge[a].w);
                }
                sort(edge,edge+e);
                printf("%lld\n",kruskal());
        }
        return 0;
}
有點失敗的解法，一年級研究的，足足比上面慢了快20%
/**********************************************************************************/
/*  Problem: a129 "最小生成樹" from                                          */
/*  Language: CPP (1183 Bytes)                                                    */
/*  Result: AC(0.7s, 6.1MB) judge by this@ZeroJudge                               */
/*  Author: lfs92002 at 2013-03-16 23:09:18                                       */
/**********************************************************************************/


#include<queue>
#include<string.h>
#include<cstdio>
#include<iostream>
using namespace std;

int uni_data[100000];
int group;
void init(int size)
{
        for(int a=0;a<size;a++)uni_data[a]=a;
        group=size;
}

int find(int n)
{
        if(uni_data[n]==n)return n;
        uni_data[n]=find(uni_data[n]);
        return uni_data[n];
}

int same(int a,int b)
{
        return find(a)==find(b);
}

int _union(int a,int b)
{
        uni_data[find(b)]=find(a);
        group--;
}


struct _edge{
        int s,e,w;
        _edge(int _s=0,int _e=0,int _w=0):s(_s),e(_e),w(_w){
        }
};
bool operator< (const _edge &a,const _edge &b)
{
        return a.w>b.w;
}

priority_queue<_edge> edge;

long long kruskal()
{
        long long MinCost=0;
        while(!edge.empty())
        {
                _edge t=edge.top();
                edge.pop();
                if(!same(t.s,t.e))
                {
                        _union(t.s,t.e);
                        MinCost+=t.w;
                //        cout<<"UNI"<<t.s<<' '<<t.e<<" COST "<<MinCost <<"G"<<group<<endl;
                }
        }
        if(group!=1)return -1;
        return MinCost;
}


int main()
{
        int d,e,s,n,w;
        while(~scanf("%d%d",&d,&e))
        {
                init(d);
                for(int a=0;a<e;a++)
                {
                        scanf("%d%d%d",&s,&n,&w);
                        edge.push(_edge(s,n,w));
                }
                printf("%lld\n",kruskal());
        }
        return 0;
}

---

歡迎光臨 竹園論壇 (http://forum.tfcis.org/)

Powered by Discuz! X3.2