POJ1325.md

对于一个任务可以被A的某个模式完成，也可以被B的某个模式完成，要求最终转换的模式数最少。 每个人物看可以被A的modex做，也可以被B的modey做，那就把x和y连边，最后其实就要找最小点覆盖，二分图最小点覆盖=二分图最大匹配

#include<cstring>
#include<cstdio>
#include<iostream>
using namespace std;
const int MAXN = 1111;
int n,m,k,match[MAXN];
bool vis[MAXN];
struct Graph{
    int head[MAXN],to[MAXN],nxt[MAXN],tot;
    void init(){ tot = 0; memset(head,255,sizeof(head)); }
    void ADDEDGE(int u, int v){
        tot++;
        to[tot] = v;
        nxt[tot] = head[u];
        head[u] = tot;
    }
}G;
bool dfs(int u){
    vis[u] = true;
    for(int i = G.head[u]; ~i; i = G.nxt[i]){
        int v = G.to[i];
        if(match[v]==-1||(!vis[match[v]]&&dfs(match[v]))){
            match[v] = u;
            return true;
        }
    }
    return false;
}
int solve(){
    memset(match,255,sizeof(match));
    int tot = 0;
    for(int i = 1; i <= n; i++){
        memset(vis,0,sizeof(vis));
        if(dfs(i)) tot++;
    }
    return tot;
}
int main(){
    while(scanf("%d",&n)!=EOF, n){
        scanf("%d %d",&m,&k);
        G.init();
        n--, m--;
        for(int i = 1; i <= k; i++){
            int x, y;
            scanf("%d %d %d",&x,&x,&y);
            if(!x || !y) continue;
            G.ADDEDGE(x,y);
        }
        printf("%d\n",solve());
    }
    return 0;
}