SRM 465 600pt: GreenWarfare

TopCoder

問題概要

砲台がC(<50)個、基地がB(<50)個、プラントがP(<50)個ある。プラントと基地の距離がR以下ならプラントは基地に兵力を補給することができる。砲台は基地かプラントを破壊することができる。破壊するのには距離の2乗に応じたコストが生じる。全ての基地について、基地そのものを破壊するか補給する全てのプラントを破壊しなければならない。必要なコストの最小値を求める問題。

考えたこと

  • (当時は問題を勘違いしていたことが今判明した)
  • グラフっぽい。しかも最小費用流っぽい気がする。
  • でもどうキャパシティを定義すればいいんだ？
  • そもそも基地狙いかプラント狙いかで流量が変わってしまうんだから最小費用流では上手く行かない。
    • この辺をいじってどうにかならないかずっと考えてた。
  • 基地破壊するか近いプラント破壊するかで2SAT？
  • いやいや。自明解があるに決まってるじゃないか。どちらかだけ、という条件付けたらN-SATになってしまう。
  • うーん。まったく分からない。仕方ないのでEditorial見よう。
  • 最小カット！
  • 言われてもすぐに分からなかったのでちゃんと読んでみて、本当に最小カットで解けることを確認した。
  • 最小カットな問題は自分にとってははじめてだった。これはまだ全然ピンと来ない。自力で思いつける気がしない。

practiceで通ったコード

#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAX_N = 50;

struct GreenWarfare {

	int minimumEnergyCost(vector <int> canonX, vector <int> canonY, vector <int> baseX, vector <int> baseY, vector <int> plantX, vector <int> plantY, int energySupplyRadius) {
		const int C = canonX.size(), B = baseX.size(), P = plantX.size();

		//source -> baseの辺をはる
		for(int i=0; i<B; i++){
			int dist = INF;
			for(int j=0; j<C; j++){
				dist = min(dist, sq(canonX[j] - baseX[i]) + sq(canonY[j] - baseY[i]));
			}
			add_edge(B+P, i, dist);
		}

		//plant -> sinkの辺をはる
		for(int i=0; i<P; i++){
			int dist = INF;
			for(int j=0; j<C; j++){
				dist = min(dist, sq(canonX[j] - plantX[i]) + sq(canonY[j] - plantY[i]));
			}
			add_edge(i+B, B+P+1, dist);
		}

		//base -> plantの辺を張る
		for(int i=0; i<B; i++){
			for(int j=0; j<P; j++){
				if(sq(energySupplyRadius) >= sq(baseX[i] - plantX[j]) + sq(baseY[i] - plantY[j])){
					add_edge(i, j+B, INF);
				}
			}
		}

		return max_flow(B+P, B+P+1);
	}

	int sq(int x){
		return x*x;
	}
};