1. 拓扑排序+bitset

第一次使用bitset，复杂度：N/32，比N小

所以总的时间复杂度为O(N*(N+M)/32)

#include <iostream>
#include <bitset>
#include <queue>
using namespace std;
const int N = 3e4+20;
bitset<N> f[N];
struct NODE{int to, next;
}edge[N];
int head[N], cnt, inv[N], n, m;
void add(int u, int v) {++cnt;edge[cnt].to = v, edge[cnt].next = head[u], head[u] = cnt;
}void topo() {queue<int> q;for(int i=1; i<=n; i++) {if(!inv[i]) q.push(i);}while(!q.empty()) {int x = q.front();q.pop();f[x][x] = 1; //自己可到达for(int i = head[x]; i; i = edge[i].next) {int v = edge[i].to;f[v] |= f[x];inv[v]--;if(!inv[v]) q.push(v);}}for(int i=1; i<=n; i++) printf("%d\n", f[i].count()); //二进制中1的个数
}int main() {int u, v; scanf("%d%d", &n, &m);while(m--){scanf("%d%d", &u, &v);add(v, u); //反向建图inv[u]++;}topo();return 0;
}

2. 01分数规划, spfa判断正环

题目链接：Acwing 观光奶牛

#include <bits/stdc++.h>
using namespace std;
const int N = 1050, M = 5005;
int head[N], cnt, n, ct[N], st[N];
double dis[N], f[N];
struct NODE{int to, next, w;
}edge[M];void add(int u, int v, int w){++cnt;edge[cnt].to = v, edge[cnt].next = head[u], head[u] = cnt;edge[cnt].w = w;
}bool spfa(double mid) {queue<int> q;for(int i=1; i<=n; i++) q.push(i), st[i] = true, dis[i] = ct[i] = 0;while(!q.empty()) {int x = q.front();q.pop();st[x] = false;for(int i = head[x]; i; i = edge[i].next) {int v = edge[i].to;if( dis[v] < dis[x] + f[x] - mid * edge[i].w) { //判断正环dis[v] = dis[x] + f[x] - mid * edge[i].w;ct[v] = ct[x]+1;if(ct[v] >= n) return true;if(!st[v]) {q.push(v), st[v] = true;}}}}return false;
}
int main() {int p; scanf("%d%d", &n, &p);for(int i=1; i<=n; i++) cin >> f[i];int a, b, w;while(p--) {scanf("%d%d%d", &a, &b, &w);add(a, b, w);}double l = 0, r = 1010, eps = 1e-4;while(r-l > eps) {double mid = (l+r)/2;if(spfa(mid)) l = mid;else r =mid;}printf("%.2lf", l);return 0;
}