TA的每日心情 | 慵懶 2015-4-10 14:18 |
---|
簽到天數: 78 天 [LV.6]常住居民II
管理員
- 積分
- 3959
|
趕快加入我們來參與討論吧!
您需要 登錄 才可以下載或查看,沒有帳號?加入我們
x
原題: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;
}
|
|