本文主要是介绍Sins of a Solar Empire P3，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
★ 实验任务正如你所知道的 s_sin 是一个贪玩的不得了的小 P 孩 QAQ，你也知道他最近很喜欢玩一
个叫做太阳帝国的原罪的策略游戏去年他已经和疯狂的 AI 交战了整整一年。而现在，战斗
的序幕又要拉开了。 如果你没有忘记去年的 gungnir 和 Freya 的话， 今年他又带来了新武器，
命名为 Cassandra。
已知疯狂的 AI 占领了 n 个行星，这 n 个行星中有 n-1 个通道保证他们之间连通。（我们
把 n 个行星和它们之间的 n-1 个通道称为 1 个 n 元行星群）而敌方的物资就是通过这些通道
在行星之间流动。现在 Cassandra 的能力是能够直接摧毁所有通往某个行星 xi 的通道。而
作为机智的 s_sin 他所希望的目的是，在摧毁通往某个行星 xi 的所有通道之后，使得其余
的若干个行星群中元数最大的最小。请按照字典序输出所有 xi
★ 数据输入
输入第一行为一个正整数 N (2 < N < =30000)， 表示敌方占有的 n 个行星
接下来 n-1 行，每行三个整数 a b，表示编号 a b 行星之间有一条相位转移通道。
其中 50% (1<N<=10000)
★ 数据输出 输出所有如题目描述中的 xi
输入示例 输出示例
6 2 3
1 2
2 3
2 5
3 4
3 6
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 30010 struct Node
{ int d,next;
}el[N*2];//结点 int n,t,s;
int f[N],vis[N],l[N];
int tem[N]; int main()
{ void add(int x,int y); void dfs(int u); memset(l,-1,sizeof(l)); memset(vis,0,sizeof(vis)); scanf("%d",&n); int i,a,b; t=0; for(i=1;i<n;++i) { scanf("%d%d",&a,&b); add(a,b); } s=n; dfs(1); sort(f+1,f+1+f[0]); printf("%d",f[1]); for(i=2;i<=f[0];++i) printf(" %d",f[i]); return 0;
} void add(int x,int y)
{ el[t].d=y; el[t].next=l[x]; l[x]=t++; el[t].d=x; el[t].next=l[y]; l[y]=t++;
} void dfs(int u)
{ int q=-1; vis[u]=1; tem[u]=0; for(int i=l[u];i!=-1;i=el[i].next) { int d=el[i].d; if(vis[d]) continue; dfs(d); tem[u]+=1+tem[d]; if(q==-1 || tem[d]+1>q) q=tem[d]+1; } if(n-tem[u]-1>q) q=n-tem[u]-1; if(q<s) { s=q; f[0]=1,f[1]=u; } else if(q==s) { f[++f[0]]=u; }
}
这篇关于Sins of a Solar Empire P3的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
