Submission #1574167

---

Source Code Expand

#include <iostream>
#include <array>
#include <map>
#include <algorithm>
#include <cmath>
#include <vector>
#include <fstream>
#include <string>
#include <random>
#include <queue>
#include <iomanip>
#include <functional>
#include <climits>

using namespace std;

using ll = long long int;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vll = std::vector<ll>;
using vpll = std::vector<pll>;

const ll mod197 = 1000000007LL;
const ll INF = INT_MAX;

const double PI11 = 3.14159265359;

//最大公約数
ll gcd(ll a, ll b) {
	if ( a%b == 0 )
		return b;
	return gcd(b,a%b);
}

//最小公倍数
ll lcm(ll a, ll b) {
	return a / gcd(a, b) * b;
}

// (a ^ b) % mod
ll powMod(ll x, ll k, ll m) {
	if (k == 0)     return 1;
	if (k % 2 == 0) return powMod(x*x % m, k / 2, m);
	else            return x*powMod(x, k - 1, m) % m;
}

ll combi(ll n, ll k) {

	if (n < k) {
		swap(n, k);
	}

	ll a = 1, b = 1;

	for (ll i = n; i > n-k; i--) {
		a *= i;
		a %= mod197;
	}
	for (ll i = k; i > 0; i--) {
		b *= i;
		b %= mod197;
	}


	//cout << endl << a << " " << b << endl;

	//(n/a)%p = (n*a^(p-2))%p
	return (a*powMod(b, mod197 - 2, mod197)) % mod197;
}

//int main(void) {
//
//	ll a, b;
//	cin >> a >> b;
//
//	cout << combi(a+b-1, b) << endl;
//
//	return 0;
//}
//

struct edge {
	int to, cap, rev;

	edge() {
		to = cap = rev = -1;
	}
	edge(int t,int c,int r) : to(t), cap(c), rev(r) {

	}

};

using vedge = vector<edge>;

vedge arr[110] = {};

bool used[110] = {};

int n, g, e;

int dfs(int v, int t, int f) {
	if (v == t) return f;

	used[v] = true;

	for (int i = 0; i < arr[v].size(); i++) {
		edge &e = arr[v][i];

		if (!used[e.to] && e.cap > 0) {
			int d = dfs(e.to, t, min(f, e.cap));

			//cout << v << " " << d << endl;

			if (d > 0) {
				e.cap -= d;
				arr[e.to][e.rev].cap += d;
				return d;
			}
		}
	}

	return 0;
}

int max_flow(int s,int t){

	int flow = 0;

	while (true) {

		fill(used,used+110,false);

		int f = dfs(s,t,INF);
		//cout << "flow " << f << endl;
		if (f == 0)return flow;
		flow += f;
	}

}

int main() {

	cin >> n >> g >> e;

	for (int i = 0; i < g; i++) {
		int p;
		cin >> p;

		arr[p].push_back(edge(n, 1, arr[n].size()));
		arr[n].push_back(edge(p, 1, arr[p].size() - 1));
	}

	for (int i = 0; i < e; i++) {
		int a, b;
		cin >> a >> b;

		arr[a].push_back(edge(b, 1, arr[b].size()));
		arr[b].push_back(edge(a, 1, arr[a].size()-1));

	}

	cout << max_flow(0,n) << endl;


	return 0;
}

Submission Info

Judge Result