社区讨论

为什么挂了~~只有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 条回复,欢迎继续交流。

正在加载回复...