当前位置: 代码迷 >> 综合 >> poj 2239 Selecting Courses 二分图最大匹配
  详细解决方案

poj 2239 Selecting Courses 二分图最大匹配

热度:91   发布时间:2024-01-19 06:29:19.0

题意:

裸的二分图最大匹配。

思路:

直接用匈牙利算法的模板即可。

代码:

//poj 2239
//sepNINE
#include<iostream>
using namespace std;
const int maxN=302; int M,v1,v2;
bool g[maxN][maxN];
bool vis[maxN];
int link[maxN];bool dfs(int x)
{for(int y=1;y<=v2;++y)	if(g[x][y]&&!vis[y]){vis[y]=true;if(link[y]==0||dfs(link[y])){link[y]=x;return true;}}return false;
}void hungary()
{for(int x=1;x<=v1;++x){memset(vis,false,sizeof(vis));if(dfs(x))++M;}	return ;
}int main()
{int n;while(scanf("%d",&n)==1){memset(g,false,sizeof(g));memset(link,0,sizeof(link));int i,maxV1=-1;for(i=1;i<=n;++i){int x;scanf("%d",&x);while(x--){int a,b,c;scanf("%d%d",&a,&b);c=a*13+b;maxV1=max(maxV1,c);g[c][i]=1;}}M=0;v1=maxV1;v2=n;hungary();printf("%d\n",M);}return 0;	
}