kmjp's blog

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

TopCoder SRM 619 Div1 Medium GoodCompanyDivOne

計算量の見積もりが甘かったけど、何とか解けた。
http://community.topcoder.com/stat?c=problem_statement&pm=13114

問題

N人の社員がおり、0番の社員を除くと各社員はそれより若い番号の社員を上司に持つ。
ここで会社が各社員にK種類のうち2つずつスキルを身に着けるべく訓練させたい。
1人にj番のスキルを身に着けさせるスキルは、各人共通でtraining[j]である。

各人には以下の条件を満たすようなスキル配置を行いたい。

  • i番のチームとはi番の社員とその直属の部下(i番を直接上司にする社員)からなる。
  • チームの各人は、それぞれ異なるスキルを1個ずつ発揮できるようにする。

なお、各人は自分をトップとするチームと、自分の上司をトップとする2つのチームに属する場合があるが、両方で同じスキルを発揮してもよいししなくても良い。
ただし両方で発揮するスキルは、身についた2つのスキルのうちどちらかである。

条件を満たす最小コストのスキル配置を求めよ。

解法

社員構成は根付木になることは明らか。
これをDFS+最小コストフローで解いていく。

状態としては[現在の社員][その社員をトップとするチームにおける発揮スキル]を持ち、コストを最小化すればよい。

まず各人が自分がトップとなるチームにおいて自分と直属の部下が異なる発揮スキルを持てるよう最小コストフローを求める。
この際のグラフは、各部下が部下をトップとするチームで発揮したのと同じスキルを発揮する場合、後1個のスキルはなんでもいいので安いやつを覚えさせる。
別スキルを発揮する場合は、その分のコストを上乗せする。
あとは自分のスキルを0~(K-1)で総当たりし、計K回最小コストフローを求めればよい。

各頂点でK回コスト最小フローを求めるので、最小フローを求める回数はO(NK)。
各回の最小コストフローの計算量は頂点数(N+K)、辺が(K^2)。
よって全体でO((N+K)*N*K^2)。N,Kの上限は同じなので結局O(N^5)程度なので何とか間に合う。

class MinCostFlow {
public:
	struct edge { int to, capacity; ll cost, reve;};
	static const int MV = 100;
	vector<edge> E[MV];
	ll dist[MV], prev_v[MV], prev_e[MV], NV;
	
	MinCostFlow() { init(MV); }
	void init(int NV=MV) { this->NV=NV; for(int i=0;i<MV;i++) E[i].clear();}
	void add_edge(int x,int y, int cap, int cost) {
		E[x].push_back((edge){y,cap,cost,E[y].size()});
		E[y].push_back((edge){x,0, -cost,E[x].size()-1}); /* rev edge */
	}
	
	int mincost(int from, int to, int flow) {
		int res=0,i,v;
		ZERO(prev_v); ZERO(prev_e);
		while(flow>0) {
			fill(dist, dist+NV, 1LL<<50);
			dist[from]=0;
			bool up=true;
			while(up) {
				up=false;
				FOR(v,NV) {
					if(dist[v]==1LL<<50) continue;
					FOR(i,E[v].size()) {
						edge &e=E[v][i];
						if(e.capacity>0 && dist[e.to]>dist[v]+e.cost) {
							dist[e.to]=dist[v]+e.cost;
							prev_v[e.to]=v;
							prev_e[e.to]=i;
							up=true;
						}
					}
				}
			}
			
			if(dist[to]==1LL<<50) return -1;
			int lc=flow;
			for(v=to;v!=from;v=prev_v[v]) lc = min(lc, E[prev_v[v]][prev_e[v]].capacity);
			flow -= lc;
			res += lc*dist[to];
			for(v=to;v!=from;v=prev_v[v]) {
				edge &e=E[prev_v[v]][prev_e[v]];
				e.capacity -= lc;
				E[v][e.reve].capacity += lc;
			}
		}
		return res;
	}
};


class GoodCompanyDivOne {
	public:
	int N,K;
	int dpdp[50][50];
	vector<int> C[51];
	vector<int> T;
	
	void dfs(int cur) {
		int i,j,x,y;
		
		if(C[cur].empty()) {
			FOR(i,K) dpdp[cur][i]=T[i];
			return;
		}
		
		FOR(i,C[cur].size()) dfs(C[cur][i]);
		
		FOR(i,K) {
			MinCostFlow mf;
			
			mf.add_edge(0,10+cur,1,0);
			mf.add_edge(10+cur,50+i,1,T[i]);
			FOR(j,C[cur].size()) {
				int tar=C[cur][j];
				mf.add_edge(0,10+tar,1,0);
				FOR(x,K) {
					int mi=1<<20;
					FOR(y,K) {
						if(x==y) {
							if(x==0) mi=min(mi,dpdp[tar][x]+T[1]);
							else mi=min(mi,dpdp[tar][x]+T[0]);
						}
						else {
							mi=min(mi,dpdp[tar][y]+T[x]);
						}
					}
					mf.add_edge(10+tar,50+x,1,mi);
				}
			}
			
			FOR(j,K) mf.add_edge(50+j,1,1,0);
			dpdp[cur][i]=mf.mincost(0,1,1+C[cur].size());
			if(dpdp[cur][i]==-1) dpdp[cur][i]=1<<20;
		}
	}
	
	
	int minimumCost(vector <int> superior, vector <int> training) {
		int i,x,y;
		
		T=training;
		N=superior.size();
		K=T.size();
		
		sort(T.begin(),T.end());
		if(N==1) return T[0]+T[1];
		
		ZERO(C);
		for(i=1;i<N;i++) C[superior[i]].push_back(i);
		
		FOR(x,N) FOR(y,K) dpdp[x][y]=1<<20;
		
		
		dfs(0);
		int ret=1<<20;
		FOR(i,K) {
			if(i==0) ret=min(ret,dpdp[0][i]+T[1]);
			else ret=min(ret,dpdp[0][i]+T[0]);
		}
		if(ret>=1<<20) return -1;
		return ret;
	}
};

まとめ

本番、最小費用流とDPの連携まで気づくのに時間がかかったが、何とか解けてよかった。
各人のスキル割り当てが最小費用流、まではすぐ思いついたけど、DPとの連携に手こずったのよね。