TopCoder SRM 328 Div1 Medium BlockEnemy

TopCoder グラフ理論 動的計画法

問題

n個の都市がn-1本の双方向に通行可能な道路によって結ばれている。
全ての都市のペアに対して、その都市同士を結ぶ道がただ一通りだけ存在する。


それぞれの道には、その道を破壊するコストが定められている。


occupiedTowns[]の都市を敵が占領した。
敵が占領している都市の、どの二つも直接または間接的に行き来できないように道を破壊したい。


破壊する道のコストの和の最小値を求めよ。

制約条件

n≦50
道を破壊するコスト≦1000000
occupiedTownsの要素数≦n

方針

都市と道のグラフは、木になっている。


次のような動的計画法をすればよい。
dp[i][0]を、i以下の部分木について、

  • どの占領されている二都市も結ばれていない
  • 上の木へ、占領されている都市がつながっていない

ような状態にするための最小コストとする。


dp[i][1]を、i以下の部分木について、

  • どの占領されている二都市も結ばれていない
  • 上の木へ、占領されている都市がただ一つだけつながっている

ような状態にするための最小コストとする。


dp[i][0]は、
iの都市が占領されている場合はまず、上の都市へつながる道を切る。
その後、全ての部分木についてdp[j][0]を求めて合計すればよい。
iの都市が占領されていないときは、
上の都市へつながる道をきって、部分木のどれか一つがdp[j][1]で、他はdp[j][0]になっているような場合か、
上の都市へつながる道を切らないで、部分木全てがdp[j][0]になっている場合がある。


dp[i][1]は、
iの都市が占領されている場合は、上への都市へつながる道路を残して、
部分木全てについてdp[j][0]を求めて合計すればいい。
iの都市が占領されていない場合は、上への都市へつながる道路を残して、
部分木の一つがdp[j][1]で、他がdp[j][0]であるようなものの最小値をとればいい。

ソースコード

int n,dp[50][2];
bool ocp[50];
vector<vector<pi> > e;

ll rec(int c,int p,int f,int pcost){
	if(dp[c][f]>=0)return dp[c][f];
	
	if(ocp[c]){
		ll res=f?0:pcost;
		rep(i,e[c].size())if(e[c][i].first!=p)
			res+=rec(e[c][i].first,c,0,e[c][i].second);
		return dp[c][f]=res;
	}
	
	if(!f){
		ll sum=0, res;
		rep(i,e[c].size())if(e[c][i].first!=p)
			sum+=rec(e[c][i].first,c,0,e[c][i].second);
		res=sum;
		rep(i,e[c].size())if(e[c][i].first!=p){
			ll tmp=sum-rec(e[c][i].first,c,0,e[c][i].second);
			tmp+=rec(e[c][i].first,c,1,e[c][i].second)+pcost;
			res=min(res,tmp);
		}
		return dp[c][f]=res;
	}
	ll sum=0, res=1ll<<60;
	rep(i,e[c].size())if(e[c][i].first!=p)sum+=rec(e[c][i].first,c,0,e[c][i].second);
	rep(i,e[c].size())if(e[c][i].first!=p){
		res=min(res,sum-rec(e[c][i].first,c,0,e[c][i].second)+rec(e[c][i].first,c,1,e[c][i].second));
	}
	return dp[c][f]=res;
}
class BlockEnemy {
	public:
	int minEffort(int N, vector <string> roads, vector <int> occupiedTowns) 
	{
		n=N;
		rep(i,n)ocp[i]=0;
		memset(dp,-1,sizeof(dp));
		e.clear();
		e.resize(n);
		
		rep(i,n-1){
			stringstream ss(roads[i]);
			int a,b,c;
			ss>>a>>b>>c;
			e[a].pb(mp(b,c));
			e[b].pb(mp(a,c));
		}
		rep(i,occupiedTowns.size())ocp[occupiedTowns[i]]=1;
		
		return rec(0,-1,0,0);
	}