文章目录
R
e
s
u
l
t
Result
Result
H
y
p
e
r
l
i
n
k
Hyperlink
Hyperlink
D
e
s
c
r
i
p
t
i
o
n
Description
Description
S
o
l
u
t
i
o
n
Solution
Solution
C
o
d
e
Code
Code
R
e
s
u
l
t
Result
Result
H
y
p
e
r
l
i
n
k
Hyperlink
Hyperlink
https://www.luogu.com.cn/problem/P1038
D
e
s
c
r
i
p
t
i
o
n
Description
Description
一张神经网络可以看做一个
D
A
G
DAG
DAG，它由三种层组成：输入层，传输层，输出层
输入层：初始
C
i
>
0
C_i> 0
Ci>0的层 输出层：没有出边的层 传输层：输入层和输出层相对于整张图的补层
规定传输时要减去阈值
U
i
U_i
Ui，求输出层经过传输后仍然满足
C
i
>
0
C_i>0
Ci>0的点，如果没有，输出
N
U
L
L
NULL
NULL
数据范围：
n
≤
100
n\leq 100
n≤100
S
o
l
u
t
i
o
n
Solution
Solution
考虑让初始
C
i
≤
0
C_i\leq 0
Ci≤0的提前减去
U
i
U_i
Ui，因为到达它们必然要减去，它们不可能作为传输的起点 接着用
b
f
s
bfs
bfs遍历整张图即可
时间复杂度：
O
(
n
+
m
)
O(n+m)
O(n+m)
C
o
d
e
Code
Code
#include<queue>
#include<cctype>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
using namespace std
;int c
[101],u
[101],tot
,l
[101],n
,m
,U
,V
,W
;
bool vis
[101],out
[101];
struct node
{int next
,to
,w
;}e
[100011];
inline void add(int u
,int v
,int w
){e
[++tot
]=(node
){l
[u
],v
,w
};l
[u
]=tot
;return;}
inline LL
read()
{
char c
;LL d
=1,f
=0;
while(c
=getchar(),!isdigit(c
)) if(c
=='-') d
=-1;f
=(f
<<3)+(f
<<1)+c
-48;
while(c
=getchar(),isdigit(c
)) f
=(f
<<3)+(f
<<1)+c
-48;
return d
*f
;
}
queue
<int>q
;
signed main()
{
n
=read();m
=read();
for(register int i
=1;i
<=n
;i
++)
{
c
[i
]=read();u
[i
]=read();
if(c
[i
]) q
.push(i
),vis
[i
]=true;
else c
[i
]-=u
[i
];
}
for(register int i
=1;i
<=m
;i
++) U
=read(),V
=read(),W
=read(),add(U
,V
,W
),out
[U
]=true;
while(q
.size())
{
int x
=q
.front();q
.pop();
for(register int i
=l
[x
];i
;i
=e
[i
].next
)
{
int y
=e
[i
].to
,w
=e
[i
].w
;
c
[y
]+=c
[x
]*w
;
if(c
[y
]>0&&vis
[y
]==false) q
.push(y
),vis
[y
]=true;
}
}
bool flg
=true;
for(register int i
=1;i
<=n
;i
++) if(c
[i
]>0&&out
[i
]==false) printf("%d %d\n",i
,c
[i
]),flg
=false;
if(flg
) return puts("NULL")&0;
}
