AtCoder Beginner Contest #010 D問題 - 浮気予防

Source

AtCoder Beginner Contest #010
問題文

問題概要

とあるSNSに高橋くんと，それ以外に $N-1$ 人の人が登録しています．
高橋くんのIDは $0$ で，その他の人のIDは $1,2,\ldots,N-1$ です．
このSNS上で友人関係が与えられます．
友人関係は双方向であり，$x$ が $y$ の友人なら $y$ も $x$ の友人となります．
このSNSでは，自分と，自分の友人と，自分の友人の友人と，…，と何ステップかかっても良いので，友人関係で繋がっている人にメッセージを送ることができます．
高橋くんは $G$ 人の女の子，それぞれのIDが $P_1,P_2,\ldots,P_G$ の人にメッセージを送りたいです．
しかし，秘書のなぎさちゃんは，それを阻止し，その中の $1$ 人たりともメッセージを届かないようにするために，妨害工作を行います．
$1$ 回の妨害工作では，特定の $2$ 人の友人関係を解消する，または，高橋くん以外の任意の $1$ 人がログイン出来ないようにして，その人にメッセージが届いても見れなくする，という $2$ 通りのうちの片方を行うことができます．
全員にメッセージが届かなくするための妨害工作の最小回数を求める問題．

解法

高橋くんを支点として，$G$ 人の女の子から終点に向かって枝を張ったグラフの最小カットを求めれば良い．
最大流-最小カット定理より，最大流を求めれば良い．

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);}
void reader(int *x, int *y){reader(x);reader(y);}
void reader(int *x, int *y, int *z){reader(x);reader(y);reader(z);}
void writer(int x, char c){int i,sz=0,m=0;char buf[10];if(x<0)m=1,x=-x;while(x)buf[sz++]=x%10,x/=10;if(!sz)buf[sz++]=0;if(m)mypc('-');while(sz--)mypc(buf[sz]+'0');mypc(c);}

#define INT_INF 1000000000

#define INT_LIST_MAX_FLOW_NODE 202
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 N, G, E, P[120], A[20000], B[20000];

int main(){
  int i, j, k;
  int node, st, ed;
  int res;

  reader(&N,&G,&E);
  rep(i,G) reader(P+i);
  rep(i,E) reader(A+i,B+i);

  node = N;
  st = 0;
  ed = node++;
  intListMaxFlowEdgeInitAdv(node);
  rep(i,E) intListMaxFlowEdgeAdd(A[i],B[i],1,1);
  rep(i,G) intListMaxFlowEdgeAdd(P[i],ed,1,0);

  res = intListMaxFlow(node, st, ed);
  writer(res, '\n');

  return 0;
}

Current time: 2024年04月24日23時45分19秒
Last modified: 2014年06月26日21時32分14秒 (by laycrs)
Tags: Competitive_Programming AtCoder AtCoder_Beginner_Contest ABC010 ABC_D
トップページに戻る

Logged in as: unknown user (not login)

ログイン：