听学长说这道题很ex，但是思路想到的话还是挺简单的。
可能是受上一道题（放置机器人）的启发，也是找互相冲突的点连线。
但是并不是完全一样（废话）放置机器人那道题是找到冲突点连线后直接求最大匹配即可。
这道题稍微把思路变换一下，求出最大完美匹配数 \(n\) 后，说明有 \(n*2\) 个人的喜好是互相冲突的。
可以认为这些人是重合的，所以我们只需要用总人数 \(k\) 减去 \(n\) 后就是最多人数。
做完以后上网搜发现都是用最大独立集做的，最后除以 \(2\) ，内涵原理应该是相同的（应该没有什么太大差异）。
附代码
点击查看代码
#include<bits/stdc++.h>
using namespace std;
int read(){
int x=0,f=1;char ch=getchar();
for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
for(;isdigit(ch);ch=getchar())x=(x<<1)+(x<<3)+(ch^48);
return x*f;
}
void write(int x){
if(x<0)putchar('-'),x=-x;
if(x>9)write(x/10);
putchar(x%10+48);
}char s[505][3];vector<int>v[505];
bool vis[505];int match[505],shu[505][3];
inline bool dfs(int x){
for(int i=0;i<v[x].size();++i){
int y=v[x][i];
if(!vis[y]){
vis[y]=1;
if(!match[y]||dfs(match[y])){
match[y]=x;return true;
}
}
}
return false;
}
int main(){
int n=read(),m=read(),k=read(),cnt=0;
for(int i=1;i<=k;++i){
s[i][1]=getchar(),shu[i][1]=read(),s[i][2]=getchar(),shu[i][2]=read();
}
for(int i=1;i<=k;i++)
if(s[i][1]=='C'){
cnt++;
for(int j=1;j<=k;j++){
if(s[j][1]=='D'){
if(shu[j][1]==shu[i][2]||shu[j][2]==shu[i][1])v[cnt].push_back(j);
}
}
}
int ans=0;
for(int i=1;i<=cnt;++i){
memset(vis,0,sizeof(vis));
if(dfs(i))ans++;
}write(k-ans);
return 0;
}
核心代码就是读入和建图，读入时用字符数组记录即可，然后建图时是只要有一项冲突就进行连边，最后跑匈牙利即可。