洛谷 P2071 座位安排（二分图匹配）

 1 #include<iostream>
 2 #include<cstring>
 3 using namespace std;
 4 int n,ans,vis[2005][2],ok[2005][2];
 5 int m[4005][2];
 6 bool check(int u){
 7     for(int i=0;i<=1;i++){
 8         int v=m[u][i];
 9         for(int j=0;j<=1;j++){
10             if(vis[v][j]) continue;
11             vis[v][j]=1;
12             if(!ok[v][j]||check(ok[v][j])){
13                 ok[v][j]=u;
14                 return true;
15             }
16         }
17     }
18     return false;
19 }
20 int main(){
21     cin>>n;
22     for(int i=1;i<=2*n;i++){
23         cin>>m[i][0]>>m[i][1];
24     }
25     for(int i=1;i<=2*n;i++){
26         memset(vis,0,sizeof(vis));
27         if(check(i)) ans++;
28     }
29     cout<<ans;
30     return 0;
31 }