Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

February 2011 Challenge 2問目 - Coloring Colorable Graphs (チャレンジ形式) (この記事を編集する[管理者用])

Source

codechef February 2011 Challenge 2問目 (チャレンジ形式)
Problem Statement
February 2011 Challengeの参加記録

問題概要

ノード数N (500以下),枝数M (10000以下) の3彩色可能な無向グラフが与えられる.
できるだけ使用色数の少ない彩色を求める問題.

解法

とりあえず,アルゴリズムに適当なランダム性を入れてTLEにならない程度に何回も繰り返して一番良いものを出力する.
今回使った方法は,ノードを1つずつ塗れる最小の色番号に塗っていった.
次に塗るノードの選び方は,
 既に塗ったノードで隣接しているものの色の種類数が多いものから選ぶ
 同じなら,できるだけ次数の大きいものから選ぶ
3彩色可能であることを利用したアルゴリズムがあるらしい.

C言語のスパゲッティなコード (149.4pt)
#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)

#define RAND (rand()/(RAND_MAX+1.0))

int hp[510], hpi[510], d[510], hp_size;

void intHeapGoUp(int n){
  int k,m;
  if(!n) return;
  m=(n-1)/2;
  if(d[hp[m]]<=d[hp[n]]) return;
  k=hp[m]; hp[m]=hp[n]; hp[n]=k;
  hpi[hp[m]]=m; hpi[hp[n]]=n;
  intHeapGoUp(m);
}

void intHeapGoDown(int n){
  int k,m;
  m=2*n+1; if(m>=hp_size) return;
  if(hp_size>m+1 && d[hp[m]]>d[hp[m+1]]) m++;
  if(d[hp[m]]>=d[hp[n]]) return;
  k=hp[m]; hp[m]=hp[n]; hp[n]=k;
  hpi[hp[m]]=m; hpi[hp[n]]=n;
  intHeapGoDown(m);
}

void intHeapInsert(int n){
  hp[hp_size]=n; hpi[n]=hp_size++;
  intHeapGoUp(hp_size-1);
}

int intHeapDelete(void){
  int r=hp[0]; hpi[r]=-1;
  if( hp_size==1 ){hp_size--; return r;}
  hp[0]=hp[--hp_size]; hpi[hp[0]]=0;
  intHeapGoDown(0);
  return r;
}



void intIntSort(int d[],int m[],int s){int i=-1,j=s,k,t;if(s<=1)return;k=(d[0]+d[s-1])/2;for(;;){while(d[++i]<k);while(d[--j]>k);if(i>=j)break;t=d[i];d[i]=d[j];d[j]=t;t=m[i];m[i]=m[j];m[j]=t;}intIntSort(d,m,i);intIntSort(d+j+1,m+j+1,s-j-1);}


int n;
int edge[510][510], es[510];
int can[510];
int chk[510][510];
int ind[510], val[510], add[510];

int res, res_color[510];
int now, now_color[510];

int stat[510], res_stat[510], res_dame, res_loop;

int sum = 0;


int solve_2color(){
  int i,j,k;
  int st[510], st_size;

  rep(i,n) now_color[i]=-1;

  for(;;){
    rep(i,n) if(now_color[i]==-1) break;
    if(i==n) break;
    
    now_color[i]=0; st[0]=i; st_size=1;
    while(st_size){
      k = st[--st_size];
      rep(i,es[k]){
        j = edge[k][i];
        if(now_color[j]==-1){ now_color[j]=(now_color[k]^1); st[st_size++]=j; }
        if(now_color[j]==now_color[k]) return 0;
      }
    }
  }

  res=2; rep(i,n) res_color[i]=now_color[i];
}

int used[510];
int canb[510][3];
int aaaaa[510];
int step;
int uus[3];

int go_three_av(int st){
  int i,j,k,mx,stt,dame,ii;
  int g[3]={0,1,2}, v[3];

  if(st==n){
    res = 3;
    rep(i,n) res_color[i]=now_color[i];
    return 1;
  }

  stt = intHeapDelete();
  rep(i,3) v[i]=rand()%(1000+(uus[0]+uus[1]+uus[2]-uus[i])*200); intIntSort(v,g,3);

  if(step++ > 4200) return 0;
  rep(ii,3){
    i=g[ii];
    if(!canb[stt][i]){
      dame=0;
      rep(k,es[stt]){
        j=edge[stt][k]; if(used[j]) continue;
        canb[j][i]++;
        if(canb[j][i]==1){
          d[j]-=1000000; intHeapGoUp(hpi[j]);
        }
        if(canb[j][0]&&canb[j][1]&&canb[j][2]) dame++;
      }
      if(!dame){
        now_color[stt]=i; used[stt]=1; uus[i]++;
        if(go_three_av(st+1)) return 1;
        used[stt]=0; uus[i]--;
      }
      rep(k,es[stt]){
        j=edge[stt][k]; if(used[j]) continue;
        canb[j][i]--;
        if(canb[j][i]==0){
          d[j]+=1000000; intHeapGoDown(hpi[j]);
        }
      }
    }
  }

  intHeapInsert(stt);

  return 0;
}

int go_three(int st){
  int i,j,k,dame;
  int stt = ind[st];

  if(st==n){
    res = 3;
    rep(i,n) res_color[i]=now_color[i];
    return 1;
  }

  if(step++ > 10000) return 0;
  rep(i,3) if(!canb[stt][i]){
    dame=0;
    rep(k,es[stt]){
      j=edge[stt][k]; if(used[j]) continue;
      canb[j][i]++;
      if(canb[j][0]&&canb[j][1]&&canb[j][2]) dame++;
    }
    if(!dame){
      now_color[stt]=i; used[stt]=1;
      if(go_three(st+1)) return 1;
      used[stt]=0;
    }
    rep(k,es[stt]){
      j=edge[stt][k]; if(used[j]) continue;
      canb[j][i]--;
    }
  }

  return 0;
}

int main(){
  int i,ii,j,k,l,m,loop;
  int dame, mx;
  int size;

  srand(time(NULL));

  scanf("%d",&size);
  while(size--){
    scanf("%d%d",&n,&m);
    rep(i,n) es[i]=0;
    while(m--){
      scanf("%d%d",&i,&j); i--; j--;
      edge[i][es[i]++]=j;
      edge[j][es[j]++]=i;
    }
    res = n; rep(i,n) res_color[i]=i;

    if(res>3){
      solve_2color();
    }
    rep(loop,50){
      if(res>3){
        rep(i,n)rep(j,3)canb[i][j]=0;
        rep(i,n)used[i]=0;
        step=0;
        rep(i,3) uus[i]=0;
        
        rep(i,n) d[i] = rand()%(500+loop*20) - es[i]*1000;
        hp_size=0; rep(i,n) hpi[i]=-1; rep(i,n) intHeapInsert(i);
        
        go_three_av(0);
      }
    }
    rep(loop,3){
      if(res>3){
        rep(i,n) ind[i]=i, val[i]=-es[i]*5000 + (int)(RAND*1000), used[i]=0;
        rep(i,n)rep(j,3)canb[i][j]=0;
        step=0;
        intIntSort(val,ind,n);
        go_three(0);
      }
    }

    rep(loop,250){
      if(res<=3) break;
      now = 0; dame = 0;
      rep(i,n) rep(j,res+1) chk[i][j]=0;

      if(loop>5 && loop%2==0){
        rep(i,n){
          if(res_color[i]==res-1) d[i] = res_stat[i] - (int)(RAND*(4000+430*res_loop)), now_color[i]=-1;
          else                    d[i] = res_stat[i] + (int)(RAND*(1000+130*res_loop)), now_color[i]=-1;
        }
      } else {
        rep(i,n) d[i] = -es[i]*5000 + (int)(RAND*(1000+200*loop)), now_color[i]=-1;
      }

      rep(i,n) stat[i] = d[i];
      hp_size = 0; rep(i,n) hpi[i]=-1;
      rep(i,n) intHeapInsert(i);
      
      while(hp_size){
        j = intHeapDelete();

        for(i=0;;i++) if(chk[j][i]==0) break;
        now_color[j] = i;
        if(i+1 == now) dame++;
        if(i+1 > now) now = i+1, dame=0;
        if(now > res || (now==res && dame>=res_dame)) break;
        rep(m,es[j]){
          k = edge[j][m];
          if(now_color[k]==-1 && !chk[edge[j][m]][i]){
            chk[k][i]=1;
            d[k]-=300000;
            intHeapGoUp(hpi[k]);
          }
        }
      }

/*      printf("%d %d : %d %d\n",res,res_dame,now,dame);*/
      if(now < res || (now==res && dame<res_dame)){
        res = now; res_dame = dame;
        rep(i,n) res_color[i] = now_color[i];
        rep(i,n) res_stat[i] = stat[i];
        res_loop = loop;
/*        printf("%d %d\n",loop%2,loop);*/
      }
    }

    rep(i,n){
      if(i)putchar(' ');
      printf("%d",res_color[i]+1);
    }
    puts("");

    sum += res;
  }

/*  printf("sum = %d\n",sum);*/

  return 0;
}

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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