求大佬看看马蜂
  • 板块灌水区
  • 楼主__wjy__
  • 当前回复4
  • 已保存回复4
  • 发布时间2024/8/1 18:18
  • 上次更新2024/8/1 19:39:24
查看原帖
求大佬看看马蜂
735264
__wjy__楼主2024/8/1 18:18
#include <iostream>
#include <cstring>
using namespace std;
const int N=1e4+50;
int c,h[N],dp[N][4],n,p,u,v,ans,out[N],in[N],k,w[N],m;
struct E{int nx,to;}e[N];
void ad(int u,int v){e[++c].to=v;e[c].nx=h[u];h[u]=c;}
inline int read(){int x=0,f=1;char ch=getchar();while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}return x*f;}
void dfs(int u){
    dp[u][0]=w[u];
    int flag=0;
    int minn=0x7fffffff;
    for(int i=h[u];i!=0;i=e[i].nx){
        int v=e[i].to;dfs(v);
        dp[u][0]+=min(dp[v][0],min(dp[v][1],dp[v][2]));
        dp[u][2]+=min(dp[v][1],dp[v][0]);
        dp[u][1]+=min(dp[v][1],dp[v][0]);
        if(dp[v][0]<dp[v][1]) flag=1;
        minn = min(minn,dp[v][0]-dp[v][1]);
    }
    if(flag==0) dp[u][1]+=minn;
}
int main(){
    n=read();
    for(int i=1;i<=n;i++){
        u=read();k=read();m=read();
        w[u]=k;
        for(int j=1;j<=m;j++){
            k=read();
            ad(u,k);in[k]++;
        }
    }
    for(int i=1;i<=n;i++){
        if(in[i]==0){
            ans=i;
            break;
        }
    }
    dfs(ans);
    printf("%d\n",min(dp[ans][0],dp[ans][1]));
    return 0;
}
2024/8/1 18:18
加载中...