スポンサーサイト

上記の広告は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;
}


スポンサーサイト

AOJ 2200 Mr. Rito Post Office

わからなくてぐぐりました。
http://d.hatena.ne.jp/sune2/20120719/1342723320

z[i]からz[i+1]に移動するとき、

陸路のみ
陸路 → 海路 → 陸路

のうち、どちらかのタイプの経路を辿る。

この考え方で実装するとうまくいきます。
dp[i][j]に対して、i-1のとき船があった場所をkとし
z[i-1] →(陸路)→ k →(海路)→ j →(陸路)→ z[i]
と進む事で船を場所jに移し自分はz[i]に移動することができます。
k==jのとき、すなわち船を移動させる必要がないときは、
必ずしもkを経由する必要がないのでz[i-1]からz[i]の陸最短路で良い。
これがわからなくて何回かWAくらった。

#define N 200
#define M 10000
#define R 1000
#define INF 1000000

int main(){
while(1){
int n,m,r;
int sea[N][N];
int land[N][N];
int dp[R][N];
int z[R];

scanf("%d%d",&n,&m);
if(!n&&!m)break;

//陸路と海路を別々に全点対最短路を求める
for(int i=0;i for(int j=0;j if(i==j){
sea[i][j] = 0;
land[i][j] = 0;
}else{
sea[i][j] = INF;
land[i][j] = INF;
}
}
}
for(int i=0;i int x,y,t;
char s;
scanf("%d %d %d %c",&x,&y,&t,&s);
if(s=='S'){
sea[x-1][y-1] = t;
sea[y-1][x-1] = t;
}else{
land[x-1][y-1] = t;
land[y-1][x-1] = t;
}
}
for(int k=0;k for(int i=0;i for(int j=0;j sea[i][j] = min(sea[i][j],sea[i][k]+sea[k][j]);
land[i][j] = min(land[i][j],land[i][k]+land[k][j]);
}
}
}

scanf("%d",&r);
for(int i=0;i scanf("%d",&z[i]);
z[i]--;
}

//dp[i][j]をjに船をおいてz[i]まで進んだ時にかかる最短の時間
for(int i=0;i dp[0][i] = sea[z[0]][i] + land[i][z[0]];
for(int j=1;j dp[j][i] = INF;
}
}
for(int i=1;i for(int j=0;j for(int k=0;k dp[i][j] = min(
dp[i][j],
dp[i-1][k]+land[z[i-1]][k]+sea[k][j]+land[j][z[i]] );
if(k==j) dp[i][j] = min(dp[i][j],dp[i-1][j]+land[z[i-1]][z[i]]);
}
}
}

int ans = INF;
for(int i=0;i ans = min(ans,dp[r-1][i]);
}
cout << ans << endl;
}
return 0;
}


AOJ 2249 Road Construction

ある町に最短で行く経路は複数あり、
そのうち最低のコストのものだけ残せば良い。
そこで最短経路で進んだ場合の
ある町とその一つ前の町をつなぐ道をpreに保存し
preのコストが最小になるように更新していく。

struct road{int to,dist,cost;};

int main(){
while(1){
int n,m;
vector roads[MAX_N];
int dist[MAX_N];
road pre[MAX_N];

scanf("%d%d",&n,&m);
if(!n&&!m)break;

for(int i=0;i int u,v,d,c;
scanf("%d%d%d%d",&u,&v,&d,&c);
roads[u-1].push_back((road){v-1,d,c});
roads[v-1].push_back((road){u-1,d,c});
}

fill(dist,dist+n,INF);
priority_queue, greater

> que;
dist[0] = 0;
que.push(P(0,0));
while(que.size()){
P p = que.top(); que.pop();
int d = p.first;
int pos = p.second;
//cout << pos+1 << endl;
if(d>dist[pos]) continue;
for(int i=0;i int to = roads[pos][i].to;
int co = roads[pos][i].dist + dist[pos];
//cout << pos+1 <<"->" << to+1<< endl;
if(dist[to]>co){
pre[to] = roads[pos][i];
dist[to] = co;
que.push(P(dist[to],to));
}else if(dist[to]==co){
if(pre[to].cost>roads[pos][i].cost){
pre[to] = roads[pos][i];
}
}
}
}

int sum=0;
for(int i=1;i sum += pre[n-i].cost;
}
cout << sum << endl;
}
}

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