在 DAG 中, 拓扑排序可以确定 dp 的顺序
把图的信息转化到一个拓扑序上
注意转移的时候要用边转移
这道题的 dp 是用刷表法
- #include<bits/stdc++.h>
- #define REP(i, a, b) for(register int i = (a); i <(b); i++)
- #define _for(i, a, b) for(register int i = (a); i <= (b); i++)
- using namespace std;
- const int MAXN = 1e5 + 10;
- struct Edge{ int to, next; };
- Edge e[MAXN << 1];
- int head[MAXN], d[MAXN];
- int topo[MAXN], dp[MAXN];
- int n, m, cnt, tot;
- void AddEdge(int from, int to)
- {
- e[tot] = Edge{to, head[from]};
- head[from] = tot++;
- }
- void read(int& x)
- {
- int f = 1; x = 0; char ch = getchar();
- while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getchar(); }
- while(isdigit(ch)) { x = x * 10 + ch - '0'; ch = getchar(); }
- x *= f;
- }
- void toposort()
- {
- queue<int> q;
- _for(i, 1, n)
- if(!d[i])
- q.push(i);
- while(!q.empty())
- {
- int u = q.front(); q.pop();
- topo[++cnt] = u;
- for(int i = head[u]; ~i; i = e[i].next)
- {
- int v = e[i].to;
- if(--d[v] == 0) q.push(v);
- }
- }
- }
- int main()
- {
- memset(head, -1, sizeof(head)); tot = 0;
- read(n); read(m);
- _for(i, 1, m)
- {
- int u, v;
- read(u); read(v);
- AddEdge(u, v);
- d[v]++;
- }
- toposort();
- _for(i, 1, n) dp[i] = 1;
- _for(i, 1, n)
- {
- int u = topo[i];
- for(int i = head[u]; ~i; i = e[i].next)
- {
- int v = e[i].to;
- dp[v] = max(dp[v], dp[u] + 1);
- }
- }
- _for(i, 1, n) printf("%d\n", dp[i]);
- return 0;
- }
还可以用记忆化搜索
- #include<bits/stdc++.h>
- #define REP(i, a, b) for(register int i = (a); i < (b); i++)
- #define _for(i, a, b) for(register int i = (a); i <= (b); i++)
- using namespace std;
- const int MAXN = 1e5 + 10;
- struct Edge{ int to, next; };
- Edge e[MAXN << 1];
- int head[MAXN], dp[MAXN];
- int n, m, cnt, tot;
- void AddEdge(int from, int to)
- {
- e[tot] = Edge{to, head[from]};
- head[from] = tot++;
- }
- void read(int& x)
- {
- int f = 1; x = 0; char ch = getchar();
- while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getchar(); }
- while(isdigit(ch)) { x = x * 10 + ch - '0'; ch = getchar(); }
- x *= f;
- }
- int dfs(int u)
- {
- if(dp[u] != -1) return dp[u];
- dp[u] = 1;
- for(int i = head[u]; ~i; i = e[i].next)
- {
- int v = e[i].to;
- dp[u] = max(dp[u], dfs(v) + 1);
- }
- return dp[u];
- }
- int main()
- {
- memset(head, -1, sizeof(head)); tot = 0;
- read(n); read(m);
- _for(i, 1, m)
- {
- int u, v;
- read(u); read(v);
- AddEdge(v, u);
- }
- memset(dp, -1, sizeof(dp));
- _for(i, 1, n) printf("%d\n", dfs(i));
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2828640.html