TopCoder SRM442 Div1Hard

問題

Nowhere Landの王様が、国のいくつかの街に警備を置こうとしている。国にはK個の警備会社がある。最初から警備が置かれている街がいくつかあり、また警備を新たに置くことができる街は、警備会社が機関を置いている街だけである。また、いくつかの街の間には協約があって、「ある警備会社が、片方の街だけ警備していて、もう片方の街は警備していない」なら、1つの対立が生じる。対立の数をできるだけ少なくするとき、その最小値を返せ。

解法

警備会社ごとに独立な問題として考えられる。
各街と、起点、終点を持つ有向グラフを考える。ある街が、「機関がなくて警備員が置けない」なら、「起点→その街」を容量無限大の辺で結ぶ。「最初から警備員が置かれている」なら、「その街→終点」を容量無限大の辺で結ぶ。また、関係がある街同士は、容量1の双方向の辺で結ぶ。起点→終点の最大流を求めると、その警備会社による「対立の数」の最小値が求まる。
いったい何をやっているかというと、「警備員を置かない街」と「警備員を置く街」の間での最小カットを求めている。適当に警備員を置く街と経緯便を置かない街を決めたとき、「置く街」と「置かない街」の間にある辺が、対立の数である。これを最小化する（＝最小カットを求める）には、最大流を求めればよい。

コード

#include <queue>
#include <algorithm>
#include <vector>
#include <string>

using namespace std;

class dinic
{
	struct edge
	{
		edge *next, *pair;
		int src, dest, cap, flow;
	};

	int v, e;
	edge *pool, **con; int top;

	int* level;

public:
	dinic(int _v, int _e)
	{
		v = _v; e = _e;
		pool = new edge[e];
		con = new edge*[v];
		for(int i=0;i<v;i++) con[i] = NULL;
		top = 0;
	}

	~dinic()
	{
		delete [] pool;
		delete [] con;
	}

	edge* _add_edge(int src, int dest, int cap)
	{
		edge* ed = &(pool[top++]);
		ed->src = src;
		ed->dest = dest;
		ed->cap = cap;
		ed->flow = 0;

		ed->next = con[src];
		con[src] = ed;

		return ed;
	}

	void add_pair(int src, int dest, int cap1, int cap2)
	{
		edge *e1 = _add_edge(src, dest, cap1);
		edge *e2 = _add_edge(dest, src, cap2);

		e1->pair = e2;
		e2->pair = e1;
	}

	int dfs(int s, int d, int cap)
	{
		if(s==d || cap==0) return cap;

		int w = 0;
		for(edge* ed = con[s]; ed != NULL; ed = ed->next)
			if(level[ed->dest] > level[s]){
				int f = dfs(ed->dest, d, std::min(cap - w, ed->cap - ed->flow));
				if(f > 0){
					ed->flow += f;
					ed->pair->flow -= f;
					w += f;
				}
			}

		return w;
	}

	long long max_flow(int s, int d)
	{
		level = new int[v];

		for(int i=0;i<e;i++) pool[i].flow = 0;

		long long ret = 0;

		for(bool update=true; update; ){
			update = false;

			//derminate distance
			std::fill(level, level+v, -1);
			level[s] = 0;
			std::queue<int> q;
			q.push(0);

			int ps;
			while(!q.empty()){
				ps = q.front(); q.pop();
				
				for(edge* ed = con[ps]; ed != NULL; ed = ed->next){
					if(ed->cap > ed->flow && level[ed->dest]==-1){
						level[ed->dest] = level[ps] + 1;
						q.push(ed->dest);
					}
				}
			}

			for(;;){
				int gain = dfs(s, d, 0x7FFFFFFF);
				if(gain==0) break;
				ret += gain;
				update = true;
			}
		}

		delete [] level;

		return ret;
	}
};

class NowhereLand
{
	int C, K;
	bool guard[50][50], agency[50][50], rel[50][50];
	
	vector<int> parse(string s)
	{
		vector<int> ret;
		int p = -1;
		for(int i=0;i<s.size();i++){
			if(s[i]==' '){
				ret.push_back(p);
				p = -1;
			}else{
				if(p==-1) p = 0;
				else p *= 10;
				p += s[i]-'0';
			}
		}
		if(p!=-1) ret.push_back(p);
		return ret;
	}
	
	int solve(int p)
	{
		dinic dn(52, 2600);
		for(int i=0;i<C;i++)
			for(int j=i+1;j<C;j++) if(rel[i][j]){
				dn.add_pair(i+2, j+2, 1, 1);
			}
		for(int i=0;i<C;i++){
			if(agency[i][p]&&!guard[i][p]) continue;
			if(!agency[i][p]) dn.add_pair(0, i+2, 1000, 0);
			if(guard[i][p]) dn.add_pair(i+2, 1, 1000, 0);
		}
		
		return dn.max_flow(0, 1);
	}
	
public:
	int placeGuards(vector<string> cities, int k, vector<string> guards, vector<string> agencies)
	{
		C = cities.size(); K = k;
		for(int i=0;i<C;i++)
			for(int j=0;j<C;j++) rel[i][j] = (cities[i][j]=='1');
		for(int i=0;i<C;i++){
			vector<int> g = parse(guards[i]), a = parse(agencies[i]);
			for(int j=0;j<k;j++) guard[i][j] = agency[i][j] = false;
			for(int j=0;j<g.size();j++) guard[i][g[j]] = true;
			for(int j=0;j<a.size();j++) agency[i][a[j]] = true;
		}
		
		int ret = 0;
		for(int i=0;i<K;i++) ret += solve(i);
		
		return ret;
	}
};