[트리DP] Party at Hali-Bula
Party at Hali-Bula
http://acm.hdu.edu.cn/showproblem.php?pid=2412
Problem Description
Dear Contestant,
I'm going to have a party at my villa at Hali-Bula to celebrate my retirement from BCM. I wish I could invite all my co-workers, but imagine how an employee can enjoy a party when he finds his boss among the guests! So, I decide not to invite both an employee and his/her boss. The organizational hierarchy at BCM is such that nobody has more than one boss, and there is one and only one employee with no boss at all (the Big Boss)! Can I ask you to please write a program to determine the maximum number of guests so that no employee is invited when his/her boss is invited too? I've attached the list of employees and the organizational hierarchy of BCM.
Best,
--Brian Bennett
P.S. I would be very grateful if your program can indicate whether the list of people is uniquely determined if I choose to invite the maximum number of guests with that condition.
Input
The input consists of multiple test cases. Each test case is started with a line containing an integer n (1 ≤ n ≤ 200), the number of BCM employees. The next line contains the name of the Big Boss only. Each of the following n-1 lines contains the name of an employee together with the name of his/her boss. All names are strings of at least one and at most 100 letters and are separated by blanks. The last line of each test case contains a single 0.
Output
For each test case, write a single line containing a number indicating the maximum number of guests that can be invited according to the required condition, and a word Yes or No, depending on whether the list of guests is unique in that case.
Sample Input
6
Jason
Jack Jason
Joe Jack
Jill Jason
John Jack
Jim Jill
2
Ming
Cho Ming
0
Sample Output
4 Yes
1 No
#include<cstdio>
#include<cstring>
#include<string>
#include<map>
#include<vector>
using namespace std;
#define N 210
map<string,int> st;
int n,num,dp[N][2];
//dp[i][0] i ,i
//dp[i][1] i ,i
vector<int> child[N];
bool flag[N][2];
int getNum(string &a)
{
if(st.count(a))
return st.find(a)->second;
else
st.insert(make_pair(a,num++));
return num-1;
}
void dfs(int x)
{
for(int i=0;i<child[x].size();++i)
{
int y=child[x][i];
dfs(y);
dp[x][1]+=dp[y][0];
dp[x][0]+=max(dp[y][0],dp[y][1]);
if((dp[y][0]>dp[y][1]&&!flag[y][0])||(dp[y][0]<dp[y][1]&&!flag[y][1])||dp[y][0]==dp[y][1])//
flag[x][0]=false;
if(!flag[y][0])
flag[x][1]=false;
}
dp[x][1]++;
}
int main()
{
char stra[200],strb[200];
string sa,sb;
int a,b,s;
for(;scanf("%d",&n)&&n;)
{
num=1;
for(int i=0;i<=n;++i)
child[i].clear();
memset(dp,0,sizeof(dp));
memset(flag,true,sizeof(flag));
st.clear();
scanf("%s",stra);
sa=string(stra);
s=getNum(sa);
for(int i=1;i<n;++i)
{
scanf("%s %s",stra,strb);
sa=string(stra);
sb=string(strb);
child[getNum(sb)].push_back(getNum(sa));
}
dfs(s);
printf("%d ",max(dp[s][0],dp[s][1]));
if(dp[s][0]>dp[s][1]&&flag[s][0])
puts("Yes");
else if(dp[s][1]>dp[s][0]&&flag[s][1])
puts("Yes");
else puts("No");
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[SwiftUI]List화한 CoreData를 가로 스와이프로 행 삭제하는 방법
상당히 조사했지만 일본어 자료가 없었기 때문에 비망록으로 남겨 둔다.
아래와 같이 CoreData를 참조한 리스트를 가로 스와이프로 삭제하고 싶었다.
UI 요소뿐만 아니라 원본 데이터 당 삭제합니다.
잘 다른 페이지...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
6
Jason
Jack Jason
Joe Jack
Jill Jason
John Jack
Jim Jill
2
Ming
Cho Ming
0
4 Yes
1 No
#include<cstdio>
#include<cstring>
#include<string>
#include<map>
#include<vector>
using namespace std;
#define N 210
map<string,int> st;
int n,num,dp[N][2];
//dp[i][0] i ,i
//dp[i][1] i ,i
vector<int> child[N];
bool flag[N][2];
int getNum(string &a)
{
if(st.count(a))
return st.find(a)->second;
else
st.insert(make_pair(a,num++));
return num-1;
}
void dfs(int x)
{
for(int i=0;i<child[x].size();++i)
{
int y=child[x][i];
dfs(y);
dp[x][1]+=dp[y][0];
dp[x][0]+=max(dp[y][0],dp[y][1]);
if((dp[y][0]>dp[y][1]&&!flag[y][0])||(dp[y][0]<dp[y][1]&&!flag[y][1])||dp[y][0]==dp[y][1])//
flag[x][0]=false;
if(!flag[y][0])
flag[x][1]=false;
}
dp[x][1]++;
}
int main()
{
char stra[200],strb[200];
string sa,sb;
int a,b,s;
for(;scanf("%d",&n)&&n;)
{
num=1;
for(int i=0;i<=n;++i)
child[i].clear();
memset(dp,0,sizeof(dp));
memset(flag,true,sizeof(flag));
st.clear();
scanf("%s",stra);
sa=string(stra);
s=getNum(sa);
for(int i=1;i<n;++i)
{
scanf("%s %s",stra,strb);
sa=string(stra);
sb=string(strb);
child[getNum(sb)].push_back(getNum(sa));
}
dfs(s);
printf("%d ",max(dp[s][0],dp[s][1]));
if(dp[s][0]>dp[s][1]&&flag[s][0])
puts("Yes");
else if(dp[s][1]>dp[s][0]&&flag[s][1])
puts("Yes");
else puts("No");
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[SwiftUI]List화한 CoreData를 가로 스와이프로 행 삭제하는 방법상당히 조사했지만 일본어 자료가 없었기 때문에 비망록으로 남겨 둔다. 아래와 같이 CoreData를 참조한 리스트를 가로 스와이프로 삭제하고 싶었다. UI 요소뿐만 아니라 원본 데이터 당 삭제합니다. 잘 다른 페이지...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.