比赛 |
2025暑期集训第4场 |
评测结果 |
W |
题目名称 |
战略游戏 |
最终得分 |
0 |
用户昵称 |
rb_tree |
运行时间 |
0.070 s |
代码语言 |
C++ |
内存使用 |
3.89 MiB |
提交时间 |
2025-07-05 09:56:36 |
显示代码纯文本
#include<bits/stdc++.h>
#define int long long
using namespace std;
int read()
{
int x=0,w=1;
char ch=0;
while(ch<'0'||ch>'9')
{
if(ch=='-') w=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*w;
}
void write(int x)
{
if(x<0)
{
x=-x;
putchar('-');
}
if(x>=10) write(x/10);
putchar((x%10)^48);
}
const int N=1500,M=3005;
int n,dp[N][3];
int h[N],nxt[M],to[M],_cnt;
void add_edge(int a,int b)
{
to[++_cnt]=b;
nxt[_cnt]=h[a];
h[a]=_cnt;
}
void init()
{
memset(dp,0x3f,sizeof(dp));
memset(h,0,sizeof(h));
memset(nxt,0,sizeof(nxt));
memset(to,0,sizeof(to));
_cnt=0;
}
void dfs(int x,int f)
{
dp[x][0]=1;
dp[x][2]=0;
for(int i=h[x];i;i=nxt[i])
{
int v=to[i];
if(v==f) continue;
dfs(v,x);
dp[x][0]+=min(dp[v][0],dp[v][2]);
dp[x][2]+=dp[v][1];
}
for(int i=h[x];i;i=nxt[i])
{
int v=to[i];
if(v==f) continue;
dp[x][1]=min(dp[x][1],dp[x][2]-dp[v][1]+dp[v][0]);
}
}
signed main()
{
freopen("strategic.in","r",stdin);
freopen("strategic.out","w",stdout);
int n;
while(scanf("%d",&n)==1)
{
init();
for(int i=1;i<=n;i++)
{
int u=read(),m=read();
for(int j=1;j<=m;j++)
{
int v=read();
add_edge(u,v);
add_edge(v,u);
}
}
dfs(0,0);
write(min(dp[0][0],dp[0][1]));
putchar('\n');
}
fclose(stdin);
fclose(stdout);
return 0;
}