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;

}