Submission #2213647

---

Source Code Expand

#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();
}

Submission Info

Judge Result