Codeforces 919D Substring (拓撲圖DP)

手動博客搬家: 本文發表于20180716 10:53:12, 原地址https://blog.csdn.net/suncongbo/article/details/81061500

給定一個\(n\)個點\(m\)條邊的有向圖（不一定無環），每個點上有一個小寫字母。要找一條路徑，使得路徑上出現次數最多的字母出現的次數最多。如果答案為無窮大輸出-1.
題解：何時無窮大？有環的時候可以不停地走環，統計無限次答案，答案為無窮大。因此，對于-1的情況，只需要判一下環即可。
對于有限大的情況，令\(dp[i][c]\)表示以第\(i\)個節點結束的路徑中含有\(c\)這個字母次數的最大值。則有\(dp[i][c]=\max_{j\in ind[i]}{dp[j][c]}+[a[i]==c]\), \(a[i]\)為第\(i\)個點的字母。
然后就可以得到答案了。時間復雜度\(O(mS)\), S為字符集大小26.
代碼如下：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;const int N = 3e5;
const int S = 26;
struct Edge
{int v,nxt; bool used;
} e[N+3];
int fe[N+2];
char s[N+2];
int a[N+2];
int dfn[N+2],low[N+2];
int sta[N+2];
bool ins[N+2],vis[N+2];
int dp[N+2][S+2];
int ind[N+2];
int que[N+2];
int n,m,tp,mx,head,tail,tot;void addedge(int u,int v)
{e[++m].v = v; e[m].nxt = fe[u]; fe[u] = m;
}void Tarjan(int u)
{dfn[u] = low[u] = ++tp; sta[tp] = u; ins[u] = true;for(int i=fe[u]; i; i=e[i].nxt){int v = e[i].v;if(!dfn[v]) {Tarjan(v); low[u] = min(low[v],low[u]);}else if(ins[v]) low[u] = min(low[u],dfn[v]);}if(dfn[u]==low[u]){int tmp = 1;while(sta[tp]!=u && tp>0){int v = sta[tp];ins[v] = false;tp--; tmp++;}ins[u] = false; tp--;if(tmp>mx) mx = tmp;}
}int main()
{int m0; m = 0;scanf("%d%d",&n,&m0);scanf("%s",s+1); for(int i=1; i<=n; i++) a[i] = (int)s[i]-'a'+1;for(int i=1; i<=m0; i++) {int x,y; scanf("%d%d",&x,&y); addedge(x,y); if(x==y) {printf("-1\n"); return 0;}}for(int i=1; i<=n; i++) {if(!dfn[i]) Tarjan(i);}if(mx>1) {printf("-1\n"); return 0;}for(int i=1; i<=n; i++){for(int j=fe[i]; j; j=e[j].nxt) ind[e[j].v]++;}tot = 0;for(int i=1; i<=n; i++) dp[i][a[i]] = 1;while(tot<n){for(int j=1; j<=n; j++){if(ind[j]==0 && vis[j]==false){tail++;que[head] = j; vis[j] = true; tot++;while(head<=tail){int c = que[head++];for(int i=fe[c]; i; i=e[i].nxt){if(e[i].used) continue;e[i].used = true;ind[e[i].v]--;for(int k=1; k<=S; k++){if(a[e[i].v]==k) dp[e[i].v][k] = max(dp[e[i].v][k],dp[c][k]+1);else dp[e[i].v][k] = max(dp[e[i].v][k],dp[c][k]);}if(ind[e[i].v]==0 && vis[e[i].v]==false){vis[e[i].v] = true; tot++;que[++tail] = e[i].v;}}}}}}int ans = 0;for(int i=1; i<=n; i++){for(int j=1; j<=S; j++) ans = max(ans,dp[i][j]);}printf("%d\n",ans);return 0;
}