TopCoderOpen 2015 Round2A Medium FoxMeeting

これは解けても良かったかもなぁ。
http://community.topcoder.com/stat?c=problem_statement&pm=13776

問題

N頂点の木を成すグラフが与えられる。
各辺は長さを持つ無向辺である。

このうち幾つかの異なる頂点にキツネがいる。
各キツネを動かし、キツネがいる頂点が連結している(間にキツネがいない頂点が挟まらない)ようにしたい。

各キツネの移動する最大距離の最小値を求めよ。

解法

頂点数は50なので、先にWarshall-Floyedを用いて全点間距離を求めておく。
後は最大距離の最小値を二分探索で求めていこう。

先に最大距離が定まると、各キツネの移動可能な頂点が定まる。
あとは、「キツネがいる頂点が連結している」の条件を満たせるか考えればよい。

総当たりで中心となる頂点を仮定しよう。
各キツネはその頂点に向けて移動する。
キツネが所定の最大距離内で中心点に到達できない場合、できるだけ近い頂点に移動する。

ここで、「キツネがいる頂点が連結している」の条件を満たすには、このキツネが寄れるもっとも近い頂点に対し、そこから中心に至る各頂点に１匹以上キツネがいればよいことになる。
この考察より、キツネがいなければならない頂点が列挙できる。
ここまで来ると、「キツネの初期位置」「キツネがいなければならない頂点」を頂点とし、「キツネの移動できる頂点」を辺とした二部マッチング問題になるので、後は最大マッチングが「キツネがいなければならない頂点」をカバーできるか判定すればよい。

template<class V> class MaxFlow_Ford {
public:
	struct edge { int to,reve;V cap;};
	static const int MV = 200;
	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 FoxMeeting {
	public:
	ll mat[51][51];
	int N;
	vector<int> F;
	
	bool ok(int v) {
		int i,x,y,tar;
		
		FOR(tar,N) {
			set<int> S,S2;
			FORR(r,F) {
				x = r;
				FOR(i,N) if(mat[r][i]<=v && mat[i][tar]<mat[x][tar]) x=i;
				S.insert(x);
			}
			FORR(r,S) {
				FOR(i,N) if(mat[r][tar]==mat[r][i]+mat[i][tar]) S2.insert(i);
			}
			MaxFlow_Ford<int> mf;
			FORR(r,F) mf.add_edge(0,r+1,1);
			FORR(r,S2) {
				mf.add_edge(r+51,101,1);
				FOR(i,N) if(mat[i][r]<=v) mf.add_edge(i+1,r+51,1);
			}
			if(mf.maxflow(0,101)==S2.size()) return true;
		}
		
		return false;
	}
	
	int maxDistance(vector <int> A, vector <int> B, vector <int> L, vector <int> foxes) {
		N=A.size()+1;
		F=foxes;
		
		int i,x,y;
		FORR(r,F) r--;
		
		FOR(x,N) FOR(y,N) mat[x][y]=1LL<<60;
		FOR(x,N) mat[x][x]=0;
		FOR(i,A.size()) mat[A[i]-1][B[i]-1]=mat[B[i]-1][A[i]-1]=L[i];
		
		FOR(i,N) FOR(x,N) FOR(y,N) mat[x][y]=min(mat[x][y],mat[x][i]+mat[i][y]);
		
		int ret=(1<<30)-1;
		for(i=29;i>=0;i--) if(ok(ret-(1<<i))) ret -= 1<<i;
		return ret;
	}
}

まとめ

本番ヘタにこの問題が頭に浮かんでしまい、DP解かと思ってしまった。
TopCoder SRM 604 Div1 Medium FoxConnection - kmjp's blog