ABC010 D - 浮気予防

D - 浮気予防

概要

頂点辺の無向グラフと項の数列が与えられる。はからまでの整数からなり、相異なる。グラフの頂点は0-indexed。
グラフのうちいくつかの辺を通行止めにし、その状態で頂点から各頂点にいくつ行けるかを考える。
このとき、「通行止めにする辺数」と「頂点列のうち行くことができる頂点数」の合計の最小値を求めよ。

制約

・共通制約

①部分点制約

②満点制約

方針①部分点

通行止めにする辺の組み合わせをすべて試す。いわゆるbit全探索。計算量は少なくとものオーダーになる。

解答①部分点

Submission #4086373 - AtCoder Beginner Contest 010

#include <bits/stdc++.h>
 
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,n) FOR(i,0,n)
#define RFOR(i,a,b) for(int i=(a)-1;i>=(b);i--)
#define rrep(i,n) RFOR(i,n,0)
#define fi first
#define se second
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
 
const int max_N = 105;
int N, G, E;
int p[max_N];
vector<pii> g[max_N];
 
int u[max_N];
 
void dfs(int x, int c){
	for(pii q : g[x]){
		if((c >> q.se) & 1 && !u[q.fi]){
			u[q.fi] = true;
			dfs(q.fi, c);
		}
	}
}
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	cin >> N >> G >> E;
 
	rep(i, G) cin >> p[i];
	rep(i, E){
		int a, b;
		cin >> a >> b;
		g[a].push_back((pii){b, i});
		g[b].push_back((pii){a, i});
	}
 
	if(E > 12) {
		cout << -1 << endl;
		return 0;
	}
 
	int ans = 1e9;
	for(int c = 0; c < (1 << E); c++){
		rep(i, N) u[i] = false;
		dfs(0, c);
 
		int t = E;
		rep(i, E) if((c >> i) & 1) t--;
		rep(i, G) if(u[p[i]]) t++;
		ans = min(ans, t);
	}
 
	cout << ans << endl;
}

方針②満点

グラフに番目の頂点と、各頂点と頂点を結ぶ辺を追加する。
すると、与えられた問題は「頂点から頂点へのパスが存在しなくなるまでに除去しなければいけない辺の数の最小値を求める」問題と言い換えることができる。すなわち、これはネットワークフローの最小カット問題である。

最小カット問題を解くことは最大流問題を解くことと同じであり、辺の容量が1のネットワークフローを構成し、最大流を求める。（Ford-Fulkersonのアルゴリズム）

解答②満点

Submission #4086466 - AtCoder Beginner Contest 010

#include <bits/stdc++.h>
 
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,n) FOR(i,0,n)
#define RFOR(i,a,b) for(int i=(a)-1;i>=(b);i--)
#define rrep(i,n) RFOR(i,n,0)
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
 
class Flow{
private:
	struct edge{int to, cap, rev;};
	vector<vector<edge>> E;
	vector<bool> used;
 
public:
	Flow(int n){
		E.resize(n);
		used.resize(n);
	}
 
	void add_edge(int from, int to, int cap){
		E[from].push_back({to, cap, (int)E[to].size()});
		E[to].push_back({from, 0, (int)E[from].size() - 1});
	}
 
	int dfs(int v, int t, int f){
		if(v == t) return f;
		used[v] = true;
		for(edge& e : E[v]){
			if(!used[e.to] && e.cap > 0){
				int d = dfs(e.to, t, min(f, e.cap));
				if(d > 0){
					e.cap -= d;
					E[e.to][e.rev].cap += d;
					return d;
				}
			}
		}
		return 0;
	}
 
	int max_flow(int s, int t){
		int ans = 0;
		while(true){
			fill(used.begin(), used.end(), 0);
			int f = dfs(s, t, INT_MAX);
			if(f == 0) return ans;
			ans += f;
		}
	}
};	
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	int N, G, E;
	cin >> N >> G >> E;
 
	Flow f(N + 1);
	rep(i, G){
		int p;
		cin >> p;
		f.add_edge(p, N, 1);
	}
 
	rep(i, E){
		int a, b;
		cin >> a >> b;
		f.add_edge(a, b, 1);
		f.add_edge(b, a, 1);
	}
 
	cout << f.max_flow(0, N);
}

感想

満点解法は下記を参考にしました。
Submission #1307747 - AtCoder Beginner Contest 010

これは知らないと思いつかない。。