スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

AOJ 2224 Save your cat

フェンスを辺と考え、閉路をなくせばよいので、
閉路をなくす → 全域木の辺の数を最小にする
壊す長さを最小に → 長い辺から使っていく
と考えると最小全域木と同じような解き方で解けます。

UnionFind木を使ったクラスカル法で解く場合。
fenceをcostの大きさで降順にソートして、
使わなかったfenceのcostの和を出力します。

struct fence{
int u,v;
double cost;
};

//union-find木
#define N 10000
int par[N];
int urank[N];
void init(int n){
for(int i=0;i par[i] = i;
urank[i] = 0;
}
}
int find(int x){
if(par[x] == x){
return x;
}else{
return par[x] = find(par[x]);
}
}
void unite(int x,int y){
x = find(x);
y = find(y);
if(x==y)return;

if(urank[x] par[x] = y;
}else{
par[y] = x;
if(urank[x]==urank[y])urank[x]++;
}
}
bool same(int x,int y){
return find(x)==find(y);
}

//2点間の距離を求める
double distance(int x1,int y1,int x2,int y2){
return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}

//fenceはcostの大きさで降順ソートしたいので不等号はこの向き
bool cmp(const fence &a,const fence &b){
return a.cost > b.cost;
}

int main(){
int n,m;
P piles[N];
vector fences;

scanf("%d%d",&n,&m);
for(int i=0;i int x,y;
scanf("%d%d",&x,&y);
piles[i] = P(x,y);
}
for(int i=0;i int p,q;
scanf("%d%d",&p,&q);
p--;q--;
double c = distance(piles[p].first,piles[p].second,piles[q].first,piles[q].second);
fences.push_back((fence){p,q,c});
}

double sum = 0;
init(n);
sort(fences.begin(),fences.end(),cmp);
for(int i=0;i int u = fences[i].u;
int v = fences[i].v;
if(same(u,v)){
sum += fences[i].cost;
}else{
unite(u,v);
}
}

printf("%.3f\n",sum);


return 0;
}



プリム法で解く場合。
プリム法は最小全域"木"をつくるので、森をつくるため、
使われていない頂点に対して何度かプリム法で木を作ります。
(森に対してプリム法を使う方法これしかおもいつかない……)
あと、この実装方法だと同じ辺を何度もみることがあるので
クラスカル法の時のように素直にsumを出力できません。

typedef pair P;
typedef pair Pdi;
#define N 10000
struct fence{
int to;
double cost;
};

//2点間の距離を求める
double distance(int x1,int y1,int x2,int y2){
return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}

int main(){
int n,m;
P piles[N];
vector fences[N];
double costsum = 0;

scanf("%d%d",&n,&m);
for(int i=0;i int x,y;
scanf("%d%d",&x,&y);
piles[i] = P(x,y);
}
for(int i=0;i int p,q;
scanf("%d%d",&p,&q);
p--;q--;
double c = distance(piles[p].first,piles[p].second,piles[q].first,piles[q].second);
fences[p].push_back((fence){q,c});
fences[q].push_back((fence){p,c});
costsum += c;
}

double sum = 0;
bool used[N];
fill(used,used+n,false);

priority_queue que;
for(int i=0;i if(!used[i]){
que.push(Pdi(0,i));
while(que.size()){
Pdi p = que.top(); que.pop();
int pos = p.second;
if(used[pos]) continue;
used[pos] = true;
sum += p.first;
for(int j=0;j que.push(Pdi(fences[pos][j].cost,fences[pos][j].to));
}
}
}
}

printf("%.3f\n",costsum-sum);


return 0;
}


コメントの投稿

非公開コメント

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。