POJ 1469 COURSES(二分图最大匹配)
http://poj.org/problem?id=1469
题意:
有P门课和N个学生,每门课可能有0个或多个学生选修想选.现在问你能不能找到一种选课方案,使得P门课每门课都正好只有1个学生选修,且任意两个选了课的学生所选的课都不同?
分析:
注意:二分图是无向图,但是二分图中的g数组只保存从左边点集到右边点集的边.即g[i]==j,只代表左边i点与右边j点连接了一条无向边,不代表右边i点也与左边j点连了边. 以上结论一定要牢记.
因为只有课与学生之间存在边,所以该图可以看成是左边有P个点,右边有N个点的二分图.
又由于我们想使得课与学生连的边最多且每个学生只能连一门课,每门课也只能有一个学生连接(即每个学生或每门课最多只有一条边依附).所以这就是一个匹配问题且是最大匹配.
现在要求这个图的最大匹配,看看能否该最大匹配边数目==P.
AC代码:
#include<cstdio>
#include<cstring>
using namespace std;
struct Max_Match
{
int p,n;//左右两点集的点个数
bool g[110][310];//邻接矩阵,g[i][j]=true表示从左边第i个节点到右边第j个节点有边
int left[310];//left[i]==j表右边第i个点与左边第j个点匹配,为-1表无点匹配
bool vis[310];//表右边第i个点是否已经被访问过
void init()
{
memset(g,0,sizeof(g));
memset(left,-1,sizeof(left));
}
bool match(int i)
{
for(int j=1;j<=n;j++)if(g[i][j] && !vis[j])
{
vis[j]=true;
if(left[j]==-1 || match(left[j]) )
{
left[j]=i;
return true;
}
}
return false;
}
int solve()
{
int ans=0;//记录匹配边数目
for(int i=1;i<=p;i++)
{
memset(vis,0,sizeof(vis));
if(match(i)) ans++;
}
return ans;
}
}MM;
int main()
{
int T; scanf("%d",&T);
while(T--)
{
MM.init();
bool ok=true;
scanf("%d%d",&MM.p,&MM.n);
for(int i=1;i<=MM.p;i++)
{
int num;
scanf("%d",&num);
if(num)
{
while(num--)
{
int j;
scanf("%d",&j);
MM.g[i][j]=true;
}
}
else ok=false;
}
if(ok) printf("%s\n",MM.solve()==MM.p?"YES":"NO");
else printf("NO\n");
}
return 0;
}
AC代码2:用vector实现邻接矩阵
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
struct Max_Match
{
int p,n;//左右两点集的点个数
vector<int> g[110];//邻接矩阵,g[i]中保存的是左边第i个节点所连的右边节点的编号
int left[310];//left[i]==j表右边第i个点与左边第j个点匹配,为-1表无点匹配
bool vis[310];//表右边第i个点是否已经被访问过
void init()
{
for(int i=0;i<110;i++) g[i].clear();
memset(left,-1,sizeof(left));
}
bool match(int i)
{
for(int k=0;k<g[i].size();k++)
{
int j=g[i][k];
if(!vis[j])
{
vis[j]=true;
if(left[j]==-1 || match(left[j]) )
{
left[j]=i;//此步相当于将增广路取反
return true;
}
}
}
return false;
}
int solve()
{
int ans=0;//记录匹配边数
for(int i=1;i<=p;i++)
{
memset(vis,0,sizeof(vis));
if(match(i)) ans++;
}
return ans;
}
}MM;
int main()
{
int T; scanf("%d",&T);
while(T--)
{
MM.init();
bool ok=true;
scanf("%d%d",&MM.p,&MM.n);
for(int i=1;i<=MM.p;i++)
{
int num;
scanf("%d",&num);
if(num)
{
while(num--)
{
int j; scanf("%d",&j);
MM.g[i].push_back(j);
}
}
else ok=false;
}
if(ok) printf("%s\n",MM.solve()==MM.p?"YES":"NO");
else printf("NO\n");
}
return 0;
}
分享到:
相关推荐
poj openjudge 1111题最大正向匹配 提交ac
【二分图顶点覆盖->最小割->最大流->Dinic算法求解】 解题报告+AC代码 http://hi.csdn.net/!s/WKVPR0 ----> 我的所有POJ解题报告 http://blog.csdn.net/lyy289065406/article/details/6642573
初期: 一.基本算法: (1)枚举. (poj1753,poj2965) (2)贪心(poj1328,poj2109,poj2586) ... (5)二分图的最大匹配 (匈牙利算法) (poj3041,poj3020) (6)最大流的增广路算法(KM算法). (poj1459,poj3436) ......
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
acm.pku.edu.cn/OnlineJudge上一些已经通过的代码
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
北大POJ初级-图算法 解题报告+AC代码
poj2516代码最小费用最大流
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
poj分类poj分类poj分类poj分类
北大POJ1159-Palindrome 解题报告+AC代码
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
poj online judge 1050 最大子矩阵动态规划解决
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
POJ1503解答 POJ1503解答,正确答案(已通过POJ)
北大POJ2002-Squares 解题报告+AC代码
POJ1048,加强版的约瑟夫问题 难度中等