[题目链接]
https://www.lydsy.com/JudgeOnline/problem.php?id=1585
[算法]
一个最小割的经典模型 ， 详见代码
时间复杂度 : O(dinic(2N , 2C))
[代码]
#include<bits/stdc++.h> using namespace std; #define MAXN 8010 #define MAXC 50010 const int inf = 2e9; struct edge { int to , w , nxt; } e[MAXC << 1]; int tot , n , c , p , S , T; int a[MAXN] , depth[MAXN], head[MAXN]; template <typename T> inline void chkmax(T &x,T y) { x = max(x,y); } template <typename T> inline void chkmin(T &x,T y) { x = min(x,y); } template <typename T> inline void read(T &x) { T f = 1; x = 0; char c = getchar(); for (; !isdigit(c); c = getchar()) if (c == '-') f = -f; for (; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + c - '0'; x *= f; } inline void addedge(int u , int v , int w) { ++tot; e[tot] = (edge){v , w , head[u]}; head[u] = tot; ++tot; e[tot] = (edge){u , 0 , head[v]}; head[v] = tot; } inline bool bfs() { int l , r; static int q[MAXN]; q[l = r = 1] = S; memset(depth , 0 ,sizeof(depth)); depth[S] = 1; while (l <= r) { int cur = q[l++]; for (int i = head[cur]; i; i = e[i].nxt) { int v = e[i].to , w = e[i].w; if (w > 0 && !depth[v]) { depth[v] = depth[cur] + 1; q[++r] = v; if (v == T) return true; } } } return false; } inline int dinic(int u , int flow) { int rest = flow , ret = 0; if (u == T) return flow; for (int i = head[u]; i && rest; i = e[i].nxt) { int v = e[i].to , w = e[i].w; if (depth[v] == depth[u] + 1 && w) { int k = dinic(v , min(rest , w)); if (!k) depth[v] = 0; e[i].w -= k; e[i ^ 1].w += k; rest -= k; } } return flow - rest; } int main() { read(n); read(c); read(p); S = 2 * n + 1 , T = S + 1; tot = 1; addedge(S , 1 , inf); for (int i = 1; i <= c; i++) { int x , y; read(x); read(y); addedge(x + n , y , inf); addedge(y + n , x , inf); } for (int i = 1; i <= p; i++) { int x; read(x); a[x] = true; } addedge(1 , n + 1 , inf); for (int i = 2; i <= n; i++) { if (a[i]) { addedge(i , n + i , inf); addedge(i , T , inf); } else addedge(i , n + i , 1); } int ans = 0; while (bfs()) { while (int flow = dinic(S , inf)) ans += flow; } printf("%d " , ans); return 0; }