SPFA的两个优化(转)
hdu 1569 方格取数

poj 1325 最小点覆盖

scturtle posted @ 2010年8月29日 18:48 in algorithm , 2019 阅读

描述:有A,B俩机器,各有0~n-1和0~m-1种模式.有k个任务,既可在A的某种模式下运行又可在B的某种模式下进行,求最小的模式转换次数(A,B初始为模式0).

牛人:

每个任务化为一条线,它连接着a[i]和b[j],问题转化为求(a[]和b[]中)最少的点,
使得每条线都至少有一个端点被选(这个任务就完成了)。这个就是最小点覆盖的模型了

所以是:

            scanf("%d%d%d",&j,&x,&y);
            if(x*y!=0)
                map[x][y]=1;
 

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
int n,m;
bool map[105][105];
int match[105];
bool v[105];
bool dfs(int p)
{
    int i;
    for (i = 1; i <= m; i++)
    {
        if (map[p][i] && !v[i])
        {
            v[i] = 1;
            if (match[i] == -1 || dfs(match[i]))
            {
                match[i] = p;
                return 1;
            }
        }
    }
    return 0;
}
int Hungry()
{
    int i;
    int ans = 0;
    memset(match,-1,sizeof(match));
    for (i = 1; i <= n; i++)
    {
        memset(v, false, sizeof(v));
        if (dfs(i))
            ans++;
    }
    return ans;
}
int main()
{
    freopen("in", "r", stdin);
    freopen("out", "w", stdout);
    int i,k,j,x,y;
    while(scanf("%d%d%d",&n,&m,&k)!=EOF && n!=0)
    {
        memset(map,false,sizeof(map));
        for (i = 1; i <= k; i++)
        {
            scanf("%d%d%d",&j,&x,&y);
            if(x*y!=0)
                map[x][y]=1;
        }
        printf("%d\n",Hungry());
    }
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter