読者です 読者をやめる 読者になる 読者になる

SRM619Med

問題:GoodCompanyDivOne
概要:
n<=30の根付き木とm(2以上30以下)個の整数(1以上100以下)の仕事(にかかるコスト)を表す配列x[i]がある.それぞれの頂点に,異なる2つの仕事i,jをある条件のもと割り当てて、選ばれた2n個のx[]の和を最小化せよ.条件が満たせないなら-1を返せ.
ある条件:どの頂点を選んでも、その頂点とその直接の子たち(departmentと呼ぶ)からそれぞれ1つ仕事を選んで、それらが全て異なるようにできる.(頂点を選んだ後に仕事を選んで良いことに注意)

解法:
departmentの最大の大きさがmより大きければ-1.下から再帰的にやると、それぞれのdepartmentで、条件をみたすように選んだ方の仕事を決めると、もう片方は残る最小のものを選んで良い(このことから全部の頂点が0(xはソート済みとする)を選ぶことがわかるが、"0じゃない方で何を選ぶか"を考えて解くのは難しいと思う).
pw[i][w]=頂点iで(iのdepartmentで仕事を選ぶときに選ぶ仕事として)wを選んだ時に,i以下のsubtreeでのコストの最小は? とした時に、それぞれの子は、同じものを選んではいけない、wを選んではいけない、という条件があるので、これはmincostflowでいける.(前述の"0じゃない方"を考えると、1つのdepartmentに,(0,1),(0,1)のように同じ仕事を選んでいる可能性があってフローに持ち込めない気がする)

"0以外"で考えてはまっていたが、Method名がminimumCostである時点で気づけよ…

コード:

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <utility>
#include <algorithm>
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
using namespace std;
typedef pair<int,int> P;				//first=
struct edge {int to,cap,cost,rev;};
const int MAX_V=62,INF=1e8;
int V;
int pw[30][30];		//person work
vector<edge> G[MAX_V];
int h[MAX_V];							//potential
int dist[MAX_V];						//
int prevv[MAX_V],preve[MAX_V];
void add_edge(int from, int to, int cap, int cost){
	edge e1={to,cap,cost,G[to].size()},e2={from,0,-cost,G[from].size()};
	G[from].push_back(e1);
	G[to].push_back(e2);
}
int min_cost_flow(int s, int t, int f){
	int res=0;
	fill(h,h+V,0);
	while(f>0){												//renew h through dijkstra 
		priority_queue< P,vector<P>,greater<P> > que;		//小さい順
		fill(dist,dist+V,INF);
		dist[s]=0;
		que.push(P(0,s));
		while(!que.empty()){
			P p=que.top();
			que.pop();
			int v=p.second;
			if(dist[v]<p.first) continue;
			for(int i=0;i<G[v].size();i++){
				edge &e=G[v][i];
				if(e.cap>0 && dist[e.to]>dist[v]+e.cost+h[v]-h[e.to]){
					dist[e.to]=dist[v]+e.cost+h[v]-h[e.to];
					prevv[e.to]=v;
					preve[e.to]=i;
					que.push(P(dist[e.to],e.to));
				}
			}
		}
		if(dist[t]==INF) return -1;
		for(int v=0;v<V;v++) h[v]+=dist[v];
		int d=f;
		for(int v=t;v!=s;v=prevv[v]){
			d=min(d,G[prevv[v]][preve[v]].cap);
		}
		f-=d;
		res+=d*h[t];
		for(int v=t;v!=s;v=prevv[v]){
			edge &e=G[prevv[v]][preve[v]];
			e.cap-=d;
			G[v][e.rev].cap+=d;
		}
	}
	return res;
}
class GoodCompanyDivOne{
	public:
	int minimumCost(vector <int> sup, vector <int> t){
		vector<int> dep[30];
		int n=sup.size(),m=t.size();
		sort(t.begin(),t.end());
		rep1(i,n-1) dep[sup[i]].push_back(i);
		rep(i,n) if(dep[i].size()+1>m) return -1;
		for(int i=n-1;i>=0;i--){
			int ds=dep[i].size();
			if(ds==0){
				pw[i][0]=t[0]+t[1];
				////cout << i << " " << 0 << " " << pw[i][0] << endl;
				rep1(w,m-1){
					pw[i][w]=t[0]+t[w];
					//cout << i << " " << w << " " << pw[i][w] << endl;
				}
				continue;
			}
			rep(w,m){
				V=ds+m+2;
				int ss=V-2,tt=V-1;
				rep(i,V) G[i].clear();
				rep(p,ds) rep(tr,m) if(w!=tr && pw[dep[i][p]][tr]>0) add_edge(p,ds+tr,1,pw[dep[i][p]][tr]);
				rep(p,ds) add_edge(ss,p,1,0);
				rep(tr,m) if(w!=tr) add_edge(ds+tr,tt,1,0);
				pw[i][w]=min_cost_flow(ss,tt,ds);
				if(w==0) pw[i][w]+=t[1]+t[0];
				else pw[i][w]+=t[0]+t[w];
				//cout << i << " "  << w << " "  << pw[i][w] << endl;
			}
		}
		int ans=INF;
		rep(w,m) ans=min(ans,pw[0][w]);
		return ans;
	}
};