HDU 4160 Dolls(DAG最小路径覆盖)
http://acm.hdu.edu.cn/showproblem.php?pid=4160
题意:
有N个木偶,木偶有3项指标,w,i,h. 如果第i个木偶的3项指标对应小于第j个木偶的3项指标,那么i木偶可以放到j木偶中. 且一个木偶里面只能直接的放一个别的木偶.问你这N个木偶最优嵌套的方案下,最多有几个木偶不能被任何木偶嵌套?
分析:
如果i木偶能放在j木偶中,那么连一条i->j的有向边. 那么最终我们能得到一个DAG图. 现在我们的问题是要在该DAG图中找最少的简单路径,这些路径没有交集且正好完全覆盖了DAG的各个顶点.(想想是不是这个问题)
上面这个问题就是DAG的最小路径覆盖问题,我们可以通过建立二分图来求解. DAG的最小路径覆盖 = N-二分图最大匹配数.
AC代码:
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
const int maxn=500+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=1;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=1;i<=n;++i)
{
memset(vis,0,sizeof(vis));
if(match(i)) ++ans;
}
return ans;
}
}MM;
struct Node
{
int w,l,h;
bool link(Node& rhs)
{
return (w<rhs.w && l<rhs.l && h<rhs.h);
}
}nodes[maxn];
int main()
{
int n;
while(scanf("%d",&n)==1 && n)
{
MM.init(n);
for(int i=1;i<=n;i++)
scanf("%d%d%d",&nodes[i].w, &nodes[i].l, &nodes[i].h);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)if(i!=j)
if(nodes[i].link(nodes[j]))
MM.g[i].push_back(j);
printf("%d\n",n-MM.solve());
}
return 0;
}
分享到:
相关推荐
hdu2215 最简单的最小圆覆盖
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
杭电ACMhdu1163
HDU1059的代码
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
hdu2101AC代码
搜索 dfs 解题代码 hdu1241
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
杭电ACM课件2014版之 (HDUACM201403版_06)并查集(最小生成树)
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
(HDUACM2010版_06)并查集(最小生成树(HDUACM2010版_06)并查集(最小生成树(HDUACM2010版_06)并查集(最小生成树(HDUACM2010版_06)并查集(最小生成树
ACM HDU题目分类,我自己总结的大概只有十来个吧
hdu 1166线段树代码
HDU最全ac代码
hdu动态规划算法集锦
自己做的HDU ACM已经AC的题目
hdu题目分类