AtCoder Beginner Contest #010 D - 浮気予防
蟻本のフローを写経する所までだった。
本番では通せなかった問題だが、冷静に考えれば写経(蟻本)するだけだった。
詳しい事は蟻本を読もう。
問題
http://abc010.contest.atcoder.jp/tasks/abc010_4解法
新たに終点(N)を作成してマークされてる女の子から終点に辺を張り、高橋君(始点)からフローを流す。コード
#include <map> #include <set> #include <list> #include <cmath> #include <queue> #include <stack> #include <cstdio> #include <string> #include <vector> #include <complex> #include <cstdlib> #include <cstring> #include <numeric> #include <sstream> #include <iostream> #include <algorithm> #include <functional> #define mp make_pair #define pb push_back #define all(x) (x).begin(),(x).end() #define rep(i,n) for(int i=0;i<(n);i++) using namespace std; typedef long long ll; typedef unsigned long long ull; typedef vector<bool> vb; typedef vector<int> vi; typedef vector<vb> vvb; typedef vector<vi> vvi; typedef pair<int,int> pii; const int INF=1<<29; const double EPS=1e-9; const int dx[]={1,0,-1,0},dy[]={0,-1,0,1}; const int MAX_V = 110; struct edge { int to,cap,rev; }; vector<edge> G[MAX_V]; bool used[MAX_V]; void add_edge(int from,int to,int cap){ G[from].push_back((edge){to,cap,G[to].size()}); G[to].push_back((edge){from,0,G[from].size() - 1}); } int dfs(int v,int t,int f){ if(v == t)return f; used[v] = true; for(int i = 0;i < G[v].size();i++){ edge &e = G[v][i]; if(!used[e.to] && e.cap > 0){ int d = dfs(e.to,t,min(f,e.cap)); if(d > 0){ e.cap -= d; G[e.to][e.rev].cap += d; return d; } } } return 0; } int max_flow(int s,int t){ int flow = 0; for(;;){ memset(used, 0, sizeof(used)); int f = dfs(s,t,INF); if(f == 0)return flow; flow += f; } } int N,V,E; int main(){ cin>>N>>V>>E; for(int i = 0;i < V;i++){ int x; cin>>x; add_edge(x, N, 1); } for(int i = 0;i < E;i++){ int x,y; cin>>x>>y; add_edge(x, y, 1); add_edge(y, x, 1); } cout <<max_flow(0, N)<<endl; return 0; }