|
|
Posted on 2010-08-21 18:34 acronix 阅读(1643) 评论(0) 编辑 收藏 引用 所属分类: hzshuai收集的模板
匈牙利算法：
 
//poj_1469
/*==================================================*\
| 二分图匹配（匈牙利算法DFS 实现）
| INIT: g[][]邻接矩阵;
| 优点：实现简洁容易理解，适用于稠密图，DFS找增广路快。
| 找一条增广路的复杂度为O（E），最多找V条增广路，故时间复杂度为O（VE）
\*==================================================*/
#include <cstdio>
#include <memory.h>
bool g[110][310],flag,vis[310];
int match[310];
int p,n;
/************* 匈牙利算法**************/
int SearchPath(int u)
{
for (int v = 1; v <= n; v ++)
if (g[u][v] && ! vis[v])
{
vis[v] = true;
if (match[v] == -1 || SearchPath(match[v]))
{
match[v] = u;
return 1;
}
}
return 0;
}
/**********************************/
int main()
{
int i,j,k,t,v,cnt;
scanf("%d",&t);
while (t--)
{
scanf("%d %d", &p, &n);
for (i = 1; i <= p; i++)
for (j = 1; j <= n; j++)
g[i][j] = false;
for (i = 1; i <= n; i++)
match[i] = -1;
flag = true;
for (i = 1; i <= p; i++)
{
scanf("%d",&k);
if (k == 0)
flag = false;
while (k--)
{
scanf("%d",&v);
g[i][v] = true;
}
}
if (flag)
{
cnt = 0;
for (i = 1; i <= p; i++)
{
/***************/
memset(vis,false,sizeof(vis));
cnt += SearchPath(i);
/*********************************/
}
if (cnt == p)
printf("YES\n");
else printf("NO\n");
}
else printf("NO\n");
}
return 0;
}
//poj_1469
/*==================================================*\
| 二分图匹配（Hopcroft－Carp 的算法）
| INIT: g[][]邻接矩阵;
| CALL: res = MaxMatch(); Nx, Ny要初始化！！！
| Mx，My为match
| 时间复杂度为O（V^0.5 E）
\*==================================================*/
/***********************Hopcroft－Carp 算法****************************************/
#include <cstdio>
#include <memory.h>
#include <queue>
using namespace std;
const int MAXN = 310;
const int INF = 1 << 28;
bool flag;
int p,n;
int Mx[MAXN], My[MAXN], Nx, Ny;
int dx[MAXN], dy[MAXN], dis;
bool vst[MAXN],g[110][310];
bool searchP(void)
{
queue <int> Q;
dis = INF;
memset(dx, -1, sizeof(dx));
memset(dy, -1, sizeof(dy));
for (int i = 1; i <= Nx; i++)
if (Mx[i] == -1){
Q.push(i); dx[i] = 0;
}
while (!Q.empty()) {
int u = Q.front(); Q.pop();
if (dx[u] > dis) break;
for (int v = 1; v <= Ny; v++)
if (g[u][v] && dy[v] == -1) {
dy[v] = dx[u]+1;
if (My[v] == -1) dis = dy[v];
else{
dx[My[v]] = dy[v]+1;
Q.push(My[v]);
}
}
}
return dis != INF;
}
bool DFS(int u){
for (int v = 1; v <= Ny; v++)
if (!vst[v] && g[u][v] && dy[v] == dx[u]+1) {
vst[v] = 1;
if (My[v] != -1 && dy[v] == dis) continue;
if (My[v] == -1 || DFS(My[v])) {
My[v] = u; Mx[u] = v;
return 1;
}
}
return 0;
}
int MaxMatch(void){
int res = 0;
memset(Mx, -1, sizeof(Mx));
memset(My, -1, sizeof(My));
while (searchP()) {
memset(vst, 0, sizeof(vst));
for (int i = 1; i <= Nx; i++)
if (Mx[i] == -1 && DFS(i)) res++;
}
return res;
}
/**********************************************************************/
int main()
{
int i,j,k,t,v,cnt;
scanf("%d",&t);
while (t--)
{
scanf("%d %d", &p, &n);
for (i = 1; i <= p; i++)
for (j = 1; j <= n; j++)
g[i][j] = false;
flag = true;
for (i = 1; i <= p; i++)
{
scanf("%d",&k);
if (k == 0)
flag = false;
while (k--)
{
scanf("%d",&v);
g[i][v] = true;
}
}
Nx = p; Ny = n;
if (flag)
{
cnt = MaxMatch();
if (cnt == p)
printf("YES\n");
else printf("NO\n");
}
else printf("NO\n");
}
return 0;
}
|