洛谷 P2071 座位安排题解
因为一个人坐一个座位很像二分图，题意转化为二分图最大匹配。
把人放在左部，把座位放在右部，一排座位占右部的两个点。
假设人想要坐在 \(x\) 排，那么建图的时候就可以将这个人连向 \(2x\) 和 \(2x+1\)。这样一排就对应着两个人了。由于 \(n\le 4000\)，直接由朴素的 \(O(nm)\) 的匈牙利算法求最大匹配即可。
代码
int n;
int vis[maxn<<1];
vector<int> G[maxn<<1];
void add(int x,int y) {
pb(G[x],y);
}
int to[maxn];
int ans=0;
int dfs(int now) {
int sz=G[now].size();
For(i,0,sz-1) {
int v=G[now][i];
if(!vis[v]) {
vis[v]=1;
if(!to[v]||dfs(to[v])) return to[v]=now,1;
}
}
return 0;
}
signed main() {
in1(n);
For(i,1,n<<1) {
int x,y;
in2(x,y);
add(i,x<<1),add(i,x<<1|1);
add(i,y<<1),add(i,y<<1|1);
}
For(i,1,n<<1) m0(vis),ans+=dfs(i);
cout<<ans;
return 0;
}