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

poj 1325 最小点覆盖

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

描述:有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());
    }
}
cleaning services du 说:
2020年2月23日 13:08

It is actually easy enough to look for at least a handful of commercial rug cleaning service companies within driving distance just by just looking during the yellow sites, checking any advertising component to your publication, or carrying out a search on line. The next step is to sit and learn a little bit more about each professional rug cleaning companies you are looking for so you do feel confident that there is chosen right. Following happen to be some tips that will help decide.

bank of baroda rtgs 说:
2022年10月03日 16:05

Bank of BarodaFor RTGS - amount must be Rs.21- lac and above / For NEFT by cash maximum amount upto Rs. 49,999/-). Application. Bank of BarodaFor RTGS - amount must be Rs.21- lac and above / For NEFT by cash maximum amount upto Rs. 49,999/-). Application. Bank of Baroda (BOB) Download RTGS NEFT Fillable / Auto Fill / Editable pdf Form (featured with Auto Filling amount in words). bank of baroda rtgs form Bank of Baroda (BOB) Download RTGS NEFT Fillable / Auto Fill / Editable pdf Form (featured with Auto Filling amount in words).Bank of BarodaFor RTGS - amount must be Rs.21- lac and above / For NEFT by cash maximum amount upto Rs. 49,999/-). Application. Bank of Baroda (BOB) Download RTGS NEFT Fillable / Auto Fill / Editable pdf Form (featured with Auto Filling amount in words).


登录 *


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