kmjp's blog

競技プログラミング参加記です

TopCoder SRM 721 Div1 Hard Apocalypse、Div2 Hard ApocalypseEasy

これMediumでいいと思うんだけども。
https://community.topcoder.com/stat?c=problem_statement&pm=14710
https://community.topcoder.com/stat?c=problem_statement&pm=14714

問題

木を成すN頂点の無向グラフが与えられる。
初期状態で一部の点にトークンが乗っている。

これらのトークンをTターンの間に動かすことを考える。
各ターンでは、各トークンを任意の順番で最大1回だけ隣接する点に移動させることができる。
なお、Div1では途中2個以上のトークンが同じ点に存在してはならない。Div2では存在してもよい。

最終的に、トークンをもともとトークンがなかった場所に移動するようにしたい。
Tターンの間、最大何個そのようなトークンを得られるか。

解法

最大フローとして解くことができる。
各頂点に対応して、フロー上で2*N*T個の頂点を作る。
すなわち、1ターンに対し元の1頂点に対し2個フロー上で点を作る。

1つ目の頂点から2つ目の頂点について、同じ位置または隣接する頂点に対し、移動可能なので容量1の辺を張る。
次に、Div1においては頂点にトークンが複数存在できないため、2つ目の頂点から、次ターンの対応する1つ目の頂点に容量1の辺を張る。
(Div2の時はその制限がないので容量無限大の辺を張る)

後はsourceとsinkをつなげてフローを流せば終わり。

template<class V> class MaxFlow_Ford {
public:
	struct edge { int to,reve;V cap;};
	static const int MV = 10000;
	vector<edge> E[MV];
	int vis[MV];
	void add_edge(int x,int y,V cap,bool undir=false) {
		E[x].push_back((edge){y,(int)E[y].size(),cap});
		E[y].push_back((edge){x,(int)E[x].size()-1,undir?cap:0});
	}
	V dfs(int from,int to,V cf) {
		V tf;
		if(from==to) return cf;
		vis[from]=1;
		FORR(e,E[from]) if(vis[e.to]==0 && e.cap>0 && (tf = dfs(e.to,to,min(cf,e.cap)))>0) {
			e.cap -= tf;
			E[e.to][e.reve].cap += tf;
			return tf;
		}
		return 0;
	}
	V maxflow(int from, int to) {
		V fl=0,tf;
		while(1) {
			ZERO(vis);
			if((tf = dfs(from,to,numeric_limits<V>::max()))==0) return fl;
			fl+=tf;
		}
	}
};

class Apocalypse {
	public:
	int maximalSurvival(vector <int> p, vector <int> position, int t) {
		int N=p.size()+1;
		vector<int> E[51];
		int B[51]={};
		int i,j;
		for(i=1;i<N;i++) {
			E[i].push_back(p[i-1]);
			E[p[i-1]].push_back(i);
		}
		
		MaxFlow_Ford<int> mf;
		
		FORR(p,position) mf.add_edge(0,100+p,1), B[p]=1;
		FOR(i,t) {
			int st=100+i*100;
			FOR(j,N) FORR(e,E[j]) mf.add_edge(st+j,st+50+e,1);
			FOR(j,N) mf.add_edge(st+j,st+50+j,1), mf.add_edge(st+50+j,st+100+j,1);
		}
		FOR(i,N) if(B[i]==0) mf.add_edge((t+1)*100+i,1,1);
		return mf.maxflow(0,1);
	}
}

まとめ

これがHardとなると、ちょっとSRMがネタ切れなのか心配になってくるな…。