Maximum-Cup 2013 : F - 3人の騎士と1匹の犬

Fはそこそこの難易度だけど自力でしっかり解ききれてよかった。
http://maximum-cup-2013.contest.atcoder.jp/tasks/maximum_2013_f

問題

N人の騎士の座標と、M箇所の魔力ポイントの魔力値および座標が与えられる。
各騎士は最大1か所の魔力ポイントから魔力値を取得でき、かつ1か所の魔力ポイントは騎士1人しか利用できない。
各騎士が魔力ポイントまで移動するのにかかるコストはマンハッタン距離と一致する。

この条件で、最大の魔力値を取得できるように騎士の移動コストを最小化せよ。

解法

魔力を最大化したいので、当然魔力値の多い魔力ポイントからmin(N,M)個を利用する。
ただし、同じ魔力値のポイントがいくつかある場合、総コストを最小化するように魔力ポイントを選択しなければならない。

L個の魔力ポイントを選択するとき、M個のポイントは上位L番目のポイントより魔力値が高く、N個のポイントは上位L番目と同じ魔力値とする。(当然M=Lとなる)

この時、以下のようなグラフを作って最少コストフローを解けばよい。

• sourceから各騎士に向け容量1の辺を張る
• 各騎士から各魔力ポイントに向け容量1、コストがマンタッハン距離の辺を張る
• 各魔力ポイントのうち、上位M個のポイントからはsinkに容量1の辺を張る
• 各魔力ポイントのうち、上位L番と同じ魔力値のポイントからは、中間ポイントに容量1の辺を張る
• 中間ポイントからsinkに容量(L-M)の辺を張る

上記のようにグラフを作れば、上位M個の魔力ポイントと、あとは魔力値が均衡する残りN個中(L-M)個の魔力ポイントを選択してコストを最小化できる。

int N,M;
int KX[51],KY[51];
int MA[51],MX[51],MY[51];

class MinCostFlow {
public:
	struct edge { int to, capacity; ll cost, reve;};
	static const int MV = 5000;
	vector<edge> E[MV];
	ll dist[MV], prev_v[MV], prev_e[MV], NV;
	
	void init(int NV) { 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;
	}
};


void solve() {
	int f,i,j,k,l,x,y;
	string s;
	
	cin>>N>>M;
	FOR(i,N) cin>>s>>KX[i]>>KY[i];
	FOR(i,M) cin>>s>>MA[i]>>MX[i]>>MY[i];
	vector<int> MM;
	FOR(i,M) MM.push_back(MA[i]);
	sort(MM.begin(),MM.end());
	j=MM[M-min(N,M)];
	
	MinCostFlow mcf;
	mcf.init(1000);
	FOR(i,N) mcf.add_edge(0,100+i,1,0);
	k=l=0;
	FOR(i,M) {
		if(MA[i]>j) k++,mcf.add_edge(200+i,300,1,0),l+=MA[i];
		if(MA[i]==j) mcf.add_edge(200+i,299,1,0),l+=MA[i];
	}
	if(l==0) return _P("0\n");
	
	mcf.add_edge(299,300,min(N,M)-k,0);
	FOR(x,N) FOR(y,M) mcf.add_edge(100+x,200+y,1,abs(KX[x]-MX[y])+abs(KY[x]-MY[y]));
	
	_P("%d\n",mcf.mincost(0,300,min(N,M)));
}

まとめ

面白いグラフの作り方で勉強になった。