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