题意分析

本题要求编写一个程序来帮助阿尔杰农追踪工厂中化学品的流动路径。工厂中有(N)个工作台，每个工作台排放特定的化学品，同时也能中和某些化学品。工作台之间通过管道连接，存在上下游关系。程序需要根据输入的工作台信息和管道连接关系，计算每个工作台最终输出的化学品列表并按规定格式输出。

解题思路

1. 数据存储
   • 使用数组 output[MAXN] 存储每个工作台排放的化学品信息，neutra[MAXN] 存储每个工作台能中和的化学品信息。通过位运算来表示化学品，利用 mask 数组实现位掩码操作。
   • 使用二维数组 graph[MAXN][MAXN] 表示工作台之间的连接关系，graph[i][j] 为 true 表示工作台 i 位于工作台 j 的上游。
2. 读取输入
   • 首先读取工作台数量 n。
   • 然后依次读取每个工作台排放和中和的化学品信息，通过位运算将化学品信息存储到相应数组中。
   • 接着读取工作台之间的连接关系，设置 graph 数组。
3. 化学品流动模拟
   • 使用一个循环来不断更新每个工作台的输出化学品信息。对于每个工作台 i，如果它有未处理的信息（table[i] 为 true），则将其输出信息 temp 传播到下游工作台 j（graph[i][j] 为 true）。计算下游工作台新的输出信息 newOut，如果与原来的不同，则更新下游工作台的输出信息，并标记该工作台需要进一步处理（table[j] = true）。
4. 输出结果
   • 遍历每个工作台的输出信息，按字母顺序输出每个工作台输出的化学品列表。

代码实现

#include <stdio.h>
#include <memory.h>

const int MAXN = 51;

int main()
{
    int i, j;
    int mask[32];
    for (i = 0; i < 32; i++) 
        mask[i] = 1<<i;
    int line = 0;   
    if (line) printf("\n");
    line = 1;
    int output[MAXN];
    int dump[MAXN];
    int neutra[MAXN];
    char c;
    int n;
    scanf("%d\n", &n);
    for (i = 1; i <= n; i++)
    {    
        int temp = 0;
        do    {    
            c = getc(stdin);
            if (c >= 'A') temp |= mask[c-'A'];
        } while (c != ' ');
        dump[i] =  output[i] = temp;
        temp = 0;
        while((c = getc(stdin)) != '\n')
            if (c >= 'A') temp |= mask[c-'A'];
        neutra[i] = temp; 
        dump[i] &= ~temp; 
        output[i] &= ~temp;
    }
    bool graph[MAXN][MAXN];
    bool table[MAXN];
    memset(graph, 0, sizeof(graph));
    for (i = 1; i <= n; i++)
        table[i] = true;
    int a, b;
    while(scanf("%d %d", &a, &b) && (a || b)) 
        graph[a][b] = true;
    bool flag;
    do  {
        flag = false;
        for (i = 1; i <= n; i++)
            if (table[i])
        {    
            table[i] = false;
            int temp = output[i];
            for (j = 1; j <= n; j++)
                if (graph[i][j])
            {    
                int newOut = (output[j] | temp) & (~neutra[j]);
                if (output[j] != newOut)
                {    
                    output[j] = newOut; 
                    table[j] = true;
                }
            }
            flag = true;
            break;
        }
    } while (flag);
    
    for (i = 1; i <= n; i++)
    {    
        printf(":");
        for (j = 0; j <= 25; j++)
            if ((output[i] & mask[j]) != 0) 
                printf("%c", char(j+'A'));
        printf(":\n");
    }
    return 0;
}