输入输出样例
输入 #1 复制
3 2 1 2
1 3
2 3
输出 #1 复制
1
思路
题意：这一题是问cow需要最少破话多少台电脑才能 才能使位于起点和终点位置的 cow 不能通信，也就是说这一题是让拆的是点，而不是让拆的边，我们不能够直接使用，这一题如果是让拆的是边的话，那就很简单，因为不能够通信，就意味着 在拆边之后，图的联通性就没了，图被分割成两部分，那么我们所要求的是最小割。。。。。这一题是 割点 ,当我们在破坏掉一个u 之后（假设这一条边为 u——v），我们不能够影响原来 v点的通与其他点的通信（除了u点），这一题如果我们能够把个 割点——> 转化割边 就好解决了。
思路：我们可以考虑把 一个点（假定编号为 i）拆成两个点，这两个点的编号是 ：i , i + n,在 i 与 i+1 点之间有一条权值为 1 指向 i+1 点的边（i+1这个点 和这个边是我们要用 Add函数添加进去的） ，还有一点要明白，对于题上给的边，所有与原来 i 所连的点 进入i的边 还是i ，而原来 从 i 点出去的边要变成 从 i + 1 点过出去的边，一定是可以双向通行，而且可以无线通信（所以题目上给的边就是 INF），i 点拆分后的结果
当我们把所有的点之后，再把 题目上给的边我们就得到了最终的图：
上图⬆️中 的 红线：拆点之间的边权为 1 的线，黑线是题目给的边权值为 INF
最后最后：我么要特殊考虑：源点s 与汇点e , 我们要明白 原点可以通过与 源点相连的边无限发送消息，而不是一次，所以我们 这个时候 所用的原点就变成了 s + n（这个是因为 拆点造成的）,而汇点可以通过入边无相接受消息，所以 入边 链接的还是 e （即所用的汇点e不变）
题解（Dinic）
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
#define INF 0x3f3f3f3f
const int maxn = 205;
const int maxm = 2005;
struct Edge
{
int v,w,next;
} edge[2*maxm];
int head[maxm],cur[maxm];
int deep[maxm];
int use[maxm];
int n,m,s,e;
int k = -1;
void Add(int u, int v, int w)
{
edge[++ k] = (Edge){ v, w, head[u]}; head[u] = k;
edge[++ k] = (Edge){ u, 0, head[v]}; head[v] = k;
}
//来分层用的
bool bfs(int s, int e)
{
for(int i = 0; i <= 2*n; i ++)
cur[i] = head[i], deep[i] = INF, use[i] = 0;
deep[s] = 0;
queue<int> q;
q.push(s);
int u,v;
while(! q.empty())
{
u = q.front(); q.pop();
use[u] = 0;
for(int i = head[u]; i != -1; i = edge[i].next)
{
v = edge[i].v;
if(edge[i].w && deep[v] == INF)
{
deep[v] = deep[u] + 1;
if(! use[v])
{
q.push(v);
use[v] = 1;
}
}
}
}
if(deep[e] == INF)
return false;
return true;
}
int dfs(int now, int e, int limit)
{
if(! limit || now == e) return limit;
int flow = 0,f;
for(int i = cur[now]; i != -1; i = edge[i].next)
{
if(deep[edge[i].v] == deep[now] + 1 && (f = dfs(edge[i].v, e, min(limit, edge[i].w))))
{
cur[now] = i; //当前弧优化
flow += f;
limit -= f;
edge[i].w -= f;
edge[i^1].w += f;
if(! limit)
break;
}
}
return flow;
}
int Dinic(int s, int e)
{
int mx_flw = 0;
while(bfs(s, e))
mx_flw += dfs(s, e, INF);
return mx_flw;
}
void init()
{
k = -1;
memset(head, -1, sizeof(head));
}
int main()
{
ios::sync_with_stdio(false);
//freopen("T.txt","r",stdin);
cin >> n >> m >> s >> e;
s += n;
init();
//拆点操作
for(int i = 1; i <= n; i ++)
Add(i, i + n, 1);
int u, v;
for(int i = 1; i <= m; i ++)
cin >> u >> v, Add(u + n, v, INF), Add(v + n, u, INF);
cout << Dinic(s, e) << endl;
return 0;
}