TopCoder SRM 447 Div1 Medium PeopleYouMayKnow

問題

友達関係のグラフが与えられる。
友達関係は反射的（A→Bが友達ならB→Aも友達）であるが、推移的ではない（A→Bが友達かつB→Cが友達でもA→Cが友達とは限らない）。

このグラフにおいて、n-friendを以下のように定義する。
AとBが友達ならばAとBはn-friend
AとCがn-1friendかつCとBが友達のとき、AとBはn-friend

このグラフから、何人かを取り除いて、person1とperson2が3-friendでないようにしたい。
最低で何人取り除く必要があるか求めよ。

制約条件

n≦40

方針

二人をA,Bとして、A-C-BのCのような、二人両方の知り合いは必ず取り除かなければならない。
まずはこれをあらかじめ除く。

すると、A-C-D-Bのような、AからBへの長さ3のパスがいくつかできるグラフになる。
これをAを湧き出し、Bを吸い込みとするようなグラフで、それぞれの辺の容量が1であるようなグラフと見たとき、このグラフの最小カットが除かなければならない人数の最小値である。
これはグラフの最大流に等しいため、最大流を求めればよい。

ソースコード

class PeopleYouMayKnow {
	public:
	int maximalScore(vector <string> friends, int person1, int person2) 
	{
		rep(i,MAX_V)G[i].clear();
		bool e[50][50]={};
		int need[50]={},n=friends.size();
		
		rep(i,n)rep(j,n)e[i][j]=friends[i][j]=='Y';
		int ans=0;
		rep(i,n)if(e[person1][i]&&e[i][person2]){
			ans++;
			rep(j,n)e[i][j]=e[j][i]=0;
		}
		need[person1]=1; need[person2]=4;
		rep(i,n)if(e[person1][i])need[i]=2;
		else if(e[i][person2])need[i]=3;
		rep(i,n)rep(j,n)if(need[i]&&need[j]&&need[i]<need[j]&&e[i][j])add_edge(i,j,1);
		ans+=max_flow(person1,person2);
		return ans;
	}
};