希望更丰富的展现?使用Markdown
by nth_element @ 2019-01-19 11:53:17
```
#include<bits/stdc++.h>
using namespace std;
const int N=1500+5;
const int inf=0x3f3f;
int n,k[N],f[N][3];
int cnt=0,head[N<<1];
int read()
{
int x=0,w=0;char ch=0;
while(!isdigit(ch)) w|=ch=='-',ch=getchar();
while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return w?-x:x;
}
struct edge
{
int v,nxt;
}e[N<<1];
void add(int u,int v)
{
e[++cnt].v=v;
e[cnt].nxt=head[u];
head[u]=cnt;
}
void dp(int u,int fa)
{
f[u][0]=k[u];
bool yes=0;int minc=inf;
for(int i=head[u];i!=0;i=e[i].nxt)
{
int v=e[i].v;
if(v==fa) continue;
dp(v,u);
int t=min(f[v][0],f[v][1]);
f[u][0]+=min(f[v][2],t);//自己覆盖自己
f[u][2]+=t;//被父亲覆盖
if(f[v][0]<f[v][1]) yes=1;
else minc=min(minc,f[v][0]-f[v][1]);
f[u][1]+=t;//被儿子覆盖
}
if(yes==0) f[u][1]+=minc;
}
int main()
{
n=read();
for(int i=1;i<=n;i++)
{
int ii,m;
ii=read(),k[i]=read(),m=read();
while(m--)
{
int r=read();
add(ii,r);add(r,ii);
}
}
dp(1,0);
printf("%d",min(f[1][0],f[1][1]));
return 0;
}
```
by 净霖 @ 2019-01-19 11:54:19
@[nth_element](/space/show?uid=77131) QAQ发现下面啦
by 净霖 @ 2019-01-19 11:55:03
QAQ救救蒟蒻!
by 净霖 @ 2019-01-19 11:57:57