constint N = 10010, M = 20010; int n, m; int h[N], e[M], ne[M], idx; int q[N], din[N]; int dist[N];
voidadd(int a, int b){ e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ; }
booltopsort(){ int hh = 0, tt = -1; for (int i = 1; i <= n; i ++ ) { if (!din[i]) q[ ++ tt] = i; } while (hh <= tt) { int t = q[ hh ++ ]; for (int i = h[t]; ~i; i = ne[i]) { int j = e[i]; if (-- din[j] == 0) q[ ++ tt] = j; } } return tt == n - 1; // 判断有没有环 有环则无解。 }
intmain(){ cin >> n >> m; memset(h, -1, sizeof h); while (m -- ) { int a, b; cin >> a >> b; add(b, a); // 不等式转换成图的 连边规则。 din[a] ++ ; } if (!topsort()) puts("Poor Xed"); else { // 初始化每个人最少100块钱 for (int i = 1; i <= n; i ++ ) dist[i] = 100; // 拓扑排序求最大值 依次按照顺序求就行 for (int i = 0; i < n; i ++ ) { int j = q[i]; // 求长路 for (int k = h[j]; ~k; k = ne[k]) dist[e[k]] = max(dist[e[k]], dist[j] + 1); } int res = 0; for (int i = 1; i <= n; i ++ ) res += dist[i]; cout << res << endl; } return0; }
constint N = 30010, M = 30010; int n, m; int h[N], e[M], ne[M], idx; int q[N], din[N]; bitset<N> f[N];
voidadd(int a, int b){ e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ; }
// 拓扑排序模板 voidtopsort(){ int hh = 0, tt = -1; for (int i = 1; i <= n; i ++ ) if (!din[i]) q[ ++ tt] = i; while (hh <= tt) { int t = q[hh ++ ]; for (int i = h[t]; ~i; i = ne[i]) { int j = e[i]; if (-- din[j] == 0) { q[ ++ tt] = j; } } } }
intmain(){ cin >> n >> m; memset(h, -1, sizeof h); while (m -- ) { int a, b; cin >> a >> b; add(a, b); din[b] ++ ; } topsort(); // 如果x能到达y1,y2 那么想求f[x] 必须先求出f[y1]和f[y2] // 而拓扑排序后 x一定在它能到的点(y1,y2)的前面 所以这里需要倒序 for (int i = n - 1; i >= 0; i -- ) { int j = q[i]; // 初始化当前节点的f值为1 表示节点自己能到自己 f[j][j] = 1; // 所有点j能到达的点 e[k] for (int k = h[j]; ~k; k = ne[k]) // 那么f[j]就是 点j自身 和 所有f[e[k]]的并集 // 二进制操作中就是 或运算 f[j] |= f[e[k]]; } for (int i = 1; i <= n; i ++ ) { cout << f[i].count() << endl; } return0; }
// 注意点的数量是n+m 边极限数量1000*1000 constint N = 2010, M = 1000010; int h[N], e[M], w[M], ne[M], idx; int q[N], din[N], dist[N]; // 求拓扑序和最大路径 bool st[N]; int n, m;
voidadd(int a, int b, int c){ e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ; din[b] ++ ; }
// 拓扑排序模板 voidtopsort(){ int hh = 0, tt = -1; for (int i = 1; i <= n + m; i ++ ) { if (!din[i]) q[ ++ tt] = i; } while (hh <= tt) { int t = q[hh ++ ]; for (int i = h[t]; ~i; i = ne[i]) { int j = e[i]; if (-- din[j] == 0) q[ ++ tt] = j; } } }
intmain(){ memset(h, -1, sizeof h); cin >> n >> m; for (int i = 1; i <= m; i ++ ) { memset(st, 0, sizeof st); int cnt; scanf("%d", &cnt); // 初始站是最小值,终点站是最大值, // 为了方便后续计算,把初始站初始化成n,终点站设置成1 int start = n, end = 1; for (int j = 0; j < cnt; j ++ ) { int stop; scanf("%d", &stop); // 停靠的站 start = min(start, stop); end = max(end, stop); st[stop] = true; // 判断是否是停靠的站 } int ver = n + i; // 虚拟源点 // 建边 for (int j = start; j <= end; j ++ ) { // 如果是停靠的站 则是左面的边 指向虚拟源点 权重是0 // 否则是右面的边 虚拟原点指向它 权重是1 if (!st[j]) add(j, ver, 0); else add(ver, j, 1); } } topsort(); // 初始化所有车站的距离 for (int i = 1; i <= n; i ++ ) dist[i] = 1; // 求一下每个点的最大距离 for (int i = 0; i < n + m; i ++ ) { int j = q[i]; for (int k = h[j]; ~k; k = ne[k]) { dist[e[k]] = max(dist[e[k]], dist[j] + w[k]); } } // 在所有最长距离中求出最长的点 根据最终问题 只需要 求所有停靠的点就行了 int res = 0; for (int i = 1; i <= n; i ++ ) res = max(res, dist[i]); cout << res << endl; return0; }