POJ 1325 Machine Schedule 最小点覆盖

机器A的所有模式为左部顶点，机器B的所有模式为右部顶点，然后A与B之间的每条连线代表一个任务或工作

之后就要完成所有的任务，即将每条边都覆盖

对一个有向图，若要覆盖每条边，至少需要的点数为二分图最大匹配数

建图的方法还是拆点。

代码如下

/*
ID: sdj22251
PROG: inflate
LANG: C++
*/
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#define MAXN 105
#define INF 1000000000
using namespace std;
int nx, ny;
vector<int>g[MAXN];
int cx[MAXN], cy[MAXN];
int mark[MAXN];
int path(int u)
{
    int x = g[u].size();
    for(int i = 0; i < x; i++)
    {
        int v = g[u][i];
        if(!mark[v])
        {
            mark[v] = 1;
            if(cy[v] == -1 || path(cy[v]))
            {
                cx[u] = v;
                cy[v] = u;
                return 1;
            }
        }
    }
    return 0;
}
int maxmatch()
{
    int res = 0;
    memset(cx, -1, sizeof(cx));
    memset(cy, -1, sizeof(cy));
    for(int i = 1; i <= nx; i++)
    {
        if(cx[i] == -1)
        {
            memset(mark, 0, sizeof(mark));
            res += path(i);
        }
    }
    return res;
}
int main()
{
    while(scanf("%d", &nx) != EOF && nx)
    {
        int t, x, y;
        nx--;
        for(int i = 0; i <= nx; i++)
            g[i].clear();
        scanf("%d%d", &ny, &t);
        ny--;
        while(t--)
        {
            scanf("%*d%d%d", &x, &y);
            if(!x || !y) continue;
            g[x].push_back(y);
        }
        printf("%d\n", maxmatch());
    }
    return 0;
}