本身最小割什么的不难。输出解和特殊情况的判断比较恶心。
题意，n个人的两两关系矩阵，如果a认识b，则b认识a，且认识有传递性。给出一个s和一个t，问想让s不认识t，最少需要去掉多少人。
如果有解，输出字典序最小的解。（根据那个式子推出）
注意，解为0和无解是两种情况。（无解唯一会发生在s与t直接相连的时候，即去掉多少点都不能截断这个流；而解为0的含义是，s和t一开始就是断的，初始流为0）
坑爹啊！！！这题意隐藏的真深啊！！！最小点割转化为最小边割的一般写法：拆点，将p->p'的容量赋值为点权，此题为1，而源汇不拆或者源汇拆点后容量为正无穷；然后if map[i][j] == true，则连边i'->j，容量正无穷。
初始流一遍最大流。
然后开始枚举拆点/拆边。
按字典序枚举点，如果是源汇则跳过，否则重新建图的时候拆掉该点/该边，重新流，如果流减小，说明该点属于最小字典序割集，加入割集。
所以，对于枚举的每个点，还需要判断一下，是否已存在于割集中，如果已存在于割集中则果断拆掉，否则不拆。
记得每次流完之后，如果流量减小则更新最大流，作为下一次枚举的比较值。
这样最后就求出了最小字典序割集，输出即可；如果割集大小为0则无解。
记得在枚举之前先判断一下是否初始流为0，如果为0则不用流了，答案为0。（有解但无须拆点。）
其实无解的情况唯一会发生在源汇直接相连的时候。所以其实应该特判无解，而不是特判0，就不会wa那么久了。。坑爹啊。。。
附代码：
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define maxn 405
#define maxm 50005
const int inf = 100000;
struct edge
{
int p,next,val;
edge(){}
edge(int a,int b,int c):p(a),next(b),val(c){}
}e[maxm];
int tot,n,N,S,T,flow[maxn],pre[maxn],v[maxn],arc[maxn],d[maxn],cnt[maxn],path[maxn];
void init()
{
tot = 0;
n = N + N + 1;
fill(v,v + n + 1,-1);
fill(cnt,cnt + n + 1,0);
fill(d,d + n + 1,0);
cnt[0] = n + 1;
}
void add(int p,int q,int val)
{
e[tot] = edge(q,v[p],val);
v[p] = tot++;
e[tot] = edge(p,v[q],0);
v[q] = tot++;
}
int mflow()
{
int sum,now,i,k,least,loc;
int s = 0,t = n;
bool flag;
for(int i = 0;i <= n;i++)
arc[i] = v[i];
for(sum = 0,now = inf,i = s;d[s] < n + 1;)
{
flow[i] = now;
for(flag = false,k = arc[i];~k;k = e[k].next)
{
if(e[k].val && d[i] == d[e[k].p] + 1)
{
now = min(now,e[k].val);
pre[e[k].p] = i;
path[e[k].p] = k;
arc[i] = k;
i = e[k].p;
if(i == t)
{
for(sum += now;i != s;i = pre[i])
{
e[path[i]].val -= now;
e[path[i] ^ 1].val += now;
}
now = inf;
}
flag = true;
break;
}
}
if(!flag)
{
for(least = n + 1,k = v[i];~k;k = e[k].next)
{
if(e[k].val && d[e[k].p] < least)
{
least = d[e[k].p];
loc = k;
}
}
cnt[d[i]]--;
if(!cnt[d[i]])
break;
d[i] = least + 1;
cnt[d[i]]++;
arc[i] = loc;
if(i != s)
{
i = pre[i];
now = flow[i];
}
}
}
return sum;
}
bool old[maxn][maxn];
int sol[maxn];
int ans;
int main()
{
while(scanf("%d %d %d",&N,&S,&T) == 3)
{
memset(old,0,sizeof(old));
for(int i = 1;i <= N;i++)
for(int j = 1;j <= N;j++)
{
int opt;
scanf("%d",&opt);
if(opt)
old[i][j] = 1;
else
old[i][j] = 0;
}
ans = 0;
init();
add(0,S,inf);
add(T + N,n,inf);
for(int i = 1;i <= N;i++)
{
if(i == S || i == T)
add(i,i + N,inf);
else
add(i,i + N,1);
}
for(int i = 1;i <= N;i++)
for(int j = 1;j <= N;j++)
if(old[i][j])
add(i+N,j,inf);
int FLOW = mflow();
if(FLOW == 0)
{
puts("0");
continue;
}
for(int i = 1;i <= N;i++)
{
if(i == S || i == T)
continue;
init();
add(0,S,inf);
add(T + N,n,inf);
for(int j = 1;j <= N;j++)
{
if(j == S || j == T)
{
add(j,j + N,inf);
continue;
}
if(j == i)
continue;
bool flag = false;
for(int k = 0;k < ans;k++)
if(sol[k] == j)
{
flag = true;
break;
}
if(!flag)
add(j,j + N,1);
}
for(int j = 1;j <= N;j++)
for(int k = 1;k <= N;k++)
if(old[j][k])
add(j + N,k,inf);
int temp = mflow();
if(temp < FLOW)
{
sol[ans++] = i;
FLOW = temp;
}
}
if(ans == 0)
puts("NO ANSWER!");
else
{
printf("%d\n",ans);
for(int i = 0;i < ans;i++)
printf("%d%c",sol[i],(i==ans-1?'\n':' '));
}
}
}
Down