题目分析
题意：有n个人，编号记为1~n，n个人之间可能有人可以互相联系，如果A能和B联系，那么至少满足这两种情况之一：（1）A知道B的电话（2)A可以和C联系，并且C可以和B联系；
因为某些人可能会丢失他的手机，导致他失去所有人的号码以及其他人手机中他的号码，也就是说这个人无法和任何人联系了；
此时给出两个人s,t，问至少有多少人失去他们的手机，可以使得这两个人s,t无法联系。
答案输出最少需要的人数以及失去手机的人的编号，如果存在多组解，输出字典序小的那一组。
思路：平时写的最小割问题是求边割集，这个题题目求的是最小点割集，对于这类题目我们采用如下建边方法：
1）将每个人代表的结点拆成两个结点，记编号1~n为入点，n+1~2*n为出点，由入点向出点建一条容量为1的边
2）对于可以联系的两人 a,b，由a的出点向b的入点建一条容量为inf的边，并由b的出点向a的入点建一条容量为inf的边
3）由于源点就是某个人，那么我们将这个人的出点当作源点
建好边之后，我们跑一遍最大流（最小割）就可以得到最小点割集
个人认为这个题主要麻烦在输出割点，我的方法是不断地的删点，如果删去这一点后得到的最大流大于删这点之前的最大流，那么这个点就是割点，为保证字典序最小，因而从1开始枚举割点
代码区
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<string>
#include<fstream>
#include<vector>
#include<stack>
#include <map>
#include <iomanip> #define bug cout << "**********" << endl
#define show(x, y) cout<<"["<<x<<","<<y<<"] "
#define LOCAL = 1;
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const ll mod = ;
const int Max = 1e5 + ;
const int Max2 = 1e3 + ; struct Edge
{
int to, flow, next;
} edge[Max << ]; int n, s, t;
int head[Max2], tot;
int dis[Max2];
bool vis[][], cancel[];
int id[Max2], cnt; void init()
{
memset(head, -, sizeof(head));tot = ;
} void add(int u, int v, int flow)
{
edge[tot].to = v;
edge[tot].flow = flow;
edge[tot].next = head[u];
head[u] = tot++;
} void build()
{
init();
for (int i = ; i <= n; i++)
{
if (!cancel[i])
{
add(i, i + n, );
add(i + n, i, );
}
}
for (int i = ; i <= n; i++)
{
for (int j = ; j <= n; j++)
{
if(vis[i][j])
{
add(i + n, j, inf);
add(j, i + n, );
}
}
}
} bool bfs()
{
memset(dis, -, sizeof(dis));
queue<int> q;
q.push(s);
dis[s] = ;
while (!q.empty())
{
int u = q.front();
q.pop();
for (int i = head[u]; i != -; i = edge[i].next)
{
int v = edge[i].to;
if (edge[i].flow > && dis[v] == -)
{
dis[v] = dis[u] + ;
if (v == t)
return true;
q.push(v);
}
}
}
return false;
} int dfs(int u, int flow_in)
{
if (u == t)
return flow_in;
int flow_out = ;
for (int i = head[u]; i != -; i = edge[i].next)
{
int v = edge[i].to;
if (edge[i].flow > && dis[v] == dis[u] + )
{
int flow = dfs(v, min(flow_in, edge[i].flow));
if (flow == )
continue;
flow_in -= flow;
flow_out += flow;
edge[i].flow -= flow;
edge[i ^ ].flow += flow;
if (flow_in == )
break;
}
}
return flow_out;
} int Dinic()
{
int sum = ;
while (bfs())
{
sum += dfs(s, inf);
}
return sum;
} int main()
{
#ifdef LOCAL
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
#endif
while (scanf("%d%d%d", &n, &s, &t) != EOF)
{
memset(cancel, , sizeof(cancel));
memset(vis, , sizeof(vis));
cnt = ;
for (int i = ; i <= n; i++)
{
for (int j = ,x; j <= n; j++)
{
scanf("%d", &x);
vis[i][j] = x;
}
}
if(vis[s][t]) //s,t可以直接联系，那就不存在最小割了
{
printf("NO ANSWER!\n");
continue;
}
s += n;
build();
int min_cost = Dinic(); printf("%d\n", min_cost);
if (min_cost == )
continue;
int last = min_cost;
for (int i = ; i <= n; i++)
{
if (i + n == s || i == t)
continue;
cancel[i] = true;
build();
int temp = Dinic();
if (temp < last) //相比于不删除i点，删除i点之后最大流减少，则此点为割点
{
id[++cnt] = i;
last--;
if (cnt == min_cost)
break;
}
else
{
cancel[i] = false;
}
}
for (int i = ; i < cnt; i++)
printf("%d ", id[i]);
printf("%d\n", id[cnt]);
}
return ;
}