Codeforces #227 Div2. D. George and Interesting Graph

なかなか面白い問題。
http://codeforces.com/contest/387/problem/D

問題

初期状態として、N点とM個の有向辺からなるグラフが与えられる。
このグラフを変形して、interestingなグラフを作りたい。
interestingなグラフとは、下記の条件を満たすグラフである。

1. N点のうち１つがcenterである。
2. 全ての点uは、center vに対し(u,v)(v,u)の有向辺をもつ。center自身も(v,v)のループを持つ。
3. center以外の点uの入次数・出次数は2である。

初期状態のグラフに対し、コスト１で１辺の増減ができる。
interestingなグラフを作る最小コストを求めよ。

解法

N<=500と小さいので、全ての点をcenterと置いたときのコストを総当たりする。

条件2のコストは、各点とcenterとの辺の有無をカウントして、不足する分だけコストをかけて辺を増やせばよい。

問題は条件3。
center以外の各点は、すでにcenterとの間で２辺を持っているので、残りは入次数・出次数１である。
よって、center以外の各点が複数のループを作るようにし、そのための辺の増減を行えばよい。

出来るだけ既存の辺を使ってループを作る方が当然コストが小さい。
各点が入次数・出次数１であるということから、２部マッチングを使い既存の辺でできるだけ使おう。
既存の辺で不足する辺を追加し、初期状態で余分にある辺を消せばよい。

int N,M;
vector<int> E[501];
int vis[501];
int mat[501][501];

class MaxFlow {
public:
	struct edge { int to, capacity, reve;};
	static const int MV = 10000;
	vector<edge> E[MV];
	int vis[MV];
	
	void init() { for(int i=0;i<MV;i++) E[i].clear();}
	MaxFlow() {init();}
	void add_edge(int x,int y, int cap) {
		E[x].push_back((edge){y,cap,E[y].size()});
		E[y].push_back((edge){x,0, E[x].size()-1}); /* rev edge */
	}
	
	int dfs(int from,int to,int cf) {
		int i,tf;
		if(from==to) return cf;
		vis[from]=1;
		FOR(i,E[from].size()) {
			edge& e=E[from][i];
			if(vis[e.to]==0 && e.capacity>0 && (tf = dfs(e.to,to,min(cf,e.capacity)))>0) {
				e.capacity -= tf;
				E[e.to][e.reve].capacity += tf;
				return tf;
			}
		}
		return 0;
	}
	
	int maxflow(int from, int to) {
		int fl=0,tf;
		while(1) {
			ZERO(vis);
			if((tf = dfs(from,to,1<<29))==0) return fl;
			fl+=tf;
		}
	}
};


void solve() {
	int f,i,j,k,l,x,y,r;
	
	cin>>N>>M;
	FOR(i,M) {
		cin>>x>>y;
		E[x-1].push_back(y-1);
		mat[x-1][y-1]=1;
	}
	
	int mi=1000000;
	FOR(x,N) {
		r=mat[x][x]==0;
		FOR(y,N) if(x!=y) r+=(mat[x][y]==0)+(mat[y][x]==0);
		
		MaxFlow mf;
		FOR(y,N) if(x!=y) {
			mf.add_edge(0,y+1,1);
			mf.add_edge(1000+y,2000,1);
			FOR(i,E[y].size()) {
				f=E[y][i];
				if(f!=x) {
					mf.add_edge(y+1,1000+f,1);
					r++;
				}
			}
		}
		y=mf.maxflow(0,2000);
		mi=min(mi,r-y+(N-1-y));
	}
	_P("%d\n",mi);
}

まとめ

二部グラフのマッチングを本番中に思いつけて良かったね。