思路:给出一个无向图,问两点间至少需要破坏多少点,就能使得两点不连通。
思路:显然要用最大流解决,怎么建图呢,拆点,我们可以把一个点拆成
两个点,一个用来接受流量,一个用来发送流量,两点连边,流量设置为1,
然后再把边的流量也设置为1,注意是无向图,相反边也要建,这样跑最大流,
就能得到最少需要拆分的点的个数。
拆点不要大家不要怕,以为很高大上,操作起来和离散化一样其实是简单的,2x设置为接受点,2x+1设置为发送点即可
AC代码:
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 100005; const int inf = 0x3f3f3f3f; struct edge { int f, t, nxt; ll flow; }e[maxn*2]; int hd[maxn], tot = 1; void add(int f, int t, ll flow) { e[++tot] = { f,t,hd[f],flow }; hd[f] = tot; } int n, m, c1,c2; int s, d; int dep[maxn], cur[maxn]; bool bfs() {//找增广路 memset(dep, 0, sizeof(dep)); dep[s] = 1; queue<int>Q; Q.push(s); while (!Q.empty()) { int u = Q.front(); Q.pop(); for (int i = hd[u]; i; i = e[i].nxt) { int v = e[i].t, flow = e[i].flow; if (flow > 0 && !dep[v]) { dep[v] = dep[u] + 1; if (v == d)return true; Q.push(v); } } } return false; } ll dfs(int u, ll flow) { if (u == d)return flow; ll last = flow; for (int i = cur[u]; i; i = e[i].nxt) { cur[u] = i;//当前弧优化 int v = e[i].t; ll flow = e[i].flow; if (flow > 0 && dep[v] == dep[u] + 1) { ll tmp = dfs(v, min(last, flow)); last -= tmp; e[i].flow -= tmp; e[i ^ 1].flow += tmp; if (last == 0)break;//流量没了直接退出循环,与当前弧优化对应 } } if (last == flow)dep[u] = 0;//从当前点一点流量没流到终点(未找到增广路),炸点优化 return flow - last;//返回剩余流量 } ll dinic() { ll maxflow = 0; while (bfs()) { memcpy(cur, hd, sizeof(hd)); maxflow += dfs(s, inf); } return maxflow; } int main() { //freopen("test.txt", "r", stdin); scanf("%d%d%d%d", &n, &m, &c1, &c2); for (int i = 1; i <= n; i++) { add(i * 2, i * 2 + 1, 1); add(i * 2 + 1, i * 2, 0);//先拆点 } for (int i = 1; i <= m; i++) { int a, b; scanf("%d%d", &a, &b); add(a*2+1, b*2, 1); add(b*2, a*2+1, 0); add(b*2+1, a*2, 1);//无向图,反向边也需要 add(a*2, b*2+1, 0); } s = c1*2+1, d = c2*2;//起点是c1的发送点,终点是c2的接受点 ll ans = dinic(); printf("%lld\n", ans); return 0; }