Entries

スポンサーサイト (この記事を編集する[管理者用])

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

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1442-c30cc417
この記事にトラックバックする(FC2ブログユーザー)

Beta Round #25 D問題 - Roads not only in Berland (この記事を編集する[管理者用])

Source

Codeforces Beta Round #25 D問題
Problem description

問題概要

ノード数n,枝数n-1の無向グラフが与えられる.
枝を1本消して,枝を好きな場所に1本付け加えるという操作を繰り返して連結なグラフにしたい.
最小手数と,その方法を1個求める問題.
nは1000以下.

解法

付け加える枝と,消す枝を別々に求めれば良い.
union findで連結成分を調べて,それぞれの連結成分がつながるように枝を付け加える.
後は,DFSをして閉路になっている部分の枝を探して消す.
以下のソースでは,O(n^2)程度でも問題ないので,全ての枝に対して,消しても連結成分の数が減らないなら消すということを行った.

C言語のスパゲッティなコード
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

void unionInit(int d[],int s){int i;rep(i,s)d[i]=i;}
int unionGet(int d[],int n){int t=n,k;while(d[t]!=t)t=d[t];while(d[n]!=n)k=d[n],d[n]=t,n=k;return n;}
int unionConnect(int d[],int a,int b){a=unionGet(d,a);b=unionGet(d,b);if(a==b)return 0;d[a]=b;return 1;}

int main(){
  int i,j,k,l,m,n;
  int a[1200], b[1200], unused[1200];
  int ind[1200];
  int cnt[1200];
  int res_a[1200], res_b[1200], res_c[1200], res_d[1200];
  int shima;
  int res, bef;

  scanf("%d",&n);
  m=n-1;
  rep(i,m) scanf("%d%d",a+i,b+i), a[i]--, b[i]--;

  unionInit(ind,n);
  rep(i,m) unionConnect(ind,a[i],b[i]);

  shima = 0;
  rep(i,n) cnt[unionGet(ind,i)]=1;
  rep(i,n) shima += cnt[i];

  res=0; bef=-1;
  rep(i,n) if(cnt[i]){
    if(bef>=0){
      res_c[res] = bef; res_d[res++] = i;
    }
    bef = i;
  }

  res=0;
  rep(k,m) unused[k]=0;
  
  rep(k,m){
    unionInit(ind,n);
    rep(i,m) if(unused[i]==0) if(i!=k) unionConnect(ind,a[i],b[i]);
    rep(i,n) cnt[i]=0;
    rep(i,n) cnt[unionGet(ind,i)]=1;
    j=0; rep(i,n) j+=cnt[i];
    if(j==shima){
      unused[k]=1;
      res_a[res]=a[k]; res_b[res++]=b[k];
    }
  }

  printf("%d\n",res);
  rep(i,res) printf("%d %d %d %d\n",res_a[i]+1,res_b[i]+1,res_c[i]+1,res_d[i]+1);

  return 0;
}

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1442-c30cc417
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。