学步园

pku 3014

题意：有个r行c列的棋盘，上面的某些方格中有怪物，现在你能做的一次操作是将其中一行或一列的怪物都消灭掉，问将所有怪物都消灭掉的最少次数是多少？

pku 1325

题意：

A B两台机器分别有n,m(0…n-1, 0…m-1)种工作模式，初始时都处于0模式。而且如果机器要改变模式，必须重启（重启就是回到0模式）。现在有k个任务，每个任务都可以被A或B的某些模式完成。

问最少需要重启多少次？

分析：倆道题目我们都可以这样理解：

第一个题目: 在棋盘上的每一个怪物，都可选择被该行消灭还是被该列消灭，这是行与列就是一种匹配；

而第二个题目：对与每一个任务，有俩种选择，可以选择被A的某种模式或者B的某种模式完成，这时，这俩种模式便是一种匹配；

那么问题就顺理成章的转变为求最小覆盖数了，（选择最小的行或列，选择最小的模式），而最小覆盖数又等于最大匹配数，这样问题就解决了

#include<iostream>
using namespace std;
int n,match[510];
bool vis[510],g[510][510];
int path(int s)
{
for(int i=1;i<=n;i++)
    {
if(g[s][i]&&!vis[i])
        {
            vis[i]=1;
if(match[i]==-1||path(match[i]))
            {
                match[i]=s;
return 1;
            }
        }
    }
return 0;
}
int main()
{
int k,a,b;
while(scanf("%d %d",&n,&k)==2)
    {
        memset(g,0,sizeof(g));
        memset(match,-1,sizeof(match));
for(int i=0;i<k;i++)
        {
            scanf("%d %d",&a,&b);
            g[a][b]=1;
        }
int ans=0;
for(int i=1;i<=n;i++)
        {
            memset(vis,0,sizeof(vis));
            ans+=path(i);
        }
        printf("%d\n",ans);
    }
return 0;
}

pku 1325

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
using namespace std;
bool g[210][210],vis[210];
int match[210],n,m,k;
int path(int s)
{
for(int i=1;i<=m;i++)
if(g[s][i]&&!vis[i])
        {
            vis[i]=1;
if(match[i]==-1||path(match[i]))
            {
                match[i]=s;
return 1;
            }
        }
return 0;
}
int main()
{
int a,b,c;
while(scanf("%d",&n)==1&&n)
    {
        scanf("%d %d",&m,&k);
        memset(g,0,sizeof(g));
        memset(match,-1,sizeof(match));
for(int i=1;i<=k;i++)
        {
            scanf("%d %d %d",&a,&b,&c);
            g[b][c]=1;
        }
int ans=0;
for(int i=1;i<=n;i++)
        {
            memset(vis,0,sizeof(vis));
            ans+=path(i);
        }
        printf("%d\n",ans);
    }
return 0;
}