C++14(g++5.4) 解法, 执行用时: 23ms, 内存消耗: 6104K, 提交时间: 2018-08-18 18:33:52

#include<bits/stdc++.h>
#define maxn 50010
using namespace std;
struct Edge
{
	int to;
	char c;
};
vector<Edge> G[maxn];
bool vis[maxn];
int p[maxn],g[maxn],f[maxn];
void slove(int x)
{
	if(vis[x])
		return;
	vis[x]=1;
	p[x]=1;
	int y;
	for(int i=0;i<G[x].size();i++)
	{
		y=G[x][i].to;
		slove(y);
		if(G[x][i].c=='_') f[x]+=f[y],p[x]+=p[y],g[x]+=g[y];
		if(G[x][i].c=='.') g[x]+=p[y];
		if(G[x][i].c>='a'&&G[x][i].c<='z') g[x]+=g[y];
		if(G[x][i].c>='A'&&G[x][i].c<='Z') f[x]+=g[y];
	}
}
int main()
{
	int n,m;
	scanf("%d%d",&n,&m);
	while(m--)
	{
		int a,b;
		char c;
		scanf("%d %d %c",&a,&b,&c);
		Edge e;
		e.to=b;
		e.c=c;
		G[a].push_back(e);
	}
	memset(vis,0,sizeof(vis));
	for(int i=1;i<=n;i++)
	{
		slove(i);
	}
	int ans=0;
	for(int i=1;i<=n;i++)
		ans+=f[i];
	printf("%u\n",ans);


	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 28ms, 内存消耗: 1996K, 提交时间: 2018-08-17 19:46:41

#include<bits/stdc++.h>
using namespace std;
#define MAXN 50005
int h[MAXN],ne[MAXN],p[MAXN],n,m,i,j,in[MAXN],f[MAXN][3],ans,q[MAXN],he,ta;
char w[MAXN],c[10];
int main()
{
	scanf("%d%d",&n,&m);
	for(i=1;i<=m;i++)
	{
		scanf("%d%d%s",&j,p+i,c);
		w[i]=c[0];
		ne[i]=h[j];
		h[j]=i;
		in[p[i]]++;
	}
	for(i=1;i<=n;i++)if(!in[i])q[ta++]=i;
	while(he!=ta)
	{
		i=q[he++];
		ans+=f[i][2];
		f[i][0]++;
		for(j=h[i];j;j=ne[j])
		{
			if(w[j]=='.')f[p[j]][2]+=f[i][1];
			else if(w[j]>='A'&&w[j]<='Z')f[p[j]][1]+=f[i][0];
			else
			{
				f[p[j]][1]+=f[i][1];
				if(w[j]=='_')
				{
					f[p[j]][0]+=f[i][0];
					f[p[j]][2]+=f[i][2];
				}
			}
			if(!(--in[p[j]]))q[ta++]=p[j];
		}
	}
	cout<<(unsigned)(ans)<<endl;
	return 0;
}