跳至正文

NOIP 2003 神经网络 解体报告

  其实这个题目很简单, 你们仔细想想,最像什么? 很多讨论图论第一个讨论得就是这个问题——拓扑排序, 不是吗? 几乎不用我提示了吧? 这里还有一个要注意的地方就是, 一个神经输入节点的u[i] > 0时也不回影响c[i]. 比如c[i] = 2, u[i]=100, 那么这个输入节点的c[i] 依然是2而不是-98。
  要说得救是这些, 代码如下:

#include <stdio.h>
#include <assert.h>
#define MAX 200
int c[200], u[200];

int queue[MAX];
int head, rear;

void enqueue(int k)
{
        queue[rear++] = k;
}

int exqueue(void)
{
        return queue[head++];
}

int map[200][200];
int link[200][200];
int in[200], out[200];

void add(int a, int b, int d)
{
        link[a][out[a]] = b;
        map[a][out[a]] = d;
        out[a]++, in[b]++;
}

int main(void)
{
        int a, b, d;
        int n, p;
        int i, j;
        scanf("%d%d", &n, &p);
        for(i = 0; i < n; i++){
                scanf("%d%d", &c[i], &u[i]);
                /
                Mistack 1:
                    把下面的c[i] > 0 写成了c[i] == 0
                
/
                if(c[i] > 0){
                        enqueue(i);
                }
                /
                Mistack 3:
                    作为输入神经, 无论u为多少, c都应该是固定的!
                
/
                if(c[i] == 0){
                        c[i] -= u[i];
                }
        }
        for(i = 0; i < p; i++){
                scanf("%d%d%d", &a, &b, &d);
                a–, b–;
                add(a, b, d);
        }

        while(head != rear){
                a = exqueue();
                if(c[a] > 0){
                        for(i = 0; i < out[a]; i++){
                                b = link[a][i];
                                c[b] += map[a][i] c[a];
                                in[b]–;
                                assert(in[b] >= 0);
                                if(in[b] == 0){
                                        enqueue(b);
                                }
                        }
                }
        }
        /

        Mistack 2:
          当都为0时要输出NULL
        */
        d = 1;
        for(i = 0; i < n; i++){
                if(out[i] == 0 && c[i] > 0){
                        printf("%d %d\n", i + 1, c[i]);
                        d = 0;
                }
        }
        if(d){
                printf("NULL\n");
        }
        return 0;
}

发表回复

您的电子邮箱地址不会被公开。