3883026_ac_0ms_208k.c

来自「北大大牛代码 1240道题的原代码 超级权威」· C语言 代码 · 共 53 行

#define size 110  
#include<stdio.h>   
struct {   
    int nomal;   
    int abnomal;   
    int next;   
    int visited;   
} data[size];   
int n;   
int max;   
int cur;   
  
void Search(int m)   
{   
    if(m == n + 1) {   
        if(cur < max) {   
            cur = max;   
        }   
        return ;   
    }   
    if(data[m].visited == 0) {   
        max += data[m].abnomal;   
        data[m].visited ++;   
        Search(data[m].next);   
        data[m].visited --;   
        max -= data[m].abnomal;   
    }    
    if((data[m].visited == 0 && data[m].next >= m) || ( data[m].visited != 0 )) {   
        max += data[m].nomal;   
        data[m].visited ++;   
        Search(m + 1);   
        data[m].visited --;   
        max -= data[m].nomal;   
    }   
}   
  
int main()   
{   
    int i, t, j;   
    scanf("%d", &t);   
    for(i = 0; i < t; i ++) {   
        scanf("%d", &n);   
        for(j = 1; j <= n; j ++) {   
            scanf("%d%d%d", &data[j].nomal, &data[j].abnomal, &data[j].next);   
            data[j].visited = 0;   
        }   
        max = 0;   
        cur = 0;   
        Search(1);   
        printf("%d\n", cur);   
    }   
    return 0;   
}