Codeforces Round #150 DIV1 B問題/DIV2 D問題 - Hydra

Source

Codeforces Round #150 DIV1 B問題 (1000pt)
Codeforces Round #150 DIV2 D問題 (2000pt)
Problem description

問題概要

ノード数 $N$，枝数 $M$ の無向グラフが与えられる．
正整数 $H$, $T$ が与えられる．
グラフの中で以下の条件1～4を満たす部分を1つ見つける問題．存在しないならそれを指摘する．

  1. ノード $u$ と $v$ は枝で結ばれている．
  2. $H$個のノード $U_1, U_2, \ldots, U_H$ はそれぞれノード $u$ と枝で結ばれている．
  3. $T$個のノード $V_1, V_2, \ldots, V_T$ はそれぞれノード $v$ と枝で結ばれている．
  4. $u, v, U_k, V_k$ はすべて異なる．

解法

枝で結ばれている $u$, $v$ のペアは全部試す．（このペアの数は $M$ 個しかない）
$u$ に直接つながっているノード数を $A$,
$v$ に直接つながっているノード数を $B$,
$u,v$ 両方に直接つながっているノード数を $C$ とする．
$A-C-1$ 個は $U_k$ としてだけに使えて，$B-C-1$ 個は $V_k$ としてだけに使えて，$C$ 個はどちらにも使える．($-1$ は $u,v$ が直接繋がっている分を除いている)
よって，$C$ が $\max(0, h-(A-C-1))+\max(0,t-(B-C-1))$ 以上であれば条件を満たす部分を作れる．
$u,v$ 両方に繋がっているノードを列挙するのは，$O(A+B)$ ぐらいでできる．
$A, C$ が小さくて，$B$ が大きい場合など，計算量が大きくなるので，$A+C-1$ が $H$ より小さいなどの場合は処理しない．
すると，$A+B$ が大きい時は必ず作れるようになるので，計算量が大きくて，更に解が見つからないような場合はないことがわかる．
計算時間量は $O((N+M)(H+T))$ 程度になる．(上で言った枝刈りをしないと $O(M(N+M))$ になってしまう)

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;
}

intVector edge[200000];

int chk[200000];

int both_ele[200000];
int acon_ele[200000];
int bcon_ele[200000];

int main(){
  int i,j,k,l,m,n;
  int h, t;
  int a, an, b;
  int acon, bcon, both, husoku;
  int fin = 0;

  rep(i,200000) edge[i] = intVectorNull();

  scanf("%d%d%d%d",&n,&m,&h,&t);
  rep(i,n) edge[i].size = 0;

  while(m--){
    scanf("%d%d",&i,&j);
    i--; j--;
    intVectorPushBack(edge+i,j);
    intVectorPushBack(edge+j,i);
  }

  rep(i,n) chk[i] = -1;
  
  rep(a,n) if(!fin) {
    if(edge[a].size - 1 < h) continue;
    rep(k,edge[a].size) chk[edge[a].d[k]] = a;
    
    rep(an,edge[a].size) if(!fin) {
      b = edge[a].d[an];
      if(edge[b].size - 1 < t) continue;
      both = 0;
      rep(k,edge[b].size){
        l = edge[b].d[k];
        if(chk[l]==a) both++;
      }
      acon = edge[a].size - both - 1;
      bcon = edge[b].size - both - 1;
      husoku = 0;
      if(h-acon > 0) husoku += h-acon;
      if(t-bcon > 0) husoku += t-bcon;

      if(husoku <= both){
        acon = bcon = both = 0;
        rep(k,edge[b].size){
          l = edge[b].d[k];
          if(chk[l]==a) both_ele[both++] = l;
          else if(l!=a) bcon_ele[bcon++] = l;
          chk[l] = n+1;
        }
        rep(k,edge[a].size){
          l = edge[a].d[k];
          if(chk[l] != n+1 && l!=b) acon_ele[acon++] = l;
        }

        while(acon < h) acon_ele[acon++] = both_ele[--both];
        while(bcon < t) bcon_ele[bcon++] = both_ele[--both];

        puts("YES");
        printf("%d %d\n", a+1, b+1);
        rep(i,h){
          if(i) putchar(' ');
          printf("%d",acon_ele[i]+1);
        }
        puts("");
        rep(i,t){
          if(i) putchar(' ');
          printf("%d",bcon_ele[i]+1);
        }
        puts("");
        fin = 1;
      }
    }
  }

  if(!fin) puts("NO");

  return 0;
}

Current time: 2024年04月17日00時26分08秒
Last modified: 2014年03月29日19時44分28秒 (by laycrs)
Tags: Competitive_Programming Codeforces CF150 CF_Div1_B CF_Div2_D
トップページに戻る

Logged in as: unknown user (not login)

ログイン：