社区讨论
为什么挂了~~只有50;
P2458[SDOI2006] 保安站岗参与者 1已保存回复 0
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @mi6xxshw
- 此快照首次捕获于
- 2025/11/20 12:38 4 个月前
- 此快照最后确认于
- 2025/11/20 12:38 4 个月前
CPP
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define forE(i,x) for(int i=head[x];i;i=bian[i].nxt)
#define N 10050
using namespace std;
int n,head[N],a[N],now,m,root,minn=99999999;
int f[N][3];
long long ans;
bool vis[N],ju;
struct wfq{
int nxt,to;
}bian[2*N];
void Add(int x,int y)
{
bian[++now].nxt=head[x];
bian[now].to=y;
head[x]=now;
return ;
}
void dfs(int u,int fa)
{
bool ju=0;minn=99999999;
f[u][1]=a[u];
forE(i,u)
{
int v=bian[i].to;
if(v==fa)continue;
{
dfs(v,u);
f[u][1]+=min(min(f[v][0],f[v][1]),f[v][2]);
if(f[v][1]<=f[v][0])f[u][0]+=f[v][1],ju=1;//cout<<ans<<endl;
else f[u][0]+=f[v][0],minn=min(minn,f[v][1]-f[v][0]);
f[u][2]+=min(f[v][1],f[v][0]);
//cout<<f[u][0]<<" "<<f[u][1]<<" "<<f[u][2]<<endl;
}
}if(!ju)f[u][0]+=minn;//cout<<"aaa"<<minn<<endl;;
}
int main()
{
srand((unsigned long long) new char);
cin>>n;
//rep(i,1,n)f[i][0]=9999999,f[i][1]=9999999;
rep(i,1,n)
{
int c;scanf("%d",&c);scanf("%d%d",&a[c],&m);
//if(m==0){f[c][1]=a[c];}
rep(i,1,m)
{
int y;
scanf("%d",&y);Add(c,y);Add(y,c);
vis[y]=1;
}
}
dfs(1,-1);
/* rep(i,1,n)
{
cout<<f[i][0]<<" "<<f[i][1]<<" "<<f[i][2]<<endl;
}*/
cout<<min(f[1][0],f[1][1])<<endl;
return 0;
}
有几个点比标准答案在从左数第三位少1;
回复
共 0 条回复,欢迎继续交流。
正在加载回复...