@[Rain_chr](/user/684254) 拓扑最开始可以入队所有入度为 0 的点。
对于非 n+1 的入度为 0 点,他们一定与 n+1 不连通,将其贡献设为 0。这样可以同时解决 1,2 两个问题。
by William_Wang_ @ 2023-07-12 11:35:46
@[UFO2007](/user/173077) 是的,但并不是每一道题都能够这么处理
by Rain_chr @ 2023-07-12 11:45:24
@[UFO2007](/user/173077) 等等,您真的确定吗?
[按您的方法写的](https://www.luogu.com.cn/record/115042358)
[按我方法写的](https://www.luogu.com.cn/record/105506863)
by Rain_chr @ 2023-07-12 11:48:46
@[Rain_chr](/user/684254) 我也 WA 了这个点,可以说一下为什么我的方法会出错吗?我想不到。
by William_Wang_ @ 2023-07-12 12:48:44
@[Rain_chr](/user/684254) 改成您的过了。
by William_Wang_ @ 2023-07-12 13:41:07
区别:
```cpp
// 90pts
while(!q.empty())
{
int u = q.front(); q.pop();
if(siz[u] > 1) f[u] = 36501;
if(flag[u])
{
f[u] = 0;
for(auto v : e[u]) if( -- indeg[v] == 0) q.push(v);
}
else
{
for(auto v : e[u])
{
f[v] += f[u]; f[v] = min(f[v], 36501);
if( -- indeg[v] == 0) q.push(v);
}
}
}
```
```cpp
// 100pts
while(!q.empty())
{
int u = q.front(); q.pop();
for(auto v : e[u]) if( -- indeg[v] == 0) q.push(v);
}
q.push(belong[n]); f[belong[n]] = 1;
while(!q.empty())
{
int u = q.front(); q.pop();
if(siz[u] > 1) f[u] = 36501;
for(auto v : e[u])
{
f[v] += f[u]; f[v] = min(f[v], 36501);
if( -- indeg[v] == 0) q.push(v);
}
}
```
by William_Wang_ @ 2023-07-12 13:46:33
@[UFO2007](/user/173077) 我之前说可以是因为转移是dp[to]+=dp[x]的,而不是dp[to]=dp[x]+1的,如果是后者那么按0加入会有很大的影响
by Rain_chr @ 2023-07-12 14:03:40
@[UFO2007](/user/173077) 于是我看了看我之前的代码,我之前对是环的dp[x]赋值,所以这样也会对其他点产生影响
by Rain_chr @ 2023-07-12 14:06:31
果然,在您的90pts代码中我看到一句
```cpp
if(siz[u] > 1) f[u] = 36501;
```
如果这个点入度为0,那么就会出问题
by Rain_chr @ 2023-07-12 14:08:19
@[Rain_chr](/user/684254) 可是我在下面加上了
```cpp
if(flag[u])
{
f[u] = 0;
}
```
flag 是判断是否入度 0 且不合法
by William_Wang_ @ 2023-07-12 14:13:08