TopCoder SRM 633 Div1 Medium DoubleTree

このフローは思いつかないわ。
http://community.topcoder.com/stat?c=problem_statement&pm=13359

問題

0～(N-1)の番号を振られた頂点からなる木が２組ある。
また、各頂点番号に対応するスコアscore[i]が与えられる。

これらの頂点群のサブセットのうち、２つの木の両方で単一の連結subtreeを構成するもので、スコアの合計値が最大となるものを応えよ。

解法

N<=50と小さいので、まずWarshall-Floydなどで頂点の距離をもとめておく。

頂点xとyをsubtreeに含めようとすると、どちらかの木でx-yを結ぶパスの中にあらわれる頂点は一緒に選択しないといけないことがわかる。
事前に頂点間の距離を求めておくと、上記頂点群は簡単に求めることができる。

あとはsubtreeの根を総当たりで決め打ちし、そこからどこまでsubtreeの範囲を伸ばせるかを求めることになる。
ここで、以下のブログを参考に損失のフローを作った。
最小カット - CKomakiの日記 - TopCoder部

あとは、最大フローから損失の最小カットを求めればよい。

int mat[2][51][51];
ll mask[51][51],mask2[51][51];

class MaxFlow {
public:
	struct edge { int to, capacity, reve;};
	static const int MV = 10000;
	vector<edge> E[MV];
	int vis[MV];
	
	void init() { for(int i=0;i<MV;i++) E[i].clear();}
	MaxFlow() {init();}
	void add_edge(int x,int y, int cap) {
		E[x].push_back((edge){y,cap,(int)E[y].size()});
		E[y].push_back((edge){x,0, (int)E[x].size()-1}); /* rev edge */
	}
	
	int dfs(int from,int to,int cf) {
		int i,tf;
		if(from==to) return cf;
		vis[from]=1;
		FOR(i,E[from].size()) {
			edge& e=E[from][i];
			if(vis[e.to]==0 && e.capacity>0 && (tf = dfs(e.to,to,min(cf,e.capacity)))>0) {
				e.capacity -= tf;
				E[e.to][e.reve].capacity += tf;
				return tf;
			}
		}
		return 0;
	}
	
	int maxflow(int from, int to) {
		int fl=0,tf;
		while(1) {
			ZERO(vis);
			if((tf = dfs(from,to,1<<29))==0) return fl;
			fl+=tf;
		}
	}
};

class DoubleTree {
	public:
	int N;
	vector <int> sc;
	int dodo(int cur) {
		MaxFlow mf;
		int tot=0,i,j;
		FOR(i,N) {
			if(sc[i]>0) tot+=sc[i];
			if(i==cur) {
				if(sc[i]<0) mf.add_edge(100+i,200,-sc[i]);
			}
			else {
				if(sc[i]>0) mf.add_edge(0,10+i,sc[i]);
				if(sc[i]<0) mf.add_edge(100+i,200,-sc[i]);
				FOR(j,N) if(mask[cur][i]&(1LL<<j)) mf.add_edge(100+i,10+j,100000);
			}
			mf.add_edge(10+i,100+i,100000);
		}
		return tot-mf.maxflow(0,200);
		
	}
	
	int maximalScore(vector <int> a, vector <int> b, vector <int> c, vector <int> d, vector <int> score) {
		N=a.size()+1;
		int x,y,j,i;
		sc=score;
		FOR(x,N) FOR(y,N) mat[0][x][y]=1000,mat[1][x][y]=1000;
		FOR(x,N) mat[0][x][x]=mat[1][x][x]=0;
		FOR(x,N-1) mat[0][a[x]][b[x]]=mat[0][b[x]][a[x]]=1;
		FOR(x,N-1) mat[1][c[x]][d[x]]=mat[1][d[x]][c[x]]=1;
		FOR(i,N) FOR(x,N) FOR(y,N) mat[0][x][y]=min(mat[0][x][y],mat[0][x][i]+mat[0][i][y]);
		FOR(i,N) FOR(x,N) FOR(y,N) mat[1][x][y]=min(mat[1][x][y],mat[1][x][i]+mat[1][i][y]);
		
		
		ZERO(mask);
		FOR(x,N) FOR(y,N) FOR(j,N) if(mat[0][x][j]+mat[0][j][y]==mat[0][x][y] || mat[1][x][j]+mat[1][j][y]==mat[1][x][y]) mask[x][y] |= 1LL<<j;
		
		int ma=0;
		FOR(i,N) ma=max(ma,dodo(i));
		return ma;
		
	}
}

まとめ

そんなフローの作り方知らないよ、ということで解けないのも無理はない。
本番貪欲でやったら１ケースだけ通らなかった…。