HDU 1150 Machine Schedule（二分图匹配)

浏览数：34 / 时间：2015年06月20日

解题思路：

本题要求的为最小点覆盖，最小点覆盖 == 最大匹配，要注意初始为模式0，没有消耗，所以模式0不需要连边。

#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#define LL long long
#define FOR(i, x, y) for(int i=x;i<=y;i++)
using namespace std;
const int MAXN = 200 + 10;
int G[MAXN][MAXN];
int vis[MAXN];
int match[MAXN];
int n, m;
int path(int u)
{
    for(int v=1;v<m;v++)
    {
        if(G[u][v] && !vis[v])
        {
            vis[v] = 1;
            if(match[v] == -1 || path(match[v]))
            {
                match[v] = u;
                return 1;
            }
        }
    }
    return 0;
}
int main()
{
    while(scanf("%d", &n)!=EOF)
    {
        if(n == 0) break;
        int k;
        scanf("%d%d", &m, &k);
        int x, u, v;
        memset(G, 0, sizeof(G));
        while(k--)
        {
            scanf("%d%d%d", &x, &u, &v);
            if(u > 0 && v > 0)
                G[u][v] = 1;
        }
        memset(match, -1, sizeof(match));
        int ans = 0;
        for(int i=1;i<n;i++)
        {
            memset(vis, 0, sizeof(vis));
            ans += path(i);
        }
        printf("%d\n", ans);
    }
    return 0;
}

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

HDU 1150 Machine Schedule（二分图匹配)