CodeForces - 919D Substring (拓扑排序+dp)

题意：将一个字符串上的n个字符视作点，给出m条有向边，求图中路径上最长出现的相同字母数。

分析：首先如果这张图中有环，则可以取无限大的字符数，在求拓扑排序的同时可以确定是否存在环。

之后在拓扑排序的结果上分别对26个字母dp求出最大结果，并取最大值（一定要分别对每个字母dp，否则会出现问题）。

#include<bits/stdc++.h>
using namespace std;
const int maxn =3e5+10;
int N,M;
vector<int> G[maxn];
vector<int> topo;
int indeg[maxn];
int dp[maxn][28];
char str[maxn];

void init()
{
    topo.clear();
    memset(indeg,0,sizeof(indeg));
    for(int i=0;i<=N;++i)   G[i].clear();
}

bool circle()
{
    int v,u,cnt=0;
    queue<int> Q;
    for(int i=1;i<=N;++i){
        if(!indeg[i]){
            Q.push(i);
            cnt++;
        }
    }
    while(!Q.empty()){
        v= Q.front(); Q.pop();
        topo.push_back(v);
        for(int i=0;i<G[v].size();++i){
            u =G[v][i];
            indeg[u]--;
            if(!indeg[u]){ 
                Q.push(u);
                cnt++;
            }
        }                
    }
    if(cnt==N) return false;
    else return true;
}

int solve(int key)
{
    memset(dp,0,sizeof(dp));
    int res=0;
    int e,v,u;
    for(int i =0;i<topo.size();++i){
        v =topo[i];
        e = str[v]-'a';
        if(e==key)
            dp[v][e]++;
        res = max(res,dp[v][key]);
        for(int j = 0;j<G[v].size();++j){
            u = G[v][j];
            dp[u][key]= max(dp[u][key],dp[v][key]);
        }
    }
    return res;
}

int main()
{
    int v,u;
    while(~scanf("%d%d",&N,&M)){
        init();
        scanf("%s",str+1);
        for(int i=0;i<M;++i){
            scanf("%d%d",&v,&u);
            G[v].push_back(u);
            indeg[u]++;        
        }
        if(circle()){
            printf("-1\n");
            continue;
        }
        int res=0;
        for(int i=0;i<26;++i){
            res=max(res,solve(i));
        }
        printf("%d\n",res);
    }
    return 0;
}

CodeForces - 919D Substring (拓扑排序+dp)

推荐阅读