P2071 座位安排
思路
二分图模板。
考虑将一排拆成两个座位，座位在右，人在左。
然后人去匹配座位即可。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
int n, vis[10005], ans, rec[10005];
vector<int> g[4005];
int dfs(int u, int t)
{if(vis[u] == t) return 0;vis[u] = t;for(int v : g[u]){if(rec[v] == 0 || dfs(rec[v], t)){rec[v] = u;return 1;}}return 0;
}
signed main()
{cin >> n;for(int i = 1; i <= 2 * n; i ++){int x, y; cin >> x >> y;g[i].push_back(x + 2 * n), g[i].push_back(x + 3 * n);g[i].push_back(y + 2 * n), g[i].push_back(y + 3 * n);}for(int i = 1; i <= 2 * n; i ++){if(dfs(i, i)) ans ++;}cout << ans << endl;
}