题意：给一篇文章，再给一些单词替换关系a b，表示单词a可被b替换，可多次替换，问最后把这篇文章替换后（或不替换）能达到的最小的’r’的个数是多少，如果’r’的个数相等，那么尽量是文章最短。
解法：易知单词间有二元关系，我们将每个二元关系建有向边，然后得出一张图，图中可能有强连通分量（环等），所以找出所有的强连通分量缩点，那个点的minR,Len赋为强连通分量中最小的minR,Len，然后重新建图，跑一个dfs即可得出每个强连通分量的minR,Len，最后O(n)扫一遍替换单词，统计即可。
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <map>
#define INF 0x3f3f3f3f
#define lll __int64
using namespace std;
#define N 100007struct Edge
{
int v,next;
}G[*N],G2[*N];
string ss[N];
map<string,int> mp;
int minR[*N],Len[*N];
int nR[*N],nLen[*N];
int head[*N],tot,cnt,vis[*N];
int last[*N],tot2;
stack<int> stk;
int instk[*N],now,Time;
int low[*N],dfn[*N],bel[*N];
lll sumR,sumLen;void addedge(int u,int v)
{
G[tot].v = v;
G[tot].next = head[u];
head[u] = tot++;
}void addedge2(int u,int v) //建新图
{
G2[tot2].v = v;
G2[tot2].next = last[u];
last[u] = tot2++;
}void tarjan(int u)
{
low[u] = dfn[u] = ++Time;
stk.push(u);
instk[u] = ;
for(int i=head[u];i!=-;i=G[i].next)
{
int v = G[i].v;
if(!dfn[v])
{
tarjan(v);
low[u] = min(low[u],low[v]);
}
else if(instk[v])
low[u] = min(low[u],dfn[v]);
}
if(low[u] == dfn[u])
{
cnt++;
int v;
do{
v = stk.top();
stk.pop();
instk[v] = ;
bel[v] = cnt;
if(minR[v] < nR[cnt] || (minR[v] == nR[cnt] && Len[v] < nLen[cnt]))
nR[cnt] = minR[v],nLen[cnt] = Len[v];
}while(u != v);
}
}void Tarjan()
{
memset(bel,,sizeof(bel));
memset(instk,,sizeof(instk));
memset(dfn,,sizeof(dfn));
memset(low,,sizeof(low));
Time = ,cnt = ;
while(!stk.empty()) stk.pop();
int i;
for(i=;i<=now;i++)
if(!dfn[i])
tarjan(i);
}void Build()
{
int i,j;
memset(last,-,sizeof(last));
tot2 = ;
for(i=;i<=now;i++)
{
for(j=head[i];j!=-;j=G[j].next)
{
int v = G[j].v;
if(bel[i] != bel[v])
addedge2(bel[i],bel[v]);
}
}
}void dfs(int u)
{
if(vis[u]) return;
vis[u] = ;
for(int i=last[u];i!=-;i=G2[i].next)
{
int v = G2[i].v;
dfs(v);
if((nR[v] < nR[u]) || (nR[v] == nR[u] && nLen[v] < nLen[u]))
nR[u] = nR[v],nLen[u] = nLen[v];
}
}int main()
{
int n,m,i,j,len;
while(scanf("%d",&n)!=EOF)
{
now = ;
mp.clear();
tot = ;
memset(head,-,sizeof(head));
memset(vis,,sizeof(vis));
for(i=;i<=n;i++)
{
cin>>ss[i];
len = ss[i].length();
int cntR = ;
for(j=;j<len;j++)
{
if(ss[i][j] >= 'A' && ss[i][j] <= 'Z')
ss[i][j] = ss[i][j]-'A'+'a';
if(ss[i][j] == 'r')
cntR++;
}
if(!mp[ss[i]])
mp[ss[i]] = ++now;
Len[mp[ss[i]]] = len;
minR[mp[ss[i]]] = cntR;
}
scanf("%d",&m);
string sa,sb;
for(i=;i<=m;i++)
{
sa = "", sb = "";
cin>>sa>>sb;
len = sa.length();
int cntR = ;
for(j=;j<len;j++)
{
if(sa[j] >= 'A' && sa[j] <= 'Z')
sa[j] = sa[j]-'A'+'a';
if(sa[j] == 'r')
cntR++;
}
if(!mp[sa])
mp[sa] = ++now;
int a = mp[sa];
Len[a] = len;
minR[a] = cntR; len = sb.length();
cntR = ;
for(j=;j<len;j++)
{
if(sb[j] >= 'A' && sb[j] <= 'Z')
sb[j] = sb[j]-'A'+'a';
if(sb[j] == 'r')
cntR++;
}
if(!mp[sb])
mp[sb] = ++now;
int b = mp[sb];
Len[b] = len;
minR[b] = cntR;
addedge(a,b);
}
memset(nR,INF,sizeof(nR)); //新图的点的minR,Len
memset(nLen,INF,sizeof(nLen));
Tarjan();
Build();
for(i=;i<=now;i++)
if(!vis[i])
dfs(i);
sumR = ,sumLen = ;
for(i=;i<=n;i++)
{
int u = bel[mp[ss[i]]];
sumR += nR[u];
sumLen += nLen[u];
}
printf("%I64d %I64d\n",sumR,sumLen);
}
return ;
}
还有一种做法就是反向建图，然后sort一下，优先从最优的开始dfs，最后就能得出结果，但是我不知道这样为什么一定正确，如果你知道，那么请评论告诉我吧:)
