HDU 1054 Strategic Game(二分图最小覆盖集)
http://acm.hdu.edu.cn/showproblem.php?pid=1054
题意:
给你一颗具有N个节点的树的所有边信息.现在问你最少需要多少个点放到树的节点上,使得树的任意一条边都至少有一个端点被覆盖.(其实就是最小覆盖集)
分析:
POJ题号1463.
本题明显的最小覆盖集. 且由于树天然就是二分的(可以自己验证一下),所以我们只需要求该树的最小覆盖集点数即可.
我们可以用染色法把树的所有节点二分,构建二分图,然后在求该二分图的最大匹配数.
当然我们也可以直接构建翻倍的二分图,求出最大匹配数ans.最终结果等于ans/2. 本程序用的就是翻倍二分图解的. 关于翻倍二分图可见:
POJ1466:http://blog.csdn.net/u013480600/article/details/38638219.
AC代码:
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
const int maxn=1500+5;
struct Max_Match
{
int n;
vector<int> g[maxn];
bool vis[maxn];
int left[maxn];
void init(int n)
{
this->n=n;
for(int i=0;i<n;i++) g[i].clear();
memset(left,-1,sizeof(left));
}
bool match(int u)
{
for(int i=0;i<g[u].size();i++)
{
int v=g[u][i];
if(!vis[v])
{
vis[v]=true;
if(left[v]==-1 || match(left[v]))
{
left[v]=u;
return true;
}
}
}
return false;
}
int solve()
{
int ans=0;
for(int i=0;i<n;i++)
{
memset(vis,0,sizeof(vis));
if(match(i)) ++ans;
}
return ans;
}
}MM;
int main()
{
int n;
while(scanf("%d",&n)==1)
{
MM.init(n);
for(int i=0;i<n;i++)
{
int u,num,v;
scanf("%d:(%d)",&u,&num);
while(num--)
{
scanf("%d",&v);
MM.g[u].push_back(v);
MM.g[v].push_back(u);
}
}
printf("%d\n",MM.solve()/2);
}
return 0;
}
分享到:
相关推荐
B HDU 5093 Battle ships题意给出一个n行m列的图,*代表海域,o代表冰水,#代表冰山,要想在海域中放置船,保证船与船之间不能相互看到,之间
杭电ACM课件2014版之 (HDUACM201403版_06)并查集(最小生成树)
hdu2215 最简单的最小圆覆盖
(HDUACM2010版_06)并查集(最小生成树(HDUACM2010版_06)并查集(最小生成树(HDUACM2010版_06)并查集(最小生成树(HDUACM2010版_06)并查集(最小生成树
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
本人准备2020年保研机试时刷的题目(虽然最后机试取消了,...来自某中流985,在HDU和vjudge平台上大概刷了400道。本文件地图(excel表格)包含了绝大部分我刷过的题目,笔记中具有思路、代码、总结和心得。 大佬勿入!
杭电ACMhdu1163
HDU1059的代码
二分图匹配实例代码及整理 1、匈牙利算法 HDU 1150 #include #include #include using namespace std; int m,n,k; int vis[105]; int mpt[105][105]; int use[105]; int hungary(int x) { for(int i=1;i<m;i++)...
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
hdu2101AC代码
搜索 dfs 解题代码 hdu1241
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
hdu1290 解题报告 献给杭电五十周年校庆的礼物 (切西瓜问题,即平面分割空间)
ACM HDU题目分类,我自己总结的大概只有十来个吧
hdu 1166线段树代码