如果不统计入度,只统计出度,可以完成本题吗?
查看原帖
如果不统计入度,只统计出度,可以完成本题吗?
1125645
DyingEncoder楼主2025/6/29 20:18

思路如下:

  1. 添加有向边时统计出度
  2. 把初始C[i]>0的点加入队列
  3. 每次取出队头,扩展队尾
for(int i=h[t];~i;i=ne[i]){
  int j=e[i];
  C[j]+=w[i]*(C[t]-U[t]);
  if(C[j]>U[j]){
    q.push(j);
  }
}
  1. 输出出度为0,阈值>U[i]的点
2025/6/29 20:18
加载中...