poj 1469 COURSES //題意:現(xiàn)在有p門課程和n個學生,現(xiàn)在需要有由p個學生組成的組織,該組織滿足每個學生代表一門課程以及每門課程只能由一個學生代表, //現(xiàn)給出每門課程都有哪些學生可以參加,要求判斷是否存在滿足題意所需要的組織. //求解二分圖的最大匹配數(shù),如果與p相等就輸出"YES",否則輸出"NO". poj 1469 COURSES #include<iostream> //二分圖的最大匹配
#include<cstring>
using namespace std;
int p,n;
int result[301]; //result記錄V2中的點匹配的點的編號
int edge[101][301],vis[301]; //vis記錄V2中的每個點是否被搜索過
bool find(int a)
{
for(int i=1;i<=n;++i)
{
if(edge[a][i]==1&&vis[i]==0) //如果節(jié)點i與a相鄰并且未被查找過
{
vis[i]=1; //標記i為已查找過
if( result[i]==0 || find(result[i])==true ) //如果i未在前一個匹配M中或者 i在匹配M中，但是從與i相鄰的節(jié)點出發(fā)可以有增廣路
{
result[i]=a; //記錄查找成功記錄
return true; //返回查找成功
}
}
}
return false;
}
int main()
{
int cases;
scanf("%d",&cases);
while(cases--)
{
memset(edge,0,sizeof(edge));
memset(result,0,sizeof(result));
scanf("%d%d",&p,&n);
int m,t;
for(int i=1;i<=p;++i)
{
scanf("%d",&m);
while(m--)
{
scanf("%d",&t);
edge[i][t]=1;
}
}
int ans=0;
for(int i=1;i<=p;++i)
{
memset(vis,0,sizeof(vis)); //清空上次搜索時的標記
if(find(i)==true) //從節(jié)點i嘗試擴展
ans++;
}
if(ans==p)
printf("YES\n");
else
printf("NO\n");
}
return 0;
}

　　

轉(zhuǎn)載于:https://www.cnblogs.com/mjc467621163/archive/2011/07/19/2111046.html

總結(jié)

以上是生活随笔為你收集整理的二分图匹配----匈牙利算法之二的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。