洛谷 P2071 座位安排

题目传送门

解题思路：

题目里说的很清楚，二分图的最大匹配，与模板不同的地方在于，一排座位可以连两个人。

AC代码：

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