二分图

这里是用匈牙利算法来求无权二分图的最大匹配问题。

题目大致：

有n个男生，m个妹子，他们之间有相互喜欢的关系。如何匹配使得相互喜欢并凑成一对的人最多。

正常的思路是使用什么增广路和交叉路，我也看不明白，但这个链接讲的比较容易懂。

大致思路就是：

1.建立一个链表。

2.遍历喜欢此男生的所有妹子，如果有妹子没人要，就给这个男生。

3.如果有一悲催男，喜欢他的妹子都名花有主了，那就再遍历那些“主”，看看他们能否选择其他没人要的妹子，把这个妹子空出来给那个悲催男。

4.统计能配成一对的个数。

代码：

 1 #include<cstdio>
 2 #include<cstring>
 3 #define N 420000
 4 int head[N],to[N],next[N];
 5 int n,m,e,a,b;
 6 int y,used[N],visit[N],num,tot;
 7 int find(int x){
 8     for(int i=head[x];i;i=next[i]){
 9         y=to[i];
10         if(!used[y]){
11             used[y]=1;
12             if(!visit[y]||find(visit[y])){
13                 visit[y]=x;
14                 return 1;
15             }
16         }
17     }
18     return 0;
19 }
20 int main(){
21     scanf("%d%d%d",&n,&m,&e);
22     for(int i=1;i<=e;++i){
23         scanf("%d%d",&a,&b);
24         next[++num]=head[a];
25         to[num]=b;
26         head[a]=num;
27     }
28     for(int i=1;i<=n;++i){
29         memset(used,0,sizeof(used));
30         if(find(i))
31             tot++;
32     }
33     printf("%d",tot);
34     return 0;
35 }

View Code

唯一可能不理解的地方就是那个used数组，它的意思是第i个妹子有没有被预定。

if(!used[y]){
            used[y]=1;
            if(!visit[y]||find(visit[y])){
                visit[y]=x;
                return 1;
            }
        }

举个例子：

男1喜欢女1，男1也喜欢女2。但男2只喜欢女1。

所以遍历过男1后，把男1和女1连在一起。再遍历男2,发现男2只喜欢的女1被男1占了。所以再去搜索男1，看看男1能不能和别的人匹配。但如果直接find(男1)，还是会把男1和女1连在一起，所以就把used(女1)设为1，意思是女1被人(男2)预定了，所以，男1就去找女2了。

最终，男1和女2在一起了，男2和女1在一起了。

放电视剧里这绝逼是一个催人泪下的故事。。

在每次搜索的时候，都会有一个

memset(used,0,sizeof(used));

表示重置这个数组，防止上一次的妹子预定和这一次的产生冲突。