二分图： HDU1498 & poj3041

1A，这个是poj3041的升级版，做法很简单，而且很暴力哈哈哈，具体方法下面介绍。

AC代码：

#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int maxn=1e2+10;
const int inf=0x3f3f3f3f;

int n,k;

int ori[maxn][maxn];
bool mp[maxn][maxn];

int mate[maxn];
bool used[maxn];

bool Findm(int x)
{
    for(int i=1;i<=n;i++)
    {
        if(!used[i]&&mp[x][i])
        {
            used[i]=1;
            if(!mate[i]||Findm(mate[i]))
            {
                mate[i]=x;
                return 1;
            }
        }
    }
    return 0;
}
int main()
{
    while(scanf("%d%d",&n,&k)==2&&n&&k)
    {
        int maxnum=-1;
        memset(ori,0,sizeof(ori));
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
            {
                scanf("%d",&ori[i][j]);
                if(maxnum<ori[i][j])
                    maxnum=ori[i][j];
            }


        vector<int> v;
        v.clear();
        for(int p=1;p<=maxnum;p++)
        {
            memset(mp,0,sizeof(mp));
            for(int i=1;i<=n;i++)
                for(int j=1;j<=n;j++)
                    if(ori[i][j]==p)
                        mp[i][j]=1;


            int temp=0;
            memset(mate,0,sizeof(mate));
            for(int i=1;i<=n;i++)
            {
                memset(used,0,sizeof(used));
                temp+=Findm(i);
            }

            if(temp>k)
            {
                v.push_back(p);
            }
        }

        if(v.size())
        {
            for(int i=0;i<v.size();i++)
            {
                if(i) printf(" ");
                printf("%d",v[i]);
            }
            printf("\n");
        }
        else printf("-1\n");

    }
}

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <cmath>
using namespace std;
const int maxn=5e2+10;

int N,K;
bool mp[maxn][maxn];

bool used[maxn];
int mate[maxn];
bool Findm(int x)
{
    for(int i=1;i<=N;i++)
    {
        if(!used[i]&&mp[x][i])
        {
            used[i]=1;
            if(!mate[i]||Findm(mate[i]))
            {
                mate[i]=x;
                return 1;
            }
        }
    }
    return 0;
}
int main()
{
    while(scanf("%d%d",&N,&K)==2)
    {
        memset(mp,0,sizeof(mp));
        for(int i=1;i<=K;i++)
        {
            int t1,t2;
            scanf("%d%d",&t1,&t2);
            mp[t1][t2]=1;
        }

        int ans=0;
        memset(mate,0,sizeof(mate));
        for(int i=1;i<=N;i++)
        {
            memset(used,0,sizeof(used));
            ans+=Findm(i);
        }
        printf("%d\n",ans);
    }
}