Posted on 2010-08-21 13:34
acronix 阅读(192)
评论(0) 编辑 收藏 引用 所属分类:
hzshuai解题报告
题意：就不多说了。分析：（转的有图有真相吗）这个题目如果知道使用二分图的话就很简单了，关键就是如何构图。
依照题目意思能够构造出图(1)，转变为图(2)之后发现，之前的job一定在图2中的某一条边上，同一条边上可以包含多个job，所以要完成所有的job，只需要包含所有的边即可，这就是最小点覆盖问题了。又知道二分图的最小点覆盖数=最大匹配数，因此可以用匈牙利算法求。（详细二分图关系见：）
#include <cstdio>
#include <memory.h>
bool g[110][110]; //标记二分图的链接关系
int match[110];//标记v中顶点匹配u的情况，无匹配则为-1
int vis[110];
int n,m,k;
/**********************/
int SearchPath(int u)
{
for (int v = 1; v <= m; 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,x,y,ans;
while (scanf("%d",&n) && n != 0)
{
scanf("%d %d", &m, &k);
for (i = 1; i <= n; i++)
for (j = 1; j <= m; j ++)
g[i][j] = false;
for (i = 1; i <= k; i ++)
{
scanf("%d %d %d", &j, &x, &y);
g[x][y] = true;
}
/**********/
memset(match,-1,sizeof(match));
ans = 0;
for (i = 1; i <= n; i++)
{
memset(vis,false,sizeof(vis));
ans += SearchPath(i);
}
/**************************/
printf("%d\n",ans);
}
return 0;
}