CF467D 题解

· · 题解

思路

通过拓扑将含 r 或 R 较少的赋值给含 r 或 R 较多的即可。

然而又环会让拓扑难以完成，故 Tarjan 缩点是最好的方式。

细节

首先，使用 map 将字符串转化为数字，注意第 4 至 2+m 行均要转化。
方便起见，建议大写转小写。

然后缩点。只要对第 2 行中输入的字符串数，及其能转化的字符串进行缩点即可。
存下强连通分量含第 2 行中输入的字符串数 \operatorname{cor}，最小含 r 数 \operatorname{mnr}，含 r 最少时最短长度 \operatorname{mnl}。

建边。方便起见，反向建。

拓扑。

由于处于同一强连通分量的两点可互相抵达，故设两答案为 \operatorname{ans_1}，\operatorname{ans_2}，则

\operatorname{ans_1}=\operatorname{cor}\times \operatorname{mnr} \operatorname{ans_2}=\operatorname{cor}\times \operatorname{mnl}

代码实现

#include<bits/stdc++.h>
using namespace std;
int n,m,t,c;
map<string,int>mp;
int f[300002];
int cr[300002],cl[300002];
vector<int>e[300002],E[300002];
int dfn[300002],low[300002];
bool vis[300002];
int st[300002],top;
int tot;
int mnr[300002],mnl[300002],cor[300002];
bool in[300002];
void tarjan(int u){
    dfn[u]=low[u]=++c;
    st[++top]=u;
    vis[u]=1;
    for(int v:e[u]){
        if(!dfn[v]){
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }else if(vis[v]){
            low[u]=min(low[u],dfn[v]);
        }
    }
    if(dfn[u]==low[u]){
        ++tot;
        while(1){
            int t=st[top--];
            vis[t]=0;
            f[t]=tot;
            if(cr[t]<mnr[tot]){
                mnr[tot]=cr[t];
                mnl[tot]=cl[t];
            }else if(cr[t]==mnr[tot]){
                mnl[tot]=min(mnl[tot],cl[t]);
            }
            if(t<=n){
                ++cor[tot];
            }
            if(t==u){
                break;
            }
        }
    }
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        string s;
        cin>>s;
        cl[i]=s.length();
        for(int j=0;j<cl[i];j++){
            if(s[j]<'a'){
                s[j]+=32;
            }
            if(s[j]=='r'){
                ++cr[i];
            }
        }
        mp[s]=++t;
    }
    scanf("%d",&m);
    for(int i=1;i<=m;i++){
        string x,y;
        cin>>x>>y;
        int lx=x.length(),ly=y.length();
        for(int j=0;j<lx;j++){
            if(x[j]<'a'){
                x[j]+=32;
            }
        }
        for(int j=0;j<ly;j++){
            if(y[j]<'a'){
                y[j]+=32;
            }
        }
        if(!mp[x]){
            mp[x]=++t;
            cl[mp[x]]=lx;
            for(int j=0;j<cl[mp[x]];j++){
                if(x[j]=='r'){
                    ++cr[mp[x]];
                }
            }
        }
        if(!mp[y]){
            mp[y]=++t;
            cl[mp[y]]=y.length();
            for(int j=0;j<cl[mp[y]];j++){
                if(y[j]=='r'){
                    ++cr[mp[y]];
                }
            }
        }
        e[mp[x]].push_back(mp[y]);
    }
    memset(mnr,0x3f,sizeof mnr);
    memset(mnl,0x3f,sizeof mnl);
    for(int i=1;i<=n;i++){
        if(!dfn[i]){
            tarjan(i);
        }
    }
    for(int i=1;i<=t;i++){
        if(f[i]){
            for(auto v:e[i]){
                if(f[i]!=f[v]&&f[v]){
                    E[f[v]].push_back(f[i]);
                    in[f[i]]=1;
                }
            }
        }
    }
    queue<int>q;
    for(int i=1;i<=tot;i++){
        if(!in[i]){
            q.push(i);
        }
    }
    while(!q.empty()){
        int t=q.front();
        q.pop();
        for(auto v:E[t]){
            if(mnr[v]>mnr[t]){
                mnr[v]=mnr[t];
                mnl[v]=mnl[t];
            }else if(mnr[t]==mnr[v]){
                mnl[v]=min(mnl[t],mnl[v]);
            }
        }
    }
    long long ans1=0,ans2=0;
    for(int i=1;i<=tot;i++){
        ans1+=cor[i]*mnr[i];
        ans2+=cor[i]*mnl[i];
    }
    printf("%d %d",ans1,ans2);
    return 0;
}