模板 匈牙利算法
标签：怎么 continue scan scanf include printf algo for 最大
二分图匹配，学好了就能找到对象。
我们将这个问题直男化，男生只要对象不冲突，就不存在找不到的情况，女生也不会甩掉男生。
那么，各位单身狗大佬们，怎么才能找到对象呢。
首先，要抢占先机。
最大匹配，可以根据这一步的贪心完成，如果当前这个人没有对象，就要找，而且尽量不抢别人的。
当然先进入的先找。
其次，可以抢那些花心萝卜的。
花心萝卜可以有多个选择，反正你看别人也好不如把你的让给我，而不能去抢那些没有备胎的，这样不道德。
成功就配对，尽快脱单。
大概就是这样。
假如说n个男生，m个女生，e个喜好关系，求最大匹配。（luogu3386）
代码：
1 #include 2 #include 3 #include
4 struct pnt{
5 int hd;
6 int mate;
7 bool thought_of;
8 }p[1000000];
9 struct ent{
10 int twd;
11 int lst;
12 }e[1000000];
13 int n,m;
14 int ne;
15 int cnt;
16 void fall_in_love(int p1,int p2)
17 {
18 p[p1].mate=p2;
19 p[p2].mate=p1;
20 return ;
21 }
22 void likes(int f,int t)
23 {
24 cnt++;
25 e[cnt].twd=t;
26 e[cnt].lst=p[f].hd;
27 p[f].hd=cnt;
28 return ;
29 }
30 bool looking_for_a_mate(int person)
31 {
32 for(int i=p[person].hd;i;i=e[i].lst)
33 {
34 int lover=e[i].twd;
35 if(!p[lover].thought_of)
36 {
37 p[lover].thought_of=true;
38 if((!p[lover].mate)||looking_for_a_mate(p[lover].mate))
39 {
40 fall_in_love(person,lover);
41 return true;
42 }
43 }
44 }
45 return false;
46 }
47 int Max_num_of_couple(void)
48 {
49 int ans=0;
50 for(int i=1;i)
51 if(!p[i].mate)
52 {
53 for(int j=1;j)
54 p[j].thought_of=false;
55 if(looking_for_a_mate(i))
56 ans++;
57 }
58 return ans;
59 }
60 int main()
61 {
62 scanf("%d%d%d",&n,&m,&ne);
63 for(int i=1;i)
64 {
65 int a,b;
66 scanf("%d%d",&a,&b);
67 if(a>n||b>m)
68 continue;
69 b+=n;
70 likes(a,b);
71 }
72 printf("%d\n",Max_num_of_couple());
73 return 0;
74 }
模板 匈牙利算法
标签：怎么 continue scan scanf include printf algo for 最大
原文地址：https://www.cnblogs.com/blog-Dr-J/p/9744541.html
文章来自：
搜素材网的
编程语言模块，转载请注明文章出处。
文章标题：
模板 匈牙利算法
文章链接：http://soscw.com/index.php/essay/87245.html
评论