一看就是一个最大流最小割的题。
建图：每个人i掰成两个点：i与i'，作为入点与出点。
i向i'连一个容量1的边。
如果a有b的号码，就从a'向b连一个容量∞的边。
S和S'间再连一个无穷大的边，
T和T'间再连一个无穷大的边，保证S和T不会被割掉。

跑完最大流后怎么输出方案呢？
整体思路：
for i=0 to n-1
   if <i,i'>可以是割边，即i可以被隔离
       记录i，把<i,i'>容量--，计算新的最大流。

首先，让我们看看如何判定一个边<i,i'>可以出现在最小割中：
那就是：<i,i'>剩余流量为0，沿着残余网络，找不到一个从i到i'的路径。
为什么？这样，一旦把<i,i'>的容量降低1，那最大流量也会降低1，所以
<i,i'>可以在一个最小割中。
这个判定可以用一次dfs完成。

其次，如果每次删完点后都重新跑一遍最大流，那就太脑残了。
我的方法：
从汇点开始，沿着残余网络找一条
T->i'->i->S的“逆增广路”，沿路退流（流量--），之后在
残余网络中把<i,i'>和<i',i>的剩余流量都设置成0，就完成了
降低流量并计算新流的工作。

至于最大流算法的选择，我想对发帖

神奇 dinic 正向bfs勉强过。。反向700ms。。。 (0) 200731000904 2009-05-13 18:59:47 Problem 1815

的那位说我们探讨的dinic很可能不是一个东西。我的成绩：
6299151 AllwaysLoser 1815 Accepted 308K 94MS C++ 2470B 2010-01-03 22:40:17 
这就叫有提交就会有奇迹。

示例代码：
struct edge{
	int e,f;
	edge *next,*opt;
}epool[20000],*etop;
int N,S,T,n,s,t;
edge *E[NMax],*mark[nMax];
void addEdge(int a,int b,int c){
	etop->e=b;etop->f=c;etop->next=E[a];E[a]=etop;etop->opt=etop+1;etop++;
	etop->e=a;etop->f=0;etop->next=E[b];E[b]=etop;etop->opt=etop-1;etop++;
}
int level[NMax],queue[NMax];
int Min(int a,int b){return a<b?a:b;}
int findp(int u,int alpha){int r=0,t;
	if (u==T || !alpha)return alpha;
	for (edge *p=E[u];p;p=p->next)if (p->f && level[p->e]==level[u]+1){
		t=findp(p->e,Min(p->f,alpha-r));
		r+=t;p->f-=t;p->opt->f+=t;
	}
	if (!r)level[u]=-1;
	return r;
}
int makeLevel(){
	for (int i=0;i<N;i++)level[i]=-1;
	int bot=1,x;
	level[queue[0]=S]=0;
	for (int top=0;top<bot;top++){x=queue[top];
		for (edge *p=E[x];p;p=p->next)if (p->f && level[p->e]==-1)
			level[queue[bot++]=p->e]=level[x]+1;
	}
	return level[T]!=-1;
}
int Dinic(){
	int flow=0,t;
	while (makeLevel())while ((t=findp(S,100000000)))flow+=t;
	return flow;
}
int extend(int x,int a){
	if (x==a+a+1)return mark[a]->f++,mark[a]->opt->f--,1;
	level[x]=0;
	for (edge *p=E[x];p;p=p->next)if (p->f && level[p->e] && extend(p->e,a))
		return p->f--,p->opt->f++,1;
	return 0;
}
int extend(int a){
	for (int i=0;i<N;i++)level[i]=1;
	return extend(a+a,a);
}
int dfs1(int x,int t){
	if (x==t)return 1;
	level[x]=0;
	for (edge *p=E[x];p;p=p->next)if (p->f && level[p->e] && dfs1(p->e,t))
		return p->f--,p->opt->f++,1;
	return 0;
}
void kill(int a){
	for (int i=0;i<N;i++)level[i]=1;
	dfs1(T,a+a+1);
	mark[a]->f=0;mark[a]->opt->f=0;
	for (int i=0;i<N;i++)level[i]=1;
	dfs1(a+a,S);
}

        etop=epool;
	scanf("%d %d %d",&n,&s,&t);s--;t--;
	N=n+n;S=s+s;T=t+t+1;
	for (int i=0;i<N;i++)E[i]=NULL;
	for (int i=0;i<n;i++){
		mark[i]=etop;
		if (i!=s && i!=t)
			addEdge(i+i,i+i+1,1);
		else addEdge(i+i,i+i+1,100000000);
	}
	int x,ret;
	for (int i=0;i<n;i++)for (int j=0;j<n;j++){
		scanf("%d",&x);
		if (x && i!=j)
			addEdge(i+i+1,j+j,100000000);
	}
	ret=Dinic();
	if (ret==100000000){
		puts("NO ANSWER!");
	}else{
		x=0;
		printf("%d\n",ret);
		for (int i=0;i<n;i++)if (i!=s && i!=t){
			if (!mark[i]->f && !extend(i)){
				printf("%d",i+1);
				if (x!=ret-1)putchar(' ');
				else puts("");
				x++;
				kill(i);
			}
		}
	}

• 万分感谢，正是我需要的。。。 (3324) RectaFlex 2010-02-05 21:20:58
• 顶。。楼上好思路。。 (0) joy_w 2010-04-14 23:36:39
• Re:雁过留声——输出最小割的字典序最小方案。 (5) lianzhouxiaowu 2010-09-27 15:18:47