本文共 3322 字，大约阅读时间需要 11 分钟。
题意：给一篇文章，再给一些单词替换关系a b，表示单词a可被b替换，可多次替换，问最后把这篇文章替换后（或不替换）能达到的最小的'r'的个数是多少，如果'r'的个数相等，那么尽量是文章最短。
解法：易知单词间有二元关系，我们将每个二元关系建有向边，然后得出一张图，图中可能有强连通分量（环等），所以找出所有的强连通分量缩点，那个点的minR,Len赋为强连通分量中最小的minR,Len，然后重新建图，跑一个dfs即可得出每个强连通分量的minR,Len，最后O(n)扫一遍替换单词，统计即可。
代码：
#include #include #include #include #include #include #include #include #include #include #define INF 0x3f3f3f3f#define lll __int64using namespace std;#define N 100007struct Edge{ int v,next;}G[4*N],G2[4*N];string ss[N];map mp;int minR[4*N],Len[4*N];int nR[4*N],nLen[4*N];int head[4*N],tot,cnt,vis[4*N];int last[4*N],tot2;stack stk;int instk[4*N],now,Time;int low[4*N],dfn[4*N],bel[4*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] = 1; for(int i=head[u];i!=-1;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] = 0; 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,0,sizeof(bel)); memset(instk,0,sizeof(instk)); memset(dfn,0,sizeof(dfn)); memset(low,0,sizeof(low)); Time = 0,cnt = 0; while(!stk.empty()) stk.pop(); int i; for(i=1;i<=now;i++) if(!dfn[i]) tarjan(i);}void Build(){ int i,j; memset(last,-1,sizeof(last)); tot2 = 0; for(i=1;i<=now;i++) { for(j=head[i];j!=-1;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] = 1; for(int i=last[u];i!=-1;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 = 0; mp.clear(); tot = 0; memset(head,-1,sizeof(head)); memset(vis,0,sizeof(vis)); for(i=1;i<=n;i++) { cin>>ss[i]; len = ss[i].length(); int cntR = 0; for(j=0;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=1;i<=m;i++) { sa = "", sb = ""; cin>>sa>>sb; len = sa.length(); int cntR = 0; for(j=0;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 = 0; for(j=0;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=1;i<=now;i++) if(!vis[i]) dfs(i); sumR = 0,sumLen = 0; for(i=1;i<=n;i++) { int u = bel[mp[ss[i]]]; sumR += nR[u]; sumLen += nLen[u]; } printf("%I64d %I64d\n",sumR,sumLen); } return 0;}
还有一种做法就是反向建图，然后sort一下，优先从最优的开始dfs，最后就能得出结果，但是我不知道这样为什么一定正确，如果你知道，那么请评论告诉我吧:)
转载于:https://www.cnblogs.com/whatbeg/p/3981194.html
