UVa 1220 Party at Hali-Bula 晚会
2024-08-30 13:43:53
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<string>
#include<map>
using namespace std;
map<string,int> nameCache;
int nowID,n;
string boss;
struct Edge
{
int to,next;
}edge[];
int num_edge,first[];
int dp1[][];
bool dp2[][];
bool vis[];
//[][1]表示选此点,[][0]表示不选此点,dp1记录最多选的人数,dp2记录是否唯一
void dp(int x)
{
int k=first[x];
dp2[x][]=true;
dp1[x][]=;
dp2[x][]=true;
dp1[x][]=;
vis[x]=true;
while(k!=)
{
if(!vis[edge[k].to]) dp(edge[k].to);
dp1[x][]+=dp1[edge[k].to][];
dp2[x][]&=dp2[edge[k].to][];
if(dp1[edge[k].to][]>dp1[edge[k].to][])
{
dp1[x][]+=dp1[edge[k].to][];
dp2[x][]&=dp2[edge[k].to][];
}
else if(dp1[edge[k].to][]<dp1[edge[k].to][])
{
dp1[x][]+=dp1[edge[k].to][];
dp2[x][]&=dp2[edge[k].to][];
}
else
{
dp1[x][]+=dp1[edge[k].to][];
dp2[x][]=false;
}
k=edge[k].next;
}
}
int main()
{
int i,t1,t2;
string str,str2;
cin>>n;
while(n!=)
{
cin>>boss;
nameCache.clear();
num_edge=;
nowID=;
nameCache[boss]=;
memset(vis,,sizeof(vis));
memset(first,,sizeof(first));
for(i=;i<n;i++)
{
cin>>str>>str2;
if(nameCache.count(str)==)
{
t1=nowID++;
nameCache[str]=t1;
}
else
t1=nameCache[str];
if(nameCache.count(str2)==)
{
t2=nowID++;
nameCache[str2]=t2;
}
else
t2=nameCache[str2];
edge[++num_edge].to=t1;
edge[num_edge].next=first[t2];
first[t2]=num_edge;
}
dp();
if(dp1[][]>dp1[][])
{
printf("%d ",dp1[][]);
if(dp2[][]==true)
printf("Yes\n");
else
printf("No\n");
}
else if(dp1[][]<dp1[][])
{
printf("%d ",dp1[][]);
if(dp2[][]==true)
printf("Yes\n");
else
printf("No\n");
}
else
printf("%d No\n",dp1[][]);
cin>>n;
}
return ;
}
最新文章
- js中参数不对应问题
- ActiveMQ集群下的消息回流功能
- 谈谈asp.net MVC中的AppendTrailingSlash以及LowercaseUrls ,你还记得吗?
- DevOps Workshop 研发运维一体化第一场(微软亚太研发集团总部)
- golang——concurrency笔记
- Oracle SQL的硬解析、软解析、软软解析
- 解决Eclipse导出javadoc乱码问题
- Tomcat安全
- JQuery+EasyUI弹窗代码
- UIPanGestureRecognizer的使用
- iOS设计模式:观察者
- JavaScript中的位置屬性
- OpenXml读取word内容(三)
- 项目实战13—企业级虚拟化Virtualization-KVM技术
- HTML中的select下拉框内容显示不全的解决办法
- node.js学习资料(2015-12)
- PHP-MySQL基本操作
- EasyUI-datebox设置开始日期小于结束日期,并且结束日期小于当前日期
- 20165337学习基础和C语言基础调查
- first one