【二分圖】HDU1150 最小頂點覆寫

二分圖小總結：

1、最小頂點覆寫 = 最大比對數

最小頂點覆寫：實質是個點集，點集裡面的點能覆寫所有的邊，最小點覆寫就是滿足這個要求的點集中點數最小的那個

2、最大獨立集 =  頂點個數V - 最大比對數

最大獨立集：實質是個點集，點集裡面的點互相之間不連着，最大獨立集就是滿足這個要求的點集中點數最多的那個

3、最小邊覆寫 = 頂點個數V - 最大比對數

最小邊覆寫：實質是個邊集，這個集合裡的邊能覆寫所有的點，最小邊覆寫是滿足這個要求的所有邊集中邊數最少的一個

這裡頂點數等于總的頂點數

• HDU 1150 （最小頂點覆寫）

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;

int Map[105][105];
int match[105]; ///比對
int vis[105]; ///通路
int n,m;

int Find(int x){
    for(int i=1; i<=m; i++)
        if(vis[i] == 0 && Map[x][i]){
            vis[i] = 1;
            if(match[i] == -1 || Find(match[i])){
                match[i] = x;
                return 1;
            }

        }

    return 0;
}

int main()
{
    int k;
    while(1){
        scanf("%d", &n);
        if(!n) break;
        scanf("%d%d", &m, &k);
        memset(Map, 0, sizeof Map);
        memset(match, -1, sizeof match);
        for(int i=0; i<k; i++){
            int a,b,c;
            scanf("%d%d%d", &a, &b, &c);
            Map[b][c] = 1;
        }
        int ans = 0;
        for(int i=1; i<=n; i++){
            memset(vis, 0, sizeof vis);
            if(Find(i)) ans++;
        }
        printf("%d\n", ans);
    }
    return 0;
}