d.一颗树,选最少的点覆盖所有边

s.

1.可以转成二分图的最小点覆盖来做。不过转换后要把匹配数除以2,这个待细看。

2.也可以用树形dp

c.匈牙利算法(邻接表,用vector实现):

/*

用STL中的vector建立邻接表实现匈牙利算法
效率比较高
处理点比较多的效率很高。1500的点都没有问题
*/
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<vector>
using namespace std; const int MAXN=;//这个值要超过两边个数的较大者,因为有linker
int linker[MAXN];
bool used[MAXN];
vector<int>G[MAXN];
int uN;
bool dfs(int u)
{
int sz=G[u].size();
for(int i=; i<sz; i++)
{
if(!used[G[u][i]])
{
used[G[u][i]]=true;
if(linker[G[u][i]]==-||dfs(linker[G[u][i]]))
{
linker[G[u][i]]=u;
return true;
}
}
}
return false;
} int hungary()
{
int u;
int res=;
memset(linker,-,sizeof(linker));
for(u=; u<uN; u++)
{
memset(used,false,sizeof(used));
if(dfs(u)) res++;
}
return res;
} int main(){ int n,k;
int u,v;
int i,j; while(~scanf("%d",&n)){ for(i=;i<MAXN;++i){
G[i].clear();
} for(i=;i<n;++i){
scanf("%d:(%d)",&u,&k);
for(j=;j<k;++j){
scanf("%d",&v);
G[u].push_back(v);
G[v].push_back(u);
}
} uN=n; printf("%d\n",hungary()/);
} return ;
}

c2.树形dp

/*
HDU 1054 G++ 312ms 560K
*/ #include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN=;
struct Node
{
int father,brother,child;
int yes;//该结点放置
int no;//该结点不放置
}t[MAXN];
void DFS(int x)
{
int child=t[x].child;
while(child)
{
DFS(child);
t[x].yes+=min(t[child].yes,t[child].no);
//父亲结点放置了,儿子结点可以放置也可以不放置
t[x].no+=t[child].yes;
//父亲结点没有放置,儿子结点必须放置
child=t[child].brother;
}
}
bool used[MAXN];
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
int n;
int root,k,v;
while(scanf("%d",&n)!=EOF)
{
memset(used,false,sizeof(used));
int Root;//根结点
for(int i=;i<n;i++)
{
scanf("%d:(%d)",&root,&k);
root++;//编号从1开始
if(i==)Root=root;
if(!used[root])
{
used[root]=true;
t[root].brother=t[root].father=t[root].child=;
t[root].yes=;
t[root].no=;
}
while(k--)
{
scanf("%d",&v);
v++;
if(!used[v])
{
used[v]=true;
t[v].brother=t[v].father=t[v].child=;
t[v].yes=;
t[v].no=;
}
t[v].brother=t[root].child;
t[v].father=root;
t[root].child=v;
} }
DFS(Root);
printf("%d\n",min(t[Root].yes,t[Root].no)); }
return ;
}

最新文章

  1. bzoj3037--贪心
  2. 浅谈MITM攻击之信息窃取(解密315晚会报道的免费WIFI窃取个人信息)
  3. jQuery load()方法用法集锦!
  4. 制作一个属于自己的BHO吧!(C#) (转)
  5. delete archivelog all 无法彻底删除归档日志?
  6. jQuery和CSS 3定制HTML 5视频播放器
  7. linux命令——rm
  8. HTTP 错误 500.21 - Internal Server Error 处理程序“PageHandlerFactory-Integr
  9. redis的key过期时间
  10. 如何将Java Web项目部署到服务器上
  11. Monkey学习笔记&lt;四&gt;:Monkey服务器命令
  12. String类使用方法
  13. 【ECHART】实例
  14. 自学Aruba之路
  15. php之快速排序
  16. mysql建数据库的字符集与排序规则
  17. webpack构建Vue工程
  18. C++隐藏任务栏图标
  19. 记一次JAVAWEB项目部署
  20. 【UOJ#311】【UNR #2】积劳成疾(动态规划)

热门文章

  1. 【Git】Git 本地的撤销修改和删除操作
  2. POJ 2185 Milking Grid [二维KMP next数组]
  3. 在 IntelliJ IDEA 中为自己设计的类库生成 JavaDoc
  4. Adobe Premiere Pro导入插件开发遇到的一个问题
  5. hg下拉和上传代码
  6. Spring的IoC容器概述
  7. iOS Block学习
  8. JZ2440:时钟设置
  9. 手游产品经理初探(八)CasinoStar玩家离开原因分析
  10. Mqtt协议IOS端移植3