http://www.zybbs.org/JudgeOnline/problem.php?id=2184

【第一次写那么长的题解啊囧……】

Obviously……求出给定图的最大匹配ANS后，有ANS*2个人就满足了，剩余N-ANS*2个人还要找人讲话，于是使得班里最吵的最少说话者对数就是ANS+(N-ANS*2)=N-ANS，于是答案就是N-ANS-1。

问题转化为什么求一般图的最大匹配……WQ神神犇给出了一种我无法立杰的神犇算法，果断不会写！像我这种菜鸟只能写写带花树……

好吧我承认，如果你看过某个模板以后会发现这个代码和那个基本一样……没错……背代码党出现了！

一直以为带花树是一种很难懂而且很难写的算法，现在再来看……还是一种很难写的算法，但是还是比较好懂得。

我用的是BFS，DFS也是可以的而且貌似会更快，但是我没找到相关代码……所以……

一开始写了70+行，后来发现好多地方可以改，最后改成50行了……终于比树链剖分短了……但是对于速度还是不很满意啊。

每次将一个点提根，把这个点染成白色。如果图中没有奇环，那么就可以对整张图进行黑白染色（即原图是二分图）。其中白点入队列，黑点有from表示这个黑点是从哪个点来的，白点的from=-1。如果BFS到一个N元奇环，那么：

1.必定是从一个白点U的非匹配边连向另一个白点V组成。

2.这个环上必定已经匹配了(N-1)/2条边（可以自己画一下看看）。

3.由2得，这个环上所有的点的当前匹配边的对面那个点，不在这个环里的只有一个，即只有一条环外匹配边。这么说可能有点混乱，其实就是，把这个环缩成一个大点（环内匹配边全部缩掉）后，这个大点对外也只有一条匹配边，自己画下。

由这三点就可以知道可以缩点了。重点和容易写错的地方就在于怎么缩点！缩点是把整个花朵映射到BASE上，步骤如下：

1.由于是BFS的，所以要先找环中最先visit的点，也即外向匹配的那个白点（DFS也许不用找，是不是DFS就快在这里？还是我哪里写搓了？）：这个点就是U和V的LCA。这个LCA暴力查找即可。注意：根节点也算向外匹配。

2.对于U和V分别把U和V所属的BASE的所有点的BASE改成第1步中找到的那个LCA。不过这里的改BASE其实还没改，只是标记了这个点在花朵中（因为如果这个点是一个花朵的话要修改花朵中所有点的BASE）。改BASE很好理解，缩点嘛。但是看代码会发现还要改FROM，这是为什么呢？等等说。（还有，这里能用并查集么？我觉得是不行的，网上有一个代码说是用了并查集，但是速度和这个一样快，而且代码中也没看到findfather……）

3.遍历所有点，若一个点的BASE被标记在花朵中的话，就修改这个点的BASE，并且加入队列。

现在来解释第2步为什么改FROM。为了解决一个点不知道自己应该是黑还是白的问题，我们新建一个白色人工节点，然后把原来的那些点中除了外向匹配的那个白点外的点，都变成黑点，这样他们就都有FROM了。这其中有几个问题：

1.不是新建白色节点么？怎么代码里没有？

答：外向匹配的那个白点（BASE）恰好可以代替这个人工节点，新建节点过于麻烦。

2.环中的其他点不是都变成黑点了么？为什么还加入队列？不是只有白点才入队么？

答：用那个白点代替了人工节点后，其他点的边还没有映射到这个白点上。把那些黑点加入队列只是为了遍历这个人工节点所拥有的边，即这个环所拥有的边。这个操作就相当与把那个白色的人工节点加入队列。

3.环中的黑点FROM怎么定？（注意：无论是原来就是黑点的点还是原来是白点的点，只要不是BASE都可能要改FROM）

这个必须自己画图，否则很难立杰。比如想象戊烷上装了一个乙基：Z...F___A...B___C...D___E...A，Z是根，先找到了F，F找到了A，然后从A开始找了一圈又回到了A。

现在假设我们的B点有一条未匹配边B...S，那么增广路就是S...B___C...D___E...A___F...Z（注意：增广时是按照FROM,MATCH,FROM,MATCH……这样增广的。）。这就可以知道C点的FROM是D，E点的FROM是A。

再假设我们的E点有一条未匹配边E...S，那么增广路变为S...E___D...C___B...A___F...Z，得到D的FROM是C，B的FROM是A。

看出来了罢！对于环中的未匹配边A...B，A的FROM应该改为B，B的FROM应该改为A！当然，BASE的FROM不改：因为BASE还是白点，所以FROM=-1。

从上面的分析可以看出，将人工节点映射到BASE上在空间、时间、编程复杂度上都有大幅度降低（说实话让我加人工节点的话我还真不知道应该怎么写 =。=）.

至此所有问题都解决了……开动罢！加油！

#include <stdio.h>
#include <string.h>
#define maxn 1000
#define maxm 3000
int n,m=0,match[maxn],ans=0,base[maxn],from[maxn],que[maxn],bq,eq;
_Bool v[maxn],in[maxn],anc[maxn];
struct edge{struct edge *next;int y;}*map[maxn],st[maxm<<1],*p;
inline getint(){
	int re=0,ch=getchar();
	while(ch<'0'||ch>'9')if((ch=getchar())<=0)return 0;
	for(;ch>='0'&&ch<='9';ch=getchar())re=re*10+ch-48;
	return re;
}inline bfs(x){
	int i,f;
	memset(from,-1,sizeof(from));memset(v,0,sizeof(v));
	for(i=0;i<n;i++)base[i]=i;
	for(v[que[bq=0]=x]=eq=1;bq!=eq;bq++)for(p=map[que[bq]];p;p=p->next)if(base[i=que[bq]]!=base[f=p->y]&&f!=match[i]){
		if(f==x||match[f]!=-1&&from[match[f]]!=-1){
			memset(in,0,sizeof(in));memset(anc,0,sizeof(anc));
			for(i=base[i];(anc[i]=1)&&match[i]!=-1;i=base[from[match[i]]]);
			for(f=base[f];!anc[f];f=base[from[match[f]]]);
			for(i=que[bq];base[i]!=f&&(in[base[i]]=in[base[match[i]]]=1);i=from[i])if(base[from[i=match[i]]]!=f)from[from[i]]=i;
			for(i=p->y;base[i]!=f&&(in[base[i]]=in[base[match[i]]]=1);i=from[i])if(base[from[i=match[i]]]!=f)from[from[i]]=i;
			if(base[que[bq]]!=f)from[que[bq]]=p->y;
			if(base[p->y]!=f)from[p->y]=que[bq];
			for(i=0;i<n;i++)if(in[base[i]]){
				base[i]=f;
				if(!v[i])v[que[eq++]=i]=1;
			}
		}else if(from[f]==-1){
			from[f]=i;
			if(match[f]==-1){
				for(;(i=f)!=-1;match[match[i]=from[i]]=i)f=match[from[i]];
				return 1;
			}else v[que[eq++]=match[p->y]]=1;
		}
	}return 0;
}inline void ADDEDGE(x,y){
	st[m^1].next=map[st[m].y=y];
	st[m].next=map[st[m^1].y=x];
	map[x]=st+m++;map[y]=st+m++;
}main(){
	int i,M;
	while(i=n=getint()){
		memset(match,-1,sizeof(match));memset(map,0,sizeof(map));
		for(ans=m=0,M=getint();M--;ADDEDGE(getint()-1,getint()-1));
		while(i--)if(match[i]==-1)ans+=bfs(i);
		printf("%d\n",n-1-ans);
	}return 0;
}

• inline
• block