Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

April 2011 Challenge 2問目 - Generalized Independent Sets (この記事を編集する[管理者用])

Source

codechef April 2011 Challenge 2問目
Problem Statement
April 2011 Challengeの参加記録

問題概要

ノード数n (500以下),枝数m (2000以下)の無向グラフが与えられる.
各ノードには重みf(v)が与えられており,f(v)の値は0以上1以下の実数.
サイクルで,サイクルに含まれるノードの重みの和がfloow(L/2)を超えるものを1つ出力する問題.
ただし,Lはサイクルの長さ (含まれるノードの数).
もしくは,そのようなサイクルが存在しないならそれを指摘する.
枝の両端が同じノードになっていることはないと仮定して良い.
枝(u,v)があるなら,u-v-uは長さ2のサイクルとして認める.

解法

条件を満たす長さ2のサイクルがなければ,偶数長のサイクルは作れない.
また,その時,全て重みに-0.5を足したとき,無限に重みの和が小さくなるようなサイクルは存在しない.(*)
よって,長さ奇数で,重みに全部-0.5足したとき,重みの和が-0.5を超えるようなサイクルを探せば良い.
これは,ダイクストラで求めることが可能.ダイクストラは(*)の性質により無限ループに陥ることはない.
(が,長さが負の枝は有りうるので,同じノードを1回しか処理しないダイクストラではない)
現在までに奇数個のノードを経由したか,偶数個のノードを経由したか,でノード数を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)

#define EPS 1e-10


void doubleHeapGoUp(int n,int hp[],int hpi[],double d[]){
  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;
  doubleHeapGoUp(m,hp,hpi,d);
}

void doubleHeapGoDown(int n,int hp[],int hpi[],int hp_size,double d[]){
  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;
  doubleHeapGoDown(m,hp,hpi,hp_size,d);
}

void doubleHeapInsert(int n,int hp[],int hpi[],int *hp_size,double d[]){
  hp[*hp_size]=n; hpi[n]=(*hp_size)++;
  doubleHeapGoUp((*hp_size)-1,hp,hpi,d);
}

int doubleHeapDelete(int hp[],int hpi[],int *hp_size,double d[]){
  int r=hp[0]; hpi[r]=-1;
  if( *hp_size==1 ){(*hp_size)--; return r;}
  hp[0]=hp[--(*hp_size)]; hpi[hp[0]]=0;
  doubleHeapGoDown(0,hp,hpi,*hp_size,d);
  return r;
}


double f[510];
int edge[510][510], es[510];
int a[2100], b[2100];

double d[1200];
int hp[1200], hpi[1200], hp_size, back[1200];

int res[10000], res_size;
int rtm[10000], rtm_size;

int main(){
  int i,j,k,l,m,n,len;
  int st, ed, ok, oks[510], chk[510];
  int x,y;
  double go;
  int size;

  scanf("%d",&size);
  while(size--){
    scanf("%d%d",&n,&m);
    rep(i,n) scanf("%lf",f+i);
    rep(i,n) es[i]=0;
    rep(k,m) scanf("%d%d",a+k,b+k);

    rep(k,m){
      i=a[k]; j=b[k];
      if(i>j) l=a[k], a[k]=b[k], b[k]=l;
      edge[i][es[i]++]=j;
      edge[j][es[j]++]=i;
    }

    rep(k,m) if( f[a[k]] + f[b[k]] > 1+EPS ) break;
    if(k<m){
      printf("Bad Cycle: %d %d -1\n",a[k],b[k]);
      continue;
    }

    res_size = n+1;

    rep(k,m){
      int cnt=0;
      rep(i,2*n) d[i] = 1e100, hpi[i] = -1; hp_size = 0;
      st = a[k]; ed = b[k];
      
      d[st] = -f[st]; back[st] = -1;
      doubleHeapInsert(st,hp,hpi,&hp_size,d);

      while(hp_size){
        x = doubleHeapDelete(hp,hpi,&hp_size,d);

        rep(i,es[x%n]){
          if(x<n){
            y = edge[x][i] + n;
            go = d[x] - f[y-n];
          } else {
            y = edge[x-n][i];
            go = d[x] - f[y] + 1;
          }

          if(d[y] > go+EPS){
            d[y] = go+EPS; back[y]=x;
            if(hpi[y]>=0) doubleHeapGoUp(hpi[y],hp,hpi,d);
            else          doubleHeapInsert(y,hp,hpi,&hp_size,d);
          }
        }

        if(d[ed] < -EPS) break;
        if(cnt++ > n*2 + m*2) break;
      }

/*      printf("dijkstra %d %d\n",st,ed);
      rep(i,n*2) printf("%d %lf\n",i,d[i]);*/
      if(d[ed] < -EPS){
        rtm_size = 0;
        while(ed>=0){
          rtm[rtm_size++] = ed%n;
          ed = back[ed];
        }

        rep(i,n) chk[i] = 0;
        rep(i,rtm_size) chk[rtm[i]]++;
        rep(i,n) if(chk[i]>1) break;

        if(i==n){
          res_size= rtm_size;
          rep(i,res_size) res[i] = rtm[i];
          break;
        }
      }
    }

    if(res_size==n+1){ puts("Ok"); continue; }
    printf("Bad Cycle: ");
    rep(i,res_size) printf("%d ",res[i]);
    puts("-1");
  }

  return 0;
}

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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