AtCoder Beginner Contest 010 D - 浮気予防

problem

D: 浮気予防 - AtCoder Beginner Contest 010 | AtCoder

how to solve

This problem can be reduced to the maximum matching problems. This means that Ford-Fulkerson is among the good way to solve this problem.We have to take care that this graph is undirected so we have to prepare two edges for solving flow problems. The following link is very helpful to understand.

http://hidollara.hatenablog.com/entry/2017/07/29/165951

code

#include <iostream>
#include <vector>
using namespace std;

#define INF (1<<15)

class Solver {
    private:
        int n, g, e;
        vector<vector<int> > adj; 
        vector<bool> visited;
    public:
        Solver(){
            cin >> n >> g >> e;
            adj = vector<vector<int> >(n + 1, vector<int>(n + 1, 0));
            for (int i = 0; i < g; ++i)
            {
                int mark;
                cin >> mark;
                adj[mark][n] = 1;
                // adj[n][mark] = 1;
            }
            for (int i = 0; i < e; ++i)
            {
                int a, b;
                cin >> a >> b;
                adj[a][b] = 1;
                adj[b][a] = 1;
            }
        }

        int dfs(int from, int goal, int min_cost) {
            if(from == goal) return min_cost;
            visited[from] = true;
            for (int to = 0; to < n + 1; ++to)
            {
                if(adj[from][to] == 0 || visited[to]) continue;
                int flow = dfs(to, goal, min(min_cost, adj[from][to]));
                if(flow != 0) {
                    adj[from][to] -= flow;
                    adj[to][from] += flow;
                    return flow;
                } 
            }
            return 0;
        }

        void exec(){
            int sum_flow = 0;
            while(true) {
                visited = vector<bool>(n + 1, false);
                int flow = dfs(0, n, INF);
                if(flow == 0) {
                    cout << sum_flow << endl;
                    return;
                }
                sum_flow += flow;
            }
        }
};


int main(){
    Solver s = Solver();
    s.exec();
}