Codeforces 387(#227 Div2 only) D. George and Interesting Graph

Codeforces グラフ理論

問題

有向グラフがinterestingであるとは、

  • 多重辺が存在しない。
  • 一つの頂点cがあり、cはほかのどの頂点へも辺があり、どの頂点からもcへの辺がある。
  • 頂点cには一本だけ自己辺がある。
  • c以外の頂点は入次数、出次数ともに2である

ことを言う。


多重辺の存在しない有向グラフが与えられる。
このグラフを辺の追加または削除をそれぞれ一回につきコスト1で行って、
interestingにするための最小コストを求めよ。

制約条件

頂点≦500
辺≦1000

方針

cを固定する。
cに自己辺がなかったらコスト1がかかる。
まずcからほかの頂点へ辺が出てなかったら頂点一つにつきコスト1がかかる
ほかの頂点からcへ辺が入ってなかったら頂点一つにつきコスト1がかかる。


で、cを含む辺に関するコストはこれで全てで、
cを含まない辺のコストを考える。


残りの頂点は、cを含む辺を捨てれば全て入次数、出次数が1である必要がある。
今残っている辺でできるだけこのような辺を取りたい。


これは二部グラフの最大マッチングでやればよくて、
左側に頂点iのoutに対応する頂点、右側に頂点iのinに対応する頂点をそれぞれ置いて、
元の辺(a, b)にたいしてaのoutからbのinへ辺を張ったグラフの最大マッチングを取ればいい。


残りの辺は使えないので捨てる。
で、n - 1本に足りない分の辺は生やさなければならないので生やす。
これを全ての頂点をcとして試せばいい。
計算量はO(n * マッチングの計算量)で、O(n^3 + n^2m)とか。

ソースコード

int n, m, g[500][500];
vector<vi> e;
vector<pi> es;

int p[1000];
bool use[1000];

bool rec(int s){
	if(s < 0) return 1;
	each(i, e[s]) if(!use[*i]){
		use[*i] = 1;
		if(rec(p[*i])) return p[*i] = s, p[s] = *i, 1;
	}
	return 0;
}

int matching(){
	int res = 0;
	rep(i, 2 * n) p[i] = -1;
	rep(i, 2 * n) if(p[i] < 0){
		rep(j, 2 * n) use[j] = 0;
		if(rec(i)) res++;
	}
	return res;
}

int main(){
	cin >> n >> m;
	
	rep(i, m){
		int a, b;
		cin >> a >> b;
		a--; b--;
		g[a][b] = 1;
		es.pb(mp(a, b));
	}
	
	int ans = inf;
	
	rep(i, n){
		int cost = !g[i][i];
		int cnt = 0;
		rep(j, n) if(i != j) cost += (!g[i][j]) + (!g[j][i]);
		
		e.clear();
		e.resize(2 * n);
		
		rep(j, m){
			if(es[j].first == i || es[j].second == i) continue;
			
			cnt++;
			e[es[j].first].pb(es[j].second + n);
			e[es[j].second + n].pb(es[j].first);
		}
		cost += n - 1 + cnt - 2 * matching();
		ans = min(ans, cost);
	}
	cout << ans << endl;
	
	return 0;
}