http://codeforces.com/problemset/problem/919/D

题意：

就是让你输入n字母，并且有m个关系都是a指向b的格式的，然后题目说路的价值是指一条路中字母最大的重复次数，问你最大是多少。

解题思路：

一开始的时候是想直接用记忆化搜索的，后来发现要判断是否成环，这里两种判环的写法都可以。下面给出两种代码

第一种

第一种是拓扑搜索版的，这个和平时的记忆化搜索可能有点区别，它是有点像广搜就是按入度层级递归上去的。

代码

#include<stdio.h>
#include<vector>
#include<queue>
#include<iostream>
using namespace std;
int n,m,res;
const int Maxn = 300005;
char str[Maxn];
int indegree[Maxn];
int _next[Maxn];
int dp[Maxn];
queue<int>q;
vector<int>head;
vector <int> neigh[Maxn];
bool circle()//拓扑排序中的判环法 
{
	int rco=0;
	for(int i=1;i<=n;i++)
	{
		if(indegree[i]==0)//找出入度为0的点 
		{
			q.push(i);//判环用的队列 
			head.push_back(i);//搜索用的数组 
			rco++;//记录出现的次数 
		}
	 } 
	 while(!q.empty())
	 {
	 	int temp=q.front();
	 	q.pop();
	 	for(int i=0;i<neigh[temp].size();i++)
	 	{
	 		int v=neigh[temp][i];
 			indegree[v]--;
 			if(indegree[v]==0)//当产生新的入度为零的点的时候入队，并放进搜索用的数组 
			{
				q.push(v);
				head.push_back(v);
				rco++;//这里也是记录 
			}
		 }
	 }
	 if(rco<n)//如果最终入度为零的点少于全部的点那证明成环了，建议画图试试看 
	 {
	 	return true;
	 }
	 return false;
}
void init(int v)
{
 
}
int main()
{
	ios::sync_with_stdio(false);
	while(cin>>n>>m)
	{
		res=0;
		for(int i=1;i<=n;i++)
		{
			cin>>str[i];
		 } 
		 for(int i=1;i<=m;i++)
		 {
		 	int a,b;
		 	cin>>a>>b;
		 	neigh[a].push_back(b);//把b放进a对应的集合中 
		 	indegree[b]++;
		  } 
		  if(circle())
		  {
		  	cout<<"-1"<<endl;
		  	continue;
		  }
		  for (char let = 'a'; let <= 'z'; let++)//一个一个字母对 
		  {  
			  	for (int i = head.size()-1; i >=0; i--)//从后面开始搜索保证从最低层级开始递推 
				{
					int v =head[i];
//					cout<<"-----------"<<v<<endl;
					int my = str[v] == let;
					dp[v] = my;
					for (int j = 0; j < neigh[v].size(); j++)
					{
						dp[v] = max(dp[v], dp[neigh[v][j]] + my);
					}						
					res = max(res, dp[v]);
				}
		  }
			printf("%d\n", res);
		  
	}
} 

第二种

第二种是深搜递归型的，这种是一条一条路从最深递归上来的。

代码

#include <cstdio>
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <string>
#include <cstring>
#include <sstream>
#include <queue>
#include <iomanip>
#include <algorithm>
#pragma comment(linker, "/STACK:16000000")
using namespace std;
 
const int Maxn = 300005;
 
int n, m;
char str[Maxn];
vector <int> neigh[Maxn];
int tk[Maxn];
vector <int> seq;
int dp[Maxn];
int res;
 
bool findLoop(int v)
{
	if (tk[v] == 2) return false;
	if (tk[v] == 1) return true;
	tk[v] = 1;
	for (int i = 0; i < neigh[v].size(); i++)
		if (findLoop(neigh[v][i])) return true;
	tk[v] = 2;
	seq.push_back(v);
	return false;
}
 
int main()
{
	scanf("%d %d", &n, &m);
	scanf("%s", str + 1);
	for (int i = 0; i < m; i++) 
	{
		int a, b; scanf("%d %d", &a, &b);
		neigh[a].push_back(b);
	}
	for (int i = 1; i <= n; i++) if (!tk[i])
	{
		if (findLoop(i)) 
		{ 
			printf("-1\n"); return 0; 
		}
	}	
	for (char let = 'a'; let <= 'z'; let++)
	{
		for (int i = 0; i < seq.size(); i++) 
		{
			int v = seq[i];
			int my = str[v] == let;
			dp[v] = my;
			for (int j = 0; j < neigh[v].size(); j++)
			{
				dp[v] = max(dp[v], dp[neigh[v][j]] + my);
			}
			res = max(res, dp[v]);
		}
	 } 
		
	printf("%d\n", res);
	return 0;
}

Q.E.D.