hdu 3605 二分图多重匹配

//题目描述:世界末日即将到来，地球上有n个人想转移到m个外星球，但是不同的人适应于不同的星球(1个人可适应多个星球)，每个外星球都有人数的限制，现在给你星球人数的上限。还有每个人不同的适应情况。问，能否安排所有的人都成功地转移到外星球上。

//解题思路:赤裸裸的2分图多重匹配(思想类似于匈牙利2分匹配，不知道该怎么分析时间复杂度。。。输入注意要用scanf)

//2分图多重匹配，可作为入门2分图多重匹配的题

#include <iostream>

using namespace std;

const int MAXN = 100000+10;

const int MAXM = 10+2;

int map[MAXN][MAXM];

int cap[MAXM]; //cap[i] 表示i点的匹配上限

int vlink[MAXM]; //vlink[i] 表示i点当前的匹配数

int link[MAXM][MAXN]; //link[i][j] 表示与i点匹配好的第j个点

bool used[MAXM];

int n,m;

int dfs(int k)

{

for(int i=0; i<m; i++)

{

if(!used[i] && map[k][i])

{

used[i] = 1;

if(vlink[i] < cap[i]) //i点的匹配数尚未达到上限，可直接匹配

{

link[i][vlink[i]++] = k; //k做为i的第vlink[i]个匹配点

return true;

}

//如果i点的匹配数已经达到上限，则遍历之前与i匹配的点，若它能与别的点匹配，则将位置让出来给k

for(int j=0; j<vlink[i]; j++)

{

if(dfs(link[i][j])) //能与其他点匹配

{

link[i][j] = k; //让出位置给k

return true;

}

}

}

}

return false;

}

int maxMatch()

{

// memset(link,0,sizeof(link));

memset(vlink,0,sizeof(vlink));

for(int k=0; k<n; k++)

{

memset(used,0,sizeof(used));

if(!dfs(k))

{

return false;

}

}

return true;

}

int main()

{

while(cin>>n>>m)

{

for(int i=0; i<n; i++)

{

for(int j=0; j<m; j++)

{

scanf("%d",&map[i][j]);

}

}

for(int i=0; i<m; i++)

{

cin>>cap[i];

}

if(maxMatch())

{

cout<<"YES"<<endl;

}

else

{

cout<<"NO"<<endl;

}

}

return 0;

}