Submission #6908945

---

Source Code Expand

#include <cstdlib>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <fstream>
#include <numeric>
#include <iomanip>
#include <bitset>
#include <list>
#include <stdexcept>
#include <functional>
#include <utility>
#include <ctime>
#include <random>
#include <cassert>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
#define MEM(a,b) memset((a),(b),sizeof(a))
const LL INF = 1e9 + 7;
const int N = 3e5 + 10;
const int M = 5e5 + 10;

class Graph
{
public:
	int top[N];
	struct Node
	{
		int x, y, r, pre;
	} edge[M];
	int k;
	void init(int n = N)
	{
		k = 0;
		memset(top, -1, sizeof(int) * n);
	}
	inline void addEdge(int x, int y, int w)
	{
		edge[k] = Node{ x,y,w,top[x] };
		top[x] = k++;
		edge[k] = Node{ y,x,0,top[y] };
		top[y] = k++;
	}
	inline Node& operator[] (int i)
	{
		return edge[i];
	}

} g;
int s, t;
int current[N];
int layer[N];
bool bfs(int n)
{
	memset(layer, -1, sizeof(int) * n);
	queue<int> q;
	q.push(s);
	layer[s] = 1;
	while (!q.empty())
	{
		int x = q.front();
		q.pop();
		for (int i = g.top[x]; ~i; i = g[i].pre)
		{
			int y = g[i].y;
			int r = g[i].r;
			if (r > 0 && layer[y] == -1)
			{
				layer[y] = layer[x] + 1;
				if (y == t) return true;
				q.push(y);
			}
		}
	}
	return false;
}
int dfs(int x, int tot)
{
	if (x == t) return tot;
	int ret = 0;
	for (int i = current[x]; ~i; i = g[i].pre)
	{
		int y = g[i].y;
		int r = g[i].r;
		if (r > 0 && layer[y] == layer[x] + 1)
		{
			current[x] = i;
			int tmp = dfs(y, min(r, tot - ret));
			g[i].r -= tmp;
			g[i ^ 1].r += tmp;
			ret += tmp;
			if (ret == tot) return ret;
		}
	}
	layer[x] = -1;
	return ret;
}
int solve(int n)
{
	int ret = 0;
	while (bfs(n))
	{
		memcpy(current, g.top, sizeof(int) * n);
		ret += dfs(s, INF);
	}
	return ret;
}
int main()
{
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	int n, m, e;
	cin >> n >> m >> e;
	s = 1;
	t = 2 * n + 2;
	g.init(t + 1);
	for (int i = 0; i <= n; i++)
	{
		g.addEdge(i * 2, i * 2 + 1, INF);
	}
	for (int i = 1; i <= m; i++)
	{
		int x;
		cin >> x;
		g.addEdge(x * 2 + 1, t, 1);
	}
	while (e--)
	{
		int x, y;
		cin >> x >> y;
		g.addEdge(x * 2 + 1, y * 2, 1);
		g.addEdge(y * 2 + 1, x * 2, 1);
	}
	cout << solve(t + 1) << endl;

	return 0;
}

Submission Info

Judge Result