Uvalive 4267 Finding The Heaviest Path(Regionals 2008 Asia Taipei + DFS 결점 최대 권한 경로)
[제목 대의]: 나무 한 그루를 드릴게요. 나무에서 뿌리 노드에서 잎 결점까지 결점 권한이 가장 큰 경로를 찾아서 출력합니다.
【사고방식】: dfs 검색, 검색 권한 값, 출력 경로
코드:
/*
* Problem: UVALive 4267
* Running time: 23MS
* Complier: G++
* Author: herongwei
* Create Time: 20:16 2015/10/14
*/
#include <stdio.h>
#include <string.h>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn=1e4+10;
const int inf=0x3f3f3f3f;
inline int max(int a,int b){return a>b?a:b;}
inline int min(int a,int b){return a<b?a:b;}
int w1[maxn],w2[maxn],a[maxn];
vector<int >G[maxn];
int n,m,len,ans;
int dfs(int root) //
{
int cnt=0;
for(int i=0; i<G[root].size(); ++i)
{
cnt+=dfs(G[root][i]);
// cout<<"root= "<<root<<" "<<"i="<<i<<"G[root][i]= "<<" "<<G[root][i]<<endl;
}
w1[root]+=cnt;
//cout<<"cnt= "<<cnt<<endl;
return w1[root];
}
void dfss(int root)//
{
a[len++]=root;
ans+=w2[root];
int ck=-1;
if(G[root].size()) ck=G[root][0];
for(int i=0; i<G[root].size(); ++i)
{
if(w1[G[root][i]]>w1[ck]) ck=G[root][i];
else if(w1[G[root][i]]==w1[ck]&&ck<G[root][i])
ck=G[root][i];
}
if(ck<0) return ;
else dfss(ck);
}
int main()
{
//freopen("1.txt","r",stdin);
int t;scanf("%d",&t);
while(t--)
{
len=0,ans=0;
int n,rt;scanf("%d%d",&n,&rt);
for(int i=0; i<n; ++i) G[i].clear();
for(int i=0; i<n; ++i)
{
int x,y;scanf("%d%d",&w1[i],&x);
while(x--)
{
scanf("%d",&y);
G[i].push_back(y);
}
}
for(int i=0; i<n; ++i) w2[i]=w1[i];
dfs(rt);
// cout<<w1[rt]<<endl;
dfss(rt);
printf("%d
",ans);
for(int i=0; i<len-1; ++i)
{
printf("%d",a[i]);
if(i&&i%10==9) puts("");
else printf(" ");
}
printf("%d
",a[len-1]);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
UVALive 4260 Fortune Card Game (Regionals 2008 Asia Taipei +DP)[제목 링크]: 클릭 here~~ [제목 대의]: There are five kinds of symbols, which are listed below the card. For convenience, let each ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.