90分,WA on #3,求条,马蜂良好
查看原帖
90分,WA on #3,求条,马蜂良好
945845
Chernobog_Belobog楼主2024/7/19 20:22
#include <bits/stdc++.h>
using namespace std;

int n , p , cnt , head[1507] , dp[1507][7];
struct node {
    int u , v , nxt;
}e[3007];

void dfs(int x , int f) {
    if (head[x] == -1) {
        dp[x][2] = 0x3f3f3f3f;
        return;
    }
    int t = 0 , k = 0x3f3f3f3f;
    for (int i = head[x] ; i != -1 ; i = e[i].nxt) {
        int tmp = e[i].v;
        if (tmp == f) continue;
        dfs(tmp , x);
        dp[x][1] += min(min(dp[tmp][1] , dp[tmp][2]) , dp[tmp][3]);
        dp[x][2] += min(dp[tmp][1] , dp[tmp][2]);
        dp[x][3] += min(dp[tmp][1] , dp[tmp][2]);
        if (dp[tmp][1] < dp[tmp][2]) t++;
        else k = min(k , (dp[tmp][1] - dp[tmp][2]));
    }
    if (t == 0) dp[x][2] += k;
}

int main() {
    cin >> n; memset(head , -1 , sizeof(head));
    for (int i = 1 ; i <= n ; i++) {
        int k , s; cin >> p >> s >> k;
        dp[p][1] = s;
        for (int j = 1 ; j <= k ; j++) {
            cin >> e[++cnt].v; e[cnt].u = p;
            e[cnt].nxt = head[e[cnt].u]; head[e[cnt].u] = cnt;
            e[cnt + 1].v = e[cnt].u; e[cnt + 1].u = e[cnt].v;
            e[cnt + 1].nxt = head[e[cnt + 1].u]; head[e[cnt + 1].u] = ++cnt;
        }
    }
    dfs(1 , -1);
    cout << min(dp[1][1] , dp[1][2]);
    return 0;
}

讨论区的帖子已经看过了,反边建了,i 和 id 应该也没混

求条qwq

2024/7/19 20:22
加载中...