最小割的好题,可用作模板。
//Dinic+枚举字典序最小的最小割点集
//Time:1032Ms Memory:1492K
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std; #define MAXN 205
#define INF 0x3f3f3f3f int N, S, T;
int s,t;
int sres[2*MAXN][2*MAXN]; //source-res
int res[2*MAXN][2*MAXN];
int d[2*MAXN];
int cut[MAXN]; //最小割点集
bool v[2*MAXN]; bool bfs()
{
memset(d, -1, sizeof(d));
queue<int> q;
q.push(s); d[s] = 0;
while(!q.empty() && d[t] == -1){
int cur = q.front(); q.pop();
for(int i = 1; i <= t; i++)
{
if(d[i] == -1 && res[cur][i])
{
d[i] = d[cur] + 1;
q.push(i);
}
}
}
return d[t] != -1;
} int dfs(int x, int sum)
{
if(x == t || sum == 0) return sum;
int src = sum;
for(int i = 1; i <= t; i++)
{
if(d[i] == d[x] + 1 && res[x][i])
{
int tmp = dfs(i, min(sum, res[x][i]));
res[x][i] -= tmp;
res[i][x] += tmp;
sum -= tmp;
}
}
return src - sum;
} int Dinic()
{
memcpy(res, sres, sizeof(sres));
int maxFlow = 0;
while(bfs())
maxFlow += dfs(s,INF);
return maxFlow;
} int main()
{
//freopen("in.txt", "r", stdin); while(~scanf("%d%d%d", &N,&S,&T))
{
memset(sres, 0 ,sizeof(sres));
s = 0; t = 2*N+1;
sres[0][S] = sres[T+N][t] = INF;
for(int i = 1; i <= N; i++)
{
sres[i][i + N] = 1;
for(int j = 1; j <= N; j++)
{
int num;
scanf("%d", &num);
if(num && i != j) sres[i+N][j] = INF;
}
}
sres[S][S+N] = sres[T][T+N] = INF;
int ans = Dinic();
if(ans == INF){ //不可分开
printf("NO ANSWER!\n");
continue;
}
else {
printf("%d\n", ans);
if(ans == 0) continue; //已经分开
} //枚举最小割点集
int len = 0, tmp = ans;
for(int i = 1; i <= N && tmp; i++)
{
if(i == S || i == T) continue;
if(res[i][i+N]) continue;
sres[i][i+N] = 0;
int k = Dinic();
if(k != tmp){
tmp = k;
cut[len++] = i;
}
else sres[i][i+N] = 1;
}
for(int i = 0; i < ans - 1; i++)
printf("%d ", cut[i]);
printf("%d\n", cut[ans-1]);
} return 0;
}