本文主要是介绍HDU-1150 HK二分图最小点覆盖，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
//二分图最小点覆盖 = 二分图最大匹配#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std;
const int maxn = 105;
const int inf = 1<<30;
int nx,ny,m;
int dis;
int map[maxn][maxn];
int cx[maxn],cy[maxn];
int dx[maxn],dy[maxn];
bool vis[maxn];//Hopcroft-Karp算法 有点类似dinic 都是先对图BFS分层再沿层数DFS找增广路
//***************************************************************************
bool searchpath() //BFS 对二分图分层
{queue<int>que;dis = inf;memset( dx,-1,sizeof(dx) );memset( dy,-1,sizeof(dy) );for( int i = 1; i <= nx; i ++ ) //找到x集合所有未被匹配的点压入队列中{if( cx[i] == -1 ){que.push(i);dx[i] = 0;}}while( !que.empty() ){int u = que.front(); que.pop();if( dx[u] > dis )break;for( int v = 1; v <= ny; v ++ ){if( map[u][v] && dy[v] == -1 ){dy[v] = dx[u] + 1;if( cy[v] == -1 )dis = dy[v];else{dx[cy[v]] = dy[v] + 1;que.push( cy[v] );}}}}return dis != inf;
}bool findpath( int u ) //沿着层数DFS
{for( int v = 1; v <= ny; v ++ ){if( map[u][v] && !vis[v] && dy[v] == dx[u] + 1 ){vis[v] = 1;if( cy[v] != -1 && dy[v] == dis )continue;if( cy[v] == -1 || findpath( cy[v] ) ){cy[v] = u;cx[u] = v;return true;}}}return false;
}
int MaxMatch()
{int ans = 0;memset( cx,-1,sizeof(cx) );memset( cy,-1,sizeof(cy) );while( searchpath() ){memset( vis,0,sizeof(vis) );for( int i = 1; i <= nx; i ++ ){if( cx[i] == -1 ){ans += findpath( i );}}}return ans;
}
//****************************************************************int main()
{int k,x,y;while( scanf("%d",&nx ) != EOF , nx ){scanf("%d%d",&ny,&m);memset( map,0,sizeof(map) );for( int i = 1; i <= m; i++ ){scanf("%d%d%d",&k,&x,&y);map[x][y] = 1;}printf("%d\n", MaxMatch() );}
}这篇关于HDU-1150 HK二分图最小点覆盖的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
