今日份DAG呈上
https://www.acwing.com/problem/content/458/
题意:同一趟车次内,停靠的车站\(a\)的等级严格大于未停靠的车站\(b\)的等级
所以可以根据\(a>b\)来建边(即,所有未停靠站建边指向所有停靠站)
优化:对于两个点集之间,可以在中间建立一个虚拟源点,复杂度O(n*m)变成O(n+m)
把虚拟源点的值取为左边点集的最大值,左集连到虚拟源点的权值为0,点到右集的权值为1
每条车路径对应一个虚拟源点\(n+i\)
Key:拓扑排序+虚拟源点
#include <bits/stdc++.h> using namespace std; const int N = 2005, M = N * N; //外加1000个虚拟点 int n, m, cnt = 1; int h[N], e[M], ne[M], w[M], idx; int d[N], a[N], dis[N]; bool stop[N]; void add (int a, int b, int c) { e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++; d[b] ++; //topsort特供,记得入度 } void topsort () { queue <int> q; for (int i = 1; i <= n + m; i ++) //n + m if (d[i] == 0) q.push (i); while (!q.empty()) { int t = q.front(); q.pop(); a[cnt ++] = t; for (int i = h[t]; i != -1; i = ne[i]) { int j = e[i]; d[j] --; if (d[j] == 0) q.push (j); } } } int main () { memset (h, -1, sizeof h); cin >> n >> m; for (int i = 1; i <= m; i ++) { memset (stop, false, sizeof stop); int k; cin >> k; int st = n, ed = 1; for (int j = 0; j < k; j ++) { int s; cin >> s; st = min (st, s), ed = max (ed, s); stop[s] = true; //代表该点是站点 } //重点来了,建图要用虚拟源点 int virtue_n = n + i; //是 i for (int j = st; j <= ed; j ++) { if (stop[j]) //下标写错痛哭一万年 add (virtue_n, j, 1); else add (j, virtue_n, 0); } } topsort(); for (int i = 1; i <= n; i ++) dis[i] = 1; for (int i = 0; i < n + m; i ++) { int j = a[i]; for (int k = h[j]; k != -1; k = ne[k]) { int t = e[k]; dis[t] = max (dis[t], dis[j] + w[k]); } } int ans = 0; for (int i = 1; i <= n; i ++) ans = max (ans, dis[i]); cout << ans << endl; }
提高课77 AC 祭