Cat VS Dog

真的是很巧妙的建边。
我刚开始就想着猫和狗了。
但事实上我们应该把小孩子当作节点，相互冲突的小孩连上边然后求最大独立集

真的女少口阿

我们事实上建造的是一个有向图，对一个有向图求解最大匹配。
因为这里我们没有将整个图分为左右节点所以我选择的是匈牙利算法而不是hk算法。
其实我想用hk算法的，但是我没有在不分图的情况下的hk
惨。。。

#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#include<cstring>
using namespace std;
const int max_n=550;
const int max_m=550*550;
const int inf = 1e9;
struct edge{
    int to,next;
}E[max_m<<1];
int head[max_n];
int cnt=1;
void add(int from,int to){
    E[cnt].to=to;E[cnt].next=head[from];
    head[from]=cnt++;
}
int To[max_n];
int vis[max_n];
bool match(int u){
    for (int i=head[u];i;i=E[i].next){
        int v = E[i].to;
        if (vis[v])continue;
        vis[v]=1;
        if (To[v]==-1||match(To[v])){
            To[v]=u;
            return true;
        }
    }return false;
}

int Hungarian(int N) {
    int cct = 0;
    fill(To,To+N+1,-1);
    for (int i = 1; i <= N; ++i) {
        fill(vis,vis+max_n,0);
        if (match(i)) cct++;
    }return cct;
}
int like[max_n],dislike[max_n];
int main(){
    ios::sync_with_stdio(0);
    int n,m,p;
    while (cin>>n>>m>>p){
        fill(head,head+p+5,0);cnt=1;
        for (int i=1,u,v;i<=p;++i){
            char c;
            cin>>c>>u;
            if (c=='D')u+=n;
            cin>>c>>v;
            if (c=='D')v+=n;
            like[i]=u;dislike[i]=v;
        }
        for (int i=1;i<=p;++i)
            for (int j=1;j<=p;++j)
                if (like[i]==dislike[j]||dislike[i]==like[j])
                    add(i,j);
        printf("%d\n",p-Hungarian(p)/2);
    }
}