HDU3605 Escape 多重匹配

给出每个人适合住的星球信息和该星球能住多少人，第一行给出n m 代表有 n 个人 m 个星球，然后接下来n行每行m个数字，代表可以住到第 i 个星球，0代表不可以住到第 i 个星球，最后一行m个数表示第 i 个星球最多可以住多少个人，问是不是所有人都可以搬离地球，

以前的匹配左集合中一个点对应右集合中的一个点，点只能使用一次，现在变成左集合中的一个点对应右集合中的多个点，而右集合中的点还是只能对应左集合中的一个点，

这道题目一开始做一直是超时的，直到修改了一个地方就过了，个人觉得是题目数据不好，又是900ms

#include<iostream>  
#include<cstdio>  
#include<list>  
#include<algorithm>  
#include<cstring>  
#include<string>  
#include<queue>  
#include<stack>  
#include<map>  
#include<vector>  
#include<cmath>  
#include<memory.h>  
#include<set>  
  
#define ll long long  
#define LL __int64  
#define eps 1e-8  
const ll INF=9999999999999;  
  
using namespace std;  
  
#define M 400000100  
  
#define inf 0xfffffff  
  
//vector<pair<int,int> > G;  
//typedef pair<int,int> P;  
//vector<pair<int,int>> ::iterator iter;  
//  
//map<ll,int>mp;  
//map<ll,int>::iterator p;  
  
//vector<int>G[8000];  
  
int mp[100012][22];  
int num[22];  
int marry[22];  
bool vis[22];  
int tempmp[22][100012];  
  
int dis[2][4]={0,-1,0,1,1,0,-1,0};  
  
int n,m,k;  
  
void clear()  
{  
    memset(tempmp,0,sizeof(tempmp));  
    memset(marry,0,sizeof(marry));  
    memset(num,0,sizeof(num));  
    memset(vis,false,sizeof(vis));  
    memset(mp,0,sizeof(mp));  
    /*for(int i=0;i<=n;i++) 
        G[i].clear();*/  
}  
  
bool dfs(int x)  
{  
    for(int i=0;i<m;i++)  
    {  
        if(mp[x][i] && !vis[i])  
        {  
            vis[i]=true;  
            if(marry[i]<num[i])//这里的标记数组不一样了，不是之前的简单以为就能解决的，要是一个二维的，而且要遵循星球所住人数有限的限定  
            {  
                tempmp[i][marry[i]++]=x;//这里的marry数组跟以前意义大不一样，marry[i]=j，就是i跟左集合中的点匹配了j次  
                return 1;  
            }  
            for(int j=0;j<marry[i];j++)//比如marry[i]=j，要在i与各个点匹配中去寻找，  
            {  
                if(dfs(tempmp[i][j]))  
                {  
                    tempmp[i][j]=x;  
                    return 1;  
                }  
            }  
        }  
    }  
    return 0;  
}  
  
int main(void)  
{  
    while(cin>>n>>m)  
    {  
        clear();  
        for(int i=0;i<n;i++)  
        {  
            for(int j=0;j<m;j++)  
            {  
                scanf("%d",&mp[i][j]);  
            }  
        }  
        for(int i=0;i<m;i++)  
            scanf("%d",&num[i]);//因为星球住的人数有限所以要设一个数组来限制  
        int ans=0;  
        for(int i=0;i<n;i++)  
        {  
            memset(vis,false,sizeof(vis));  
            if(!dfs(i))  
            {  
                ans=1;//本来这里用的是常用的ans++,如果ans==n就输出YES，不然就输出NO，可是那样超时了，现在直接标记，有出现不可匹配的直接输出NO，这样就过了，我觉得是题目数据有问题  
                break;  
            }  
        }  
        if(ans)  
            puts("NO");  
        else  
            puts("YES");  
    }  
}

补充：软件开发 , C++ ,