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; } };