鏈接：https://ac.nowcoder.com/acm/contest/160/B
來源：牛客網

題目描述
給一個含n個點m條邊的有向無環圖（允許重邊，點用1到n的整數表示），每條邊上有一個字符，問圖上有幾條路徑滿足路徑上經過的邊上的字符組成的的字符串去掉空格后以大寫字母開頭，句號 '.' 結尾，中間都是小寫字母，小寫字母可以為0個。
輸入描述:
第一行兩個整數n,m
接下來m行，每行兩個整數a,b和一個字符c，表示一條起點為a，終點為b的邊，邊上的字符是c
1 ≤ n, m ≤ 50000
1 ≤ a < b ≤ n
c可以是大小寫字母、句號 '.' 或空格（方便起見用 '' 表示空格）
輸出描述:
輸出一個整數，表示答案對232取模的結果
示例1
輸入
復制
6 11
1 2 A
1 2
3 4
2 4 B
2 3 a
2 3
2 4 b
4 5 .
3 5 .
2 5 .
5 6 _
輸出
復制
16

思路：
首先進行拓撲排序，

為什么要進行拓撲排序呢？

我們知道因為這是一個有向圖，拓撲排序后不存在兩個節點a,b 拓撲序中b在a的后面，而b有一條邊指向a，這是不存在的。

因為在dp的過程中，我們的后一個狀態是根據前一個狀態轉移過來的，這就要求上一個狀態一定是不能再有改變的了。

即動態規劃的無后效性：

當前的值只和當前的狀態有關，和之前怎么來到這個狀態和之后怎么去其他狀態都無關。

那么我們再拓撲排序之后，就可以根據有向邊的字符類對狀態進行轉移。

我們定義dp狀態如下：

dp[i][0] ： 以i節點為結尾的路徑中，只包括空格的路徑個數。

dp[i][1] ： 以i節點為結尾的路徑中，去掉空格后，第一個字符為大寫字符，后面均為小寫字符串的路徑個數。

dp[i][0] ： 以i節點為結尾的路徑中，以'.' 為結尾的合法路徑個數 。

轉移方程見代碼。

注意：本題有一個坑：所謂的以大寫字母意思是去掉空格后，第一個字符為大寫字符，不能有多個大寫字母。

細節見代碼：

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <queue> #include <stack> #include <map> #include <set> #include <vector> #include <iomanip> #define ALL(x) (x).begin(), (x).end() #define rt return #define dll(x) scanf("%I64d",&x) #define xll(x) printf("%I64d\n",x) #define sz(a) int(a.size()) #define all(a) a.begin(), a.end() #define rep(i,x,n) for(int i=x;i<n;i++) #define repd(i,x,n) for(int i=x;i<=n;i++) #define pii pair<int,int> #define pll pair<long long ,long long> #define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) #define MS0(X) memset((X), 0, sizeof((X))) #define MSC0(X) memset((X), '\0', sizeof((X))) #define pb push_back #define mp make_pair #define fi first #define se second #define eps 1e-6 #define gg(x) getInt(&x) #define chu(x) cout<<"["<<#x<<" "<<(x)<<"]"<<endl using namespace std; typedef long long ll; ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;} ll lcm(ll a, ll b) {return a / gcd(a, b) * b;} ll powmod(ll a, ll b, ll MOD) {ll ans = 1; while (b) {if (b % 2) { ans = ans * a % MOD; } a = a * a % MOD; b /= 2;} return ans;} inline void getInt(int *p); const int maxn = 1000010; const int inf = 0x3f3f3f3f; /*** TEMPLATE CODE * * STARTS HERE ***/ struct node {int from;int to;char t;node () {}node(int ff, int tt, int ty){from = ff;to = tt;t = ty;} }; int n, m; std::vector<node> son[maxn]; queue<node> q; node a[maxn]; int in[maxn]; ll dp[maxn][3]; const ll mod = (1ll << 32); int main() {//freopen("D:\\code\\text\\input.txt","r",stdin);//freopen("D:\\code\\text\\output.txt","w",stdout);gbtb;cin >> n >> m;int u, v;char t;repd(i, 1, m) {cin >> u >> v >> t;son[u].pb(node(u, v, t));in[v]++;}repd(i, 1, n) {if (!in[i]) {q.push(node(0, i, '_'));}}int cnt = 0;node temp;while (!q.empty()) {temp = q.front();q.pop();for (auto x : son[temp.to]) {a[++cnt] = x;in[x.to]--;if (!in[x.to]) {q.push(x);}}}repd(i, 1, cnt) {if (a[i].t == '_') {dp[a[i].to][0] += dp[a[i].from][0] + 1;dp[a[i].to][1] += dp[a[i].from][1];dp[a[i].to][2] += dp[a[i].from][2];}if (a[i].t == '.') {dp[a[i].to][2] += dp[a[i].from][1];}if (a[i].t <= 'Z' && a[i].t >= 'A') {dp[a[i].to][1] += dp[a[i].from][0] + 1;}if (a[i].t <= 'z' && a[i].t >= 'a') {dp[a[i].to][1] += dp[a[i].from][1];}repd(j, 0, 2) {dp[a[i].to][j] %= mod;}}ll ans = 0ll;repd(i, 1, n) {ans = (ans + dp[i][2]) % mod;}cout << ans << endl;return 0; }inline void getInt(int *p) {char ch;do {ch = getchar();} while (ch == ' ' || ch == '\n');if (ch == '-') {*p = -(getchar() - '0');while ((ch = getchar()) >= '0' && ch <= '9') {*p = *p * 10 - ch + '0';}} else {*p = ch - '0';while ((ch = getchar()) >= '0' && ch <= '9') {*p = *p * 10 + ch - '0';}} }

轉載于:https://www.cnblogs.com/qieqiemin/p/11272749.html

總結

以上是生活随笔為你收集整理的Wannafly挑战赛22 B字符路径 （ 拓扑排序+dp ）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。