原题链接
割去点使得无向图不连通，和最小割相似。
我们可以将点转化成边，这样就能跑最小割了。
枚举每两个不能直接到达的点(S,T)，使得删去一些点（除去这两个点）使得这两个点不连通（若两点能直接到达显然无解），然后我们按下面的方法建立新图：
- 将每个点(x)，拆成两个点(x_1,x_2)，对(forall x e S,x e T)，由(x_1)向(x_2)连一条容量为(1)的边。
- 对于原来图中每条边((x,y))，连接((x_2,y_1))和((y_2,x_1))，容量为(+infty)。
然后以(S_2)为源点，(T_1)为汇点，求最小割即可。
注意(nleqslant 1)或最终求出的最小割为(+infty)时，答案为(n)。
#include<cstdio>
#include<cstring>
using namespace std;
const int N = 1010;
const int M = 1e4 + 10;
struct eg {
int x, y;
};
eg b[M];
int fi[N], ne[M], di[M], da[M], cu[N], de[N], q[M << 4], l, st, ed, n, m;
bool a[52][52];
inline int re()
{
int x = 0;
char c = getchar();
bool p = 0;
for (; c <'0' || c > '9'; c = getchar())
p |= c == '-';
for (; c >= '0' && c <= '9'; c = getchar())
x = x * 10 + c - '0';
return p ? -x : x;
}
inline void add(int x, int y, int z)
{
di[++l] = y;
da[l] = z;
ne[l] = fi[x];
fi[x] = l;
di[++l] = x;
da[l] = 0;
ne[l] = fi[y];
fi[y] = l;
}
inline int minn(int x, int y)
{
return x < y ? x : y;
}
bool bfs()
{
int head = 0, tail = 1, i, x, y;
memset(de, 0, sizeof(de));
de[st] = 1;
q[1] = st;
while (head ^ tail)
{
x = q[++head];
for (i = fi[x]; i; i = ne[i])
if (!de[y = di[i]] && da[i] > 0)
{
de[y] = de[x] + 1;
if (!(y ^ ed))
return true;
q[++tail] = y;
}
}
return false;
}
int dfs(int x, int k)
{
int y, mi;
if (!(x ^ ed))
return k;
for (int &i = cu[x]; i; i = ne[i])
if (!(de[y = di[i]] ^ (de[x] + 1)) && da[i] > 0)
{
mi = dfs(y, minn(k, da[i]));
if (mi > 0)
{
da[i] -= mi;
da[i ^ 1] += mi;
return mi;
}
}
return 0;
}
void bumap()
{
int i;
memset(fi, 0, sizeof(fi));
l = 1;
for (i = 1; i <= n; i++)
if (i ^ (st - n) && i ^ ed)
add(i, i + n, 1);
for (i = 1; i <= m; i++)
{
add(b[i].x + n, b[i].y, 1e9);
add(b[i].y + n, b[i].x, 1e9);
}
}
int main()
{
int i, j, x, y, s, mi, k, o;
while (scanf("%d%d", &n, &m) == 2)
{
o = n << 1;
mi = 1e9;
memset(a, 0, sizeof(a));
for (i = 1; i <= m; i++)
{
x = re() + 1;
y = re() + 1;
a[x][y] = a[y][x] = 1;
b[i].x = x;
b[i].y = y;
}
for (i = 1; i < n; i++)
for (j = i + 1; j <= n; j++)
if (!a[i][j])
{
st = i + n;
ed = j;
bumap();
s = 0;
while (bfs())
{
for (k = 1; k <= o; k++)
cu[k] = fi[k];
while ((x = dfs(st, 1e9)) > 0)
s += x;
}
mi = minn(mi, s);
}
printf("%d
", mi == 1e9 || n <= 1 ? n : mi);
}
return 0;
}