BZOJ 1191: [HNOI2006]超级英雄Hero【二分图匹配】

裸的匹配题，一眼就能看出来二分图的模型，是某个经典题的改编。貌似某本图论书上讲过的，有N个人以及M个职位，每个职位只能提供给一个人，而每个人由于能力有限只能胜任有限个职位，问是否有办法使得每个人都有工作，如果不能，最多能给多少个人提供工作。如果看过这道经典题的话，这题的思路就顺秒了：将n道题看成n个点属于二分图的x部，将m个锦囊看成m个点属于y部，用匈牙利算法做这个二部图的匹配，当某个点不能匹配时算法结束

值的一说的是，由于这个二部图的特性，x部每个点有且仅有2条边与y部相连，利用这个特性能够大大优化这个算法（下面这个程序属于无脑敲的匈牙利，没用这个优化。。。。竟然也能过）

#include<iostream>

#include<cstdio>

#include <math.h>

#include <string.h>

using namespace std;

intmatch[1009],visit[1009]={0},n,map[1009][1009]={0};

int dfs(int k)

{

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

{

if (map[k][i]==1 && visit[i]==0)

{

visit[i]=1;

if ((match[i]==-1) || (dfs(match[i])==1))

{

match[i]=k;

return 1;

}

return 0;

}

int main()

{

int m,ans=0,x,y;

scanf("%d%d",&n,&m);

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

{

scanf("%d%d",&x,&y);

map[i][x]=1;

map[i][y]=1;

}

memset(match,255,sizeof(match));

for (inti=1;i<=m;i++)

{

memset(visit,0,sizeof(visit));

if (dfs(i)==1)ans++;else break;

}

printf("%d",ans);

scanf("%d%d",&n,&m);

return0;

}

巴特西

BZOJ 1191: [HNOI2006]超级英雄Hero【二分图匹配】

最新文章

热门文章