这题的时间其实没必要10000ms,o(n)的复杂度就行了,算是dp吧,每次从叶节点往上更新就是,附上代码
#include<stdio.h>
#include<string.h>
int lcy[1510],fa[1510],son[1510],ans,len;//lcy是叶节点数组,实时更新,fa是父亲节点,son表示儿子节点的个数,ans就是要占领的点的个数,len是lcy数组的长度
bool flag[1510];
void calcu(int s)
{
if(s==-1||fa[s]==-1)return;
if(flag[s])
{
s=fa[s];
son[s]--;
if(!son[s])
lcy[len++]=s;//更新叶子节点
}
else
{
s=fa[s];
son[s]--;
if(!flag[s])//儿子和父亲都没被标记,标记父亲节点
{
ans++;
flag[s]=1;
}
if(!son[s])
lcy[len++]=s;//更新叶子节点
}
}
int main()
{
int i,j,n,num,a;
while(scanf("%d",&n)!=-1)
{
memset(flag,0,sizeof(flag));
memset(fa,-1,sizeof(fa));
int node;
len=0;
for(i=0;i<n;i++)
{
scanf("%d:(%d)",&node,&num);
son[node]=num;//保存叶子节点
if(num==0)
{
lcy[len++]=node;
continue;
}
while(num--)
{
scanf("%d",&a);
fa[a]=node;
}
}
//for(i=0;i<len;i++)
//printf("lcy[%d]=%d\n",i,lcy[i]);
ans=0;
for(i=0;;i++)
{
if(i==len)break;
calcu(lcy[i]);
}
printf("%d\n",ans);
}
return 0;
}
分享到:
相关推荐
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
2019 Multi-University Training Contest 4(2019hdu多校第六场数据与标程)
ACM HDU 2000->2099 解题报告 ACM HDU 2000->2099 解题报告 ACM HDU 2000->2099 解题报告
此程序为hdu的acm2010题,就是解决水仙花数问题
杭电hdu acm资料所用杭电的acm题
包含实验内容:对应实验要求上的1/2/3/5实验,分别为setName/setNice,petree输出进程,模拟shell,进程通信,文件系统。包含全部实验源代码和详尽的word实验报告。同时包含在线PTA编程题目:进程模拟,模拟进程调度...
HDU一部分题目原码,大部分是可运行的,可能有几题不完整
杭电 hdu acm 第1084题的解法,ac过了,是一位学长教我的.内有一些中文说明.
(HDUACM2010版_08)母函数(HDUACM2010版_08)母函数(HDUACM2010版_08)母函数(HDUACM2010版_08)母函数(HDUACM2010版_08)母函数(HDUACM2010版_08)母函数
hdu 1005.比较简单的一道题,有兴趣的可以看看。
ACM HDU题目分类,我自己总结的大概只有十来个吧
hdu-acm源代码(上百题)hdu-acm源代码、hdu-acm源代码hdu-acm源代码
压缩包包含十份报告,已经通过验收,实验内容:交换机、生成树、静态路由、NAT等完全根据教材实验要求
100道 acm C语言 hdu 解题报告
ACM hdu 代码大全3000例,hdu已经AC的3000例代码,部分代码有详细解析
HDU1059的代码
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
HDU2013暑期多校联合训练第一场0723-解题报告和标程
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
一个十分简单的程序,能够ac杭电hdu的第2050题,无注释,简单明了