Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

Round #147 DIV2 D問題 - T-decomposition (この記事を編集する[管理者用])

Source

Codeforces Round #147 DIV2 D問題 (2000pt)
Problem description

問題概要

ノード数N (100000以下) の木sが与えられるので,以下の条件を満たす木tの中で,w(t)が最小となるtを1つ求める問題.
 tの各ノードは,sのノードの部分集合を表す.tの各ノードの重さをその部分集合の元の数とする
 w(t)はtに含まれるノードのうち,重さ最大のノードの重さ
 すべてのsの枝(a,b)について,aもbも含むような部分集合からなるノードがtになければいけない
 すべてのsのノードaについて,tのノードのうち対応する部分集合がaを含むものだけを取り出すと連結な木になっている

解法

絶対w(t)=2にすることができる.つまり,tのそれぞれノードは,sの枝に対応する.
tで枝をはれるのは,sの枝で端点を共有するようなものの間だけ使って,tを木にする.
なんでも良い.
自分の解法は,すこし勘違いしてたので,sの次数1のノードを根にして,sを根付き木にして,葉から順番になぞって,すべての枝に対して,その親側から更に根に遡る枝へとtで枝を張った.

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

typedef struct struct_vector_int{ int size,mem; int *d; }intVector;
intVector intVectorNull(){ intVector v; v.size=v.mem=0; return v; }

void intVectorMemoryExpand(intVector *v){
  int i, *t, m;
  m=v->mem*2; if(m<5) m=5;
  t=(int*)malloc(m*sizeof(int));
  rep(i,v->size) t[i]=v->d[i];
  if(v->mem) free(v->d);
  v->d=t; v->mem=m;
}

void intVectorPushBack(intVector *v,int add){
  if(v->mem==v->size) intVectorMemoryExpand(v);
  v->d[(v->size)++] = add;
}

int a[100000], b[100000];
intVector edge[100000], num[100000];
int deg[100000];
int up[100000], upedge[100000];

void gen(int node, int bef, int e){
  int i, k;
  up[node] = bef;
  upedge[node] = e;

  rep(i,edge[node].size){
    k = edge[node].d[i];
    if(k==bef) continue;
    gen(k, node, num[node].d[i]);
  }

  if(e>=0){
    rep(i,edge[node].size){
      k = edge[node].d[i];
      if(k==bef) continue;
      printf("%d %d\n",e,upedge[k]);
    }
  }
}

int main(){
  int i,j,k,l,m,n;
  int root;

  rep(i,100000) edge[i] = num[i] = intVectorNull();

  scanf("%d",&n);

  rep(i,n) deg[i] = 0;

  rep(i,n-1){
    scanf("%d%d",&j,&k);
    j--; k--;
    a[i] = j; b[i] = k;
    intVectorPushBack(edge+j, k);
    intVectorPushBack(edge+k, j);
    intVectorPushBack(num+j, i+1);
    intVectorPushBack(num+k, i+1);

    deg[j]++; deg[k]++;
  }

  printf("%d\n",n-1);
  rep(i,n-1) printf("2 %d %d\n",a[i]+1,b[i]+1);

  rep(root,n) if(deg[root]==1) break;
  gen(root, -1, -1);

  return 0;
}

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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