bzoj 1191: [HNOI2006]超级英雄Hero

一开始还以为用2-SAT。。

愣了几分钟才发现是二分图匹配，

用匈牙利算法找匹配碰到一个不能匹配的就退出就可以了。

 1 /*
 2 ID:WULALA
 3 PROB:bzoj1191 
 4 LANG:C++
 5 */
 6 #include <cstdio>
 7 #include <cstring>
 8 #include <algorithm>
 9 #include <cmath>
10 #include <iostream>
11 #include <ctime>
12 #include <set>
13 #define N 1008
14 #define M 1008
15 #define mod
16 #define mid(l,r) ((l+r) >> 1)
17 #define INF 0x7ffffff
18 using namespace std;
19 
20 int n,m,tot,Link[M],ans,head[N],vis[M];
21 
22 struct WULALA
23 {
24     int node,next;
25 }e[2 * N];
26 
27 bool find(int a)
28 {
29     int c = head[a];
30     for (;c;c =e[c].next)
31         if (!vis[e[c].node])
32         {
33             vis[e[c].node] = true;
34             if (Link[e[c].node] == -1 || find(Link[e[c].node]))
35             {
36                 Link[e[c].node] = a;
37                 return true;
38             }
39         }
40     return false;
41 }
42 
43 int main()
44 {
45     scanf("%d%d",&m,&n);
46     memset(Link,255,sizeof(Link));
47     for (int i = 1;i <= n;i++)
48     {
49         int a,b;
50         scanf("%d%d",&a,&b);
51         e[++tot].node = a;
52         e[tot].next = head[i];
53         head[i] = tot;
54         e[++tot].node = b;
55         e[tot].next = head[i];
56         head[i] = tot;
57     }
58     for (int i = 1;i <= n;i++)
59     {
60         memset(vis,0,sizeof(vis));
61         if (find(i)) ans++;
62         else break;
63     }
64     printf("%d
",ans);
65     return 0;
66 }

View Code