AcWing 1192题解（拓扑排序 差分约束）
发布时间
阅读量：
阅读量
AcWing 1192. 奖金
将拓扑排序与差分约束系统相结合，需要注意的是，本题旨在寻找最小路径，因此在处理过程中需为每个节点确定最大值。在构建图结构时，应将数值较小的节点指向数值较大的节点，例如表达式a>=b+1可转化为从b到a的边添加操作。
#include<bits/stdc++.h>
using namespace std;
const int N = 1e4 + 10, M = 4e4 + 10;
int h[N], e[M], ne[M], idx;
int n, m;
int dist[N];
int q[N];
int din[N];
int ans;
void add(int a, int b){
e[idx] = b;
ne[idx] = h[a];
h[a] = idx ++ ;
}
bool topsort(){
int hh = 0, tt = -1;
for(int i = 1; i <= n; i ++ ){
if(!din[i]){全部评论 (0)
还没有任何评论哟~