AtCoder Regular Contest #041 D問題 - 辺彩色

Source

AtCoder Regular Contest #041
問題文

問題概要

$N$ 個のノードと $M$ 個の枝からなる連結な無向グラフが与えられる.自己ループや多重辺はない.
最初に好きなノードから初めて,隣接するノードに自由にいくらでも移動することができる.
その時,奇数回目の移動では,通った枝の色を赤く塗り,偶数回目の移動では,通った枝の色を青く塗る(すでに枝に色が塗られていたら上書きする).
それぞれの辺について目標とする色が与えられるので,すべての辺が目標の色となるような状態を達成できるかどうかを判定する問題.

解法

時間の向きを逆にして考える.
つまり,一度色を塗ったら,その枝を通っても色が上書きされずの通ることができる,という問題になる.
その場合は,偶奇が一致した場合のみその枝を通ることができて,一度通った枝は(偶奇に関わらず)自由に通ることができる.
奇数長の閉路が完成したら,その閉路を通ることで偶奇を反転できるから,なんとでもできる.
また奇数長の閉路ができないなら,偶奇を反転させる方法はないから,貪欲に通れる枝を通ってすべての枝を通ることができるかを調べれば良い.
実装的には,今の移動回数が偶数回か奇数回かでノードを分割して,ノード数が $2$ 倍されたグラフで,始点を全て試して,DFSして,始点の偶奇反転したノードにたどり着けるか,全ての枝の始点にたどり着けるものが見つかればYesとした.
また,偶奇反転したノードを全て調べることにして,一度たどり着いたことのあるノードを始点とするものは試さないようにしたら,多少速くなった(強連結成分分解して,枝が入ってくるノードは始点にしないとかするともうちょっと速くなりそう).

C++によるスパゲッティなソースコード

#include<bits/stdc++.h>
using namespace std;
 
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
 
#define mygc(c) (c)=getchar_unlocked()
#define mypc(c) putchar_unlocked(c)
 
void reader(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
int reader(char c[]){int i,s=0;for(;;){mygc(i);if(i!=' '&&i!='\n'&&i!='\r'&&i!='\t'&&i!=EOF) break;}c[s++]=i;for(;;){mygc(i);if(i==' '||i=='\n'||i=='\r'||i=='\t'||i==EOF) break;c[s++]=i;}c[s]='\0';return s;}
template <class T, class S> void reader(T *x, S *y){reader(x);reader(y);}
template <class T, class S, class U> void reader(T *x, S *y, U *z){reader(x);reader(y);reader(z);}
 
void writer(const char x[], char c){int i;for(i=0;x[i]!='\0';i++)mypc(x[i]);mypc(c);}
template<class T> void writerLn(T x){writer(x,'\n');}
 
void* setDirectEdge(int N, int M, int A[], int B[], int **es, int ***edge, void *workMemory){int i;*es=(int*)workMemory;*edge=(int**)((*es)+N);(*edge)[0]=(int*)((*edge)+N);rep(i,N)(*es)[i]=0;rep(i,M)(*es)[A[i]]++;REP(i,1,N)(*edge)[i]=(*edge)[i-1]+(*es)[i-1];workMemory=(void*)((*edge)[N-1]+(*es)[N-1]);rep(i,N)(*es)[i]=0;rep(i,M)(*edge)[A[i]][(*es)[A[i]]++]=B[i];return workMemory;}
void getDist(int N, int root, int *es, int **edge, int dist[], void *mem){int i,j,k,*q,s,z;q=(int*)mem;rep(i,N)dist[i]=-1;dist[root]=0;s=0;z=1;q[0]=root;while(z){i=q[s++];z--;rep(j,es[i]){k=edge[i][j];if(dist[k]>=0)continue;dist[k]=dist[i]+1;q[s+z++]=k;}}}
 
char memarr[17000000]; void *mem = memarr;
 
int N, M;
int *es, **edge;
 
int A[2000], B[2000]; char C[2002];
 
int node, from[4000], to[4000], dist[4000];
 
int main(){
  int i, j, k, ii;
 
  reader(&N,&M);
  rep(i,M) reader(A+i,B+i,C+i), A[i]--, B[i]--;
 
  node = 2*N;
  rep(i,M){
    if(C[i]=='r'){
      from[2*i]   = A[i]; to[2*i]   = B[i]+N;
      from[2*i+1] = B[i]; to[2*i+1] = A[i]+N;
    } else {
      from[2*i]   = A[i]+N; to[2*i]   = B[i];
      from[2*i+1] = B[i]+N; to[2*i+1] = A[i];
    }
  }
 
  mem = setDirectEdge(node, 2*M, from, to, &es, &edge, mem);
 
  rep(i,node){
    getDist(node, i, es, edge, dist, mem);
    rep(j,M) if(dist[from[2*j]]==-1 && dist[from[2*j+1]]==-1) break;
    if(j==M){ writerLn("Yes"); return 0; }
    if(dist[i<N?i+N:i-N]!=-1){ writerLn("Yes"); return 0; }
  }
 
  writerLn("No");
 
  return 0;
}

C++によるスパゲッティなソースコード(一度訪れたノードは始点にしない)

#include<bits/stdc++.h>
using namespace std;
 
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
 
#define mygc(c) (c)=getchar_unlocked()
#define mypc(c) putchar_unlocked(c)
 
void reader(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
int reader(char c[]){int i,s=0;for(;;){mygc(i);if(i!=' '&&i!='\n'&&i!='\r'&&i!='\t'&&i!=EOF) break;}c[s++]=i;for(;;){mygc(i);if(i==' '||i=='\n'||i=='\r'||i=='\t'||i==EOF) break;c[s++]=i;}c[s]='\0';return s;}
template <class T, class S> void reader(T *x, S *y){reader(x);reader(y);}
template <class T, class S, class U> void reader(T *x, S *y, U *z){reader(x);reader(y);reader(z);}
 
void writer(const char x[], char c){int i;for(i=0;x[i]!='\0';i++)mypc(x[i]);mypc(c);}
template<class T> void writerLn(T x){writer(x,'\n');}
 
void* setDirectEdge(int N, int M, int A[], int B[], int **es, int ***edge, void *workMemory){int i;*es=(int*)workMemory;*edge=(int**)((*es)+N);(*edge)[0]=(int*)((*edge)+N);rep(i,N)(*es)[i]=0;rep(i,M)(*es)[A[i]]++;REP(i,1,N)(*edge)[i]=(*edge)[i-1]+(*es)[i-1];workMemory=(void*)((*edge)[N-1]+(*es)[N-1]);rep(i,N)(*es)[i]=0;rep(i,M)(*edge)[A[i]][(*es)[A[i]]++]=B[i];return workMemory;}
void getDist(int N, int root, int *es, int **edge, int dist[], void *mem){int i,j,k,*q,s,z;q=(int*)mem;rep(i,N)dist[i]=-1;dist[root]=0;s=0;z=1;q[0]=root;while(z){i=q[s++];z--;rep(j,es[i]){k=edge[i][j];if(dist[k]>=0)continue;dist[k]=dist[i]+1;q[s+z++]=k;}}}
 
char memarr[17000000]; void *mem = memarr;
 
int N, M;
int *es, **edge;
 
int A[2000], B[2000]; char C[2002];
 
int node, from[4000], to[4000], dist[4000];
int ind[4000], reach[4000];
 
int main(){
  int i, j, k, ii;
 
  reader(&N,&M);
  rep(i,M) reader(A+i,B+i,C+i), A[i]--, B[i]--;
 
  node = 2*N;
  rep(i,M){
    if(C[i]=='r'){
      from[2*i]   = A[i]; to[2*i]   = B[i]+N;
      from[2*i+1] = B[i]; to[2*i+1] = A[i]+N;
    } else {
      from[2*i]   = A[i]+N; to[2*i]   = B[i];
      from[2*i+1] = B[i]+N; to[2*i+1] = A[i];
    }
  }
 
  mem = setDirectEdge(node, 2*M, from, to, &es, &edge, mem);
 
  rep(i,node) ind[i] = i;
  random_shuffle(ind, ind+node);
 
  rep(ii,node){
    i = ind[ii];
    if(reach[i]) continue;
    getDist(node, i, es, edge, dist, mem);
    rep(j,M) if(dist[from[2*j]]==-1 && dist[from[2*j+1]]==-1) break;
    if(j==M){ writerLn("Yes"); return 0; }
    rep(j,N) if(dist[j]!=-1 && dist[j+N]!=-1){ writerLn("Yes"); return 0; }
    rep(j,node) if(dist[j]!=-1) reach[j] = 1;
  }
 
  writerLn("No");
 
  return 0;
}

Current time: 2017年09月25日07時54分51秒
Last modified: 2015年07月09日07時03分07秒 (by laycrs)
Tags: Competitive_Programming AtCoder AtCoder_Regular_Contest ARC041 ARC_D
トップページに戻る

Logged in as: unknown user (not login)

ログイン: