Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

February 2011 Cook-Off 2問目 - Dance Floor Energy (この記事を編集する[管理者用])

Source

codechef February 2011 Cook-Off 2問目
Problem Statement
codechef February 2011 Cook-Offの参加記録

問題概要

ダンス会場.開いている時間は0~Lまで.(Lは1000000000以下)
合計でB人の男性と,G人の女性が参加する.(BとGは200以下)
それぞれの人は,気になっている異性のリストが与えられており,お互いに気になっている人同士しかダンスできない.
それぞれの人が,会場に到着する時間,会場から出て行く時間が与えられる.
すべての瞬間で,最も多くのペアがダンスを踊っていると仮定して,
 kペアがダンスを踊っていた時間 (k = 0, 1, ..., MIN(B,G))
をすべて求める問題.

解法

それぞれの瞬間で最も多くのペアが何ペアか,というのは最大流で求まる.
後は,人が抜ける,人が追加されるなどグラフを修正しながら最大流を流す.

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 INT_INF 1000000000

#define INT_LIST_MAX_FLOW_NODE 502
int intLmfEdge[INT_LIST_MAX_FLOW_NODE][INT_LIST_MAX_FLOW_NODE];
int intLmfFlow[INT_LIST_MAX_FLOW_NODE][INT_LIST_MAX_FLOW_NODE];
int intLmfInv[INT_LIST_MAX_FLOW_NODE][INT_LIST_MAX_FLOW_NODE];
int intLmfEdgeSize[INT_LIST_MAX_FLOW_NODE],intLmfEdgeMemory[INT_LIST_MAX_FLOW_NODE];
int intLmfLevel[INT_LIST_MAX_FLOW_NODE];
int intLmfQueue[INT_LIST_MAX_FLOW_NODE];

void intListMaxFlowLevelize(int n,int st,int ed){
  int i,j,k,t;
  int q_st,q_end;
  rep(i,n) intLmfLevel[i]=-1; intLmfLevel[st]=0; q_st=0; q_end=1; intLmfQueue[0]=st;
  while(q_st!=q_end){
    i=intLmfQueue[q_st++]; t=intLmfLevel[i]+1;
    rep(j,intLmfEdgeSize[i]) if(intLmfFlow[i][j]){
      k=intLmfEdge[i][j]; if(intLmfLevel[k]!=-1) continue;
      intLmfLevel[k]=t; intLmfQueue[q_end++]=k; if(k==ed) return;
    }
  }
}

int intListMaxFlowFlow(int i,int ed,int lim){
  int j,k,ret=0,t,s,ji;
  if(i==ed) return lim;
  rep(j,intLmfEdgeSize[i]) if(intLmfFlow[i][j]){
    k=intLmfEdge[i][j]; if(intLmfLevel[k]<=intLmfLevel[i]) continue;
    s=lim; if(s>intLmfFlow[i][j]) s=intLmfFlow[i][j];
    t=intListMaxFlowFlow(k,ed,s); if(!t) continue;
    ret+=t; lim-=t; ji=intLmfInv[i][j];
    intLmfFlow[i][j]-=t; intLmfFlow[k][ji]+=t;
    if(!lim) break;
  }
  if(lim) intLmfLevel[i]=-1;
  return ret;
}

/* Dinic(Dinitz) */
/* 制約: n<=INT_LIST_MAX_FLOW_NODE, st!=ed */
int intListMaxFlow(int n,int st,int ed){
  int ret=0;
  for(;;){
    intListMaxFlowLevelize(n,st,ed); if(intLmfLevel[ed]==-1) break;
    ret += intListMaxFlowFlow(st,ed,INT_INF);
  }
  return ret;
}

void intListMaxFlowEdgeInit(){
  int i;
  rep(i,INT_LIST_MAX_FLOW_NODE) intLmfEdgeSize[i]=0;
}

void intListMaxFlowEdgeInitAdv(int n){
  int i;
  rep(i,n) intLmfEdgeSize[i]=0;
}

/* 制約: n1!=n2 */
void intListMaxFlowEdgeAdd(int n1,int n2,int f1,int f2){
  int s1=intLmfEdgeSize[n1]++, s2=intLmfEdgeSize[n2]++;
  intLmfEdge[n1][s1]=n2; intLmfEdge[n2][s2]=n1;
  intLmfFlow[n1][s1]=f1; intLmfFlow[n2][s2]=f2;
  intLmfInv[n1][s1]=s2;  intLmfInv[n2][s2]=s1;
}

int flow_cancel(int st,int ed,int flow){
  int i,j;
  rep(i,intLmfEdgeSize[st]) if(intLmfEdge[st][i]==ed){
    j = intLmfInv[st][i];
    intLmfFlow[st][i] += flow;
    intLmfFlow[ed][j] -= flow;
    return 1;
  }
  return 0;
}

int flow_delete(int st,int ed,int flow){
  int i,j;
  rep(i,intLmfEdgeSize[st]) if(intLmfEdge[st][i]==ed){
    intLmfFlow[st][i] -= flow;
    return 1;
  }
  return 0;
}



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 main(){
  int i,j,k,l,m,n,flow,mm;
  int B,G,sum,mn,res[410],T;
  int node,ss,ee;
  int st[410],ed[410];
  int edge[410][410], es[410];
  int tm[810], eve[810], sz, ok[410];
  int size;

  scanf("%d",&size);
  while(size--){
    scanf("%d%d%d",&B,&G,&T);
    mn=B; if(mn>G) mn=G;
    rep(i,mn+1) res[i]=0;
    sum=B+G;

    rep(i,sum) rep(j,sum) edge[i][j]=0;
    rep(i,sum){
      scanf("%d%d%d",st+i,ed+i,es+i);
      rep(j,es[i]){
        scanf("%d",&k);
        if(i<B) k+=B;
        edge[i][k]=1;
      }
    }

    sz = 0;
    rep(i,sum){
      tm[sz] = st[i]; eve[sz]=i; sz++;
      tm[sz] = ed[i]; eve[sz]=10000+i; sz++;
    }

    intIntSort(tm,eve,sz);

    node = sum; ss=node++; ee=node++;
    flow=0;
    
    intListMaxFlowEdgeInitAdv(node);
    rep(i,B)  REP(j,B,sum) if(edge[i][j] && edge[j][i])
      intListMaxFlowEdgeAdd(i,j,1,0);

    rep(k,sz-1){
      if(eve[k]<10000){
        m = eve[k];
        if(m<B) intListMaxFlowEdgeAdd(ss,m,1,0);
        else    intListMaxFlowEdgeAdd(m,ee,1,0);
        flow += intListMaxFlow(node,ss,ee);
      } else {
        mm = m = eve[k]-10000;
        rep(i,intLmfEdgeSize[m]){
          n = intLmfEdge[m][i];
          if(n==ss || n==ee) continue;
          if( (m<B && intLmfFlow[m][i]==0) || (m>=B && intLmfFlow[m][i]==1) ) break;
        }
        if(i < intLmfEdgeSize[m]){
          flow--;
          if(m>n) i=m, m=n, n=i;
          flow_cancel(ss,m,1);
          flow_cancel(m,n,1);
          flow_cancel(n,ee,1);
          if(mm<B) flow_delete(ss,mm,1); else flow_delete(mm,ee,1);
          flow += intListMaxFlow(node,ss,ee);
        } else {
          if(mm<B) flow_delete(ss,mm,1); else flow_delete(mm,ee,1);
        }
      }
      res[flow] += tm[k+1]-tm[k];
    }
    REP(i,1,mn+1) T -= res[i]; res[0] = T;

    rep(i,mn+1){
      if(i) putchar(' ');
      printf("%d",res[i]);
    }
    puts("");
  }
  
  return 0;
}

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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