洛谷 P2319 [HNOI2006]超级英雄

题目传送门

解题思路：

根据所给条件将题目编号和锦囊编号连边，然后跑二分图最大匹配。

AC代码：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 
 5 using namespace std;
 6 
 7 int n,m,head[1005],tot,ans,g[1005],a[1005];
 8 bool vis[1005];
 9 struct kkk{
10     int to,next;
11 }e[2005];
12 
13 inline void add(int x,int y) {
14     e[++tot].to = y;
15     e[tot].next = head[x];
16     head[x] = tot;
17 }
18 
19 inline bool find(int x) {
20     for(int i = head[x];i; i = e[i].next) {
21         int u = e[i].to;
22         if(vis[u]) continue;
23         vis[u] = 1;
24         if(g[u] == 0 || find(g[u])) {
25             g[u] = x;
26             a[x] = u;
27             return true;
28         }
29     }
30     return false;
31 }
32 
33 int main() {
34     scanf("%d%d",&n,&m);
35     for(int i = 1;i <= m; i++) {
36         int x,y;
37         scanf("%d%d",&x,&y);
38         add(i,x);
39         add(i,y);
40     }
41     for(int i = 1;i <= n; i++) {
42         memset(vis,0,sizeof(vis));
43         if(find(i)) ans++;
44         else break;
45     }
46     printf("%d
",ans);
47     for(int i = 1;i <= ans; i++) 
48         printf("%d
",a[i]);
49     return 0;
50 }