poj.3041--二部图的最小定点覆盖

本文主要是介绍poj.3041--二部图的最小定点覆盖，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

这道题可以这样转化，将每个顶点看成是一条边，每条边的起点为行，终点为列，而这题就是求覆盖所有顶点的行数和列数的和的最小值，也就是说这题可以转化为连接所有边的顶点的最小数---也即二部图的最小顶点覆盖。下面是代码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define Max 501
int pre[Max];
bool match[Max][Max];
bool vi[Max];
int n,k;
int find(int x);
int main()
{scanf("%d%d",&n,&k);int i,a,b;memset(match,false,sizeof(match));memset(pre,-1,sizeof(pre));for(i=0;i<k;i++){scanf("%d%d",&a,&b);match[a][b]=true;}int ans=0;for(i=1;i<=n;i++){memset(vi,false,sizeof(vi));if(find(i))ans++;}printf("%d\n",ans);return 0;
}
int find(int x)
{int i;for(i=1;i<=n;i++){if(match[i][x] && !vi[i]){vi[i]=true;if(pre[i]==-1 || find(pre[i])){pre[i]=x;return true;}}}return false;
}

这道题是一道非常好的题，将问题转化成二部图的最小顶点覆盖，注意体会其中转化的精髓......

这篇关于poj.3041--二部图的最小定点覆盖的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---