题面见 https://ac.nowcoder.com/acm/contest/700#question
题目大意是有n个单词，有k条替换规则（单向替换），每个单词会有一个元音度（单词里元音的个数）和长度，现在希望利用替换规则（每个规则可使用无限次或不用）将每个单词替换成元音度值最小的单词，如果有多个单词元音度同等最小，那么取长度最小的单词。最后输出替换后的n个单词的元音度值之和与长度之和。
单纯每个点暴力搜，无疑会有爆复杂度的风险 1e5*1e5 ，如果记录搜过的点之后不搜，也会有在一个强连通分量里最早的点能搜到最优解，而后来的点无法get到这个最有解。
于是我们可以用Tarjan求scc后缩点，然后在缩点之后的分量图开始DFS。因为这个分量图是绝对无环的图，所以可以在不重复搜点下得到最优解。
比赛时 替换最优解的判断写错了，昏了头把长度的比较搞错。然后此题还有一个坑点，就是开始给的n个单词中可能会有重复，不能直接由string映射至点号。
比赛时代码修改后的通过版本：
#include<bits/stdc++.h> using namespace std;
#define IsVow(i) ((i)=='a'||(i)=='e'||(i)=='i'||(i)=='o'||(i)=='u')
typedef long long ll; const int maxn=+;
struct Edge{
int from,to;
int nxt;
};
struct word{
int vow,len;
}voc[maxn], syno[maxn];;
bool vis[maxn];
int head[maxn],tot;
Edge edges[maxn];
map<string , int > dict;
string ori[maxn];
int DFN[maxn],LOW[maxn],STACK[maxn],Belong[maxn];
int scc,dfs_no,top;
bool Instack[maxn];
vector< vector< int > > G(maxn, vector<int>() ); void addedge(int u,int v){
edges[tot].from=u;
edges[tot].to=v;
edges[tot].nxt=head[u];
head[u]=tot++;
} word make_word(string & s){
int cnt=;
word ans;
ans.len=(int) s.size();
for(auto const& i:s)
if(IsVow(i)) cnt++;
ans.vow=cnt;
return ans;
} void Tarjan(int u){
LOW[u]=DFN[u]=++dfs_no;
STACK[++top]=u;
Instack[u]=true;
for(int i=head[u];i!=-;i=edges[i].nxt){
int v=edges[i].to;
if(!DFN[v]){
Tarjan(v);
LOW[u]=min(LOW[u],LOW[v]);
}
else if(Instack[v])
LOW[u]=min(LOW[u],DFN[v]);
}
if(LOW[u]==DFN[u]){
scc++;
syno[scc]=(word){,};
while(STACK[top]!=u){
int v=STACK[top];
if(voc[v].vow < syno[scc].vow)
{
syno[scc].vow=voc[v].vow;
syno[scc].len=voc[v].len;
}
else if( syno[scc].vow == voc[v].vow)
syno[scc].len=min(syno[scc].len,voc[v].len); Instack[STACK[top]]=false;
Belong[STACK[top--]]=scc; }
Instack[u]=false;
Belong[u]=scc;
top--;
if(voc[u].vow < syno[scc].vow)
{
syno[scc].vow=voc[u].vow;
syno[scc].len=voc[u].len;
}
else if( syno[scc].vow == voc[u].vow)
syno[scc].len=min(syno[scc].len,voc[u].len);
}
} void DFS(int ind){
//cout<<ind<<":"<<syno[ind].vow<<" , "<<syno[ind].len<<endl;
if(vis[ind]){
return ;
}
vis[ind]=true; for(int i=;i<G[ind].size();++i){
int nxind=G[ind][i];
DFS(nxind);
if(syno[nxind].vow < syno[ind].vow)
{
syno[ind].vow=syno[nxind].vow;
syno[ind].len=syno[nxind].len;
}
else if( syno[nxind].vow == syno[ind].vow)
syno[ind].len=min(syno[ind].len,syno[nxind].len);
}
} int main(){
ios::sync_with_stdio(false);cin.tie();
memset(head,-,sizeof(head));
tot=;
int n,k;
cin>>n;
int TOT=;
for(int i=;i<=n;++i){
string tmp;
cin>>tmp;
ori[i]=tmp;
if(dict.count(tmp)==){
dict[tmp]=++TOT;
voc[dict[tmp]]=make_word(tmp);
}
}
cin>>k;
//cout<<"N:K:"<<n<<k<<endl;
for(int i=;i<k;++i){
string frm,to;
cin>>frm>>to;
if(dict.count(frm)==) {dict[frm]=++TOT;voc[dict[frm]]=make_word(frm);}
if(dict.count(to)==) {dict[to]=++TOT;voc[dict[to]]=make_word(to);}
addedge(dict[frm],dict[to]);
}
scc=;
for(int i=;i<=n;++i)
if(!DFN[i])
Tarjan(i);
/*
for(int i=1;i<=scc;++i)
syno[i]=(word){500000+5,5000000+5};
*/
for(int i=;i<tot;++i){
int u=edges[i].from,v=edges[i].to;
if(Belong[u]!=Belong[v]){
G[Belong[u]].push_back(Belong[v]);
}
} /*
for(int i=1;i<=TOT;++i){
int ind=Belong[i];
if(syno[ind].vow > voc[i].vow)
{
syno[ind].vow= voc[i].vow;
syno[ind].len= voc[i].len;
}
else if(syno[ind].vow == voc[i].len)
syno[ind].len= min(syno[ind].len,voc[i].len);
}
*/
ll X=,Y=;
//for(int i=1;i<=scc;++i)
// cout<<"scc "<<i<<" : "<<syno[i].vow<<" and "<<syno[i].len<<endl; for(int i=;i<=scc;++i){
int ans1,ans2;
ans1=syno[i].vow;
ans2=syno[i].len;
DFS(i);
} for(int i=;i<=n;++i){
int ans1, ans2;
ans1=syno[Belong[dict[ori[i]]]].vow;
ans2=syno[Belong[dict[ori[i]]]].len;
//DFS(Belong[i],ans1,ans2);
//cout<<Belong[i]<<endl;
X+=1ll*ans1;
Y+=1ll*ans2;
}
cout<<X<<' '<<Y<<endl;
return ;
}
后来看到别人代码，发现可以定义一个类，把优解与劣解的比较重载为<
#include <bits/stdc++.h>
using namespace std; #define IsVow(x) ((x)=='a'||(x)=='e'||(x)=='i'||(x)=='o'||(x)=='u')
typedef long long ll;
const int maxn=3e5+;
struct word{
ll vow;
ll len;
word(){}
word(ll _v,ll _l):vow(_v),len(_l){}
bool operator< (const word & tmp)const{
if(vow==tmp.vow) return len<tmp.len;
return vow<tmp.vow;
}
word operator+ (const word& tmp)const{
return word(vow+tmp.vow,len+tmp.len);
}
};
word voc[maxn],syno[maxn]; struct Edge{
int from;
int to;
int nxt;
}edges[maxn];
map<string ,int > dict;
string strcash[+];
int head[maxn],tot; int DFN[maxn],LOW[maxn],STK[maxn],BLG[maxn],top=,scc=,dfs_no=;
bool InSTK[maxn];
vector< vector< int > > G(maxn+,vector<int>() );
int vis[maxn];
void Tarjan(int u){
LOW[u]=DFN[u]=++dfs_no;
STK[top++]=u;
InSTK[u]=true;
for(int i=head[u];i!=-;i=edges[i].nxt){
int v=edges[i].to;
if(!DFN[v]){
Tarjan(v);
LOW[u]=min(LOW[u],LOW[v]);
}
else if(InSTK[v])
LOW[u]=min(LOW[u],DFN[v]);
}
if(DFN[u]==LOW[u]){
int v;
scc++;
syno[scc]=word(+,+);
do{
v=STK[--top];
InSTK[v]=false;
BLG[v]=scc;
if(voc[v]<syno[scc])
syno[scc]=voc[v];
}while(u!=v);
}
} word make_word(string X){
ll _l=1ll*X.length();
ll _v=;
for(auto const & i:X){
if(IsVow(i)) _v++;
}
return word(_v,_l);
} void AddEdge(int u,int v){
edges[tot].from=u;
edges[tot].to=v;
edges[tot].nxt=head[u];
head[u]=tot++;
} void DFS(int u){
if(vis[u]) return;
vis[u]=true;
for(auto v:G[u]){
DFS(v);
if(syno[v]<syno[u]) syno[u]=syno[v];
}
} int main(){
ios::sync_with_stdio(false);cin.tie();
int _n,_k;
int vtx_no=;
cin>>_n;
for(int i=;i<_n;++i){
string tmp;cin>>tmp;
strcash[i]=tmp;
if(dict.count(tmp)==){
dict[tmp]=++vtx_no;
voc[vtx_no]=make_word(tmp);
}
}
cin>>_k;
memset(head,-,sizeof(head));
tot=;
for(int i=;i<_k;++i){
string frm,to;cin>>frm>>to;
if(dict.count(frm)==){
dict[frm]=++vtx_no;
voc[vtx_no]=make_word(frm);
}
if(dict.count(to)==){
dict[to]=++vtx_no;
voc[vtx_no]=make_word(to);
}
AddEdge(dict[frm],dict[to]);
} top=,scc=,dfs_no=;
for(int i=;i<=vtx_no;++i){
if(!DFN[i]) Tarjan(i);
}
for(int i=;i<tot;++i){
int u=edges[i].from,v=edges[i].to;
u=BLG[u];
v=BLG[v];
if(u!=v) G[u].push_back(v);
}
//for(int i=1;i<=vtx_no;++i) cout<<"voc "<<i<<" : "<<voc[i].vow<<" , "<<voc[i].len<<endl;
//for(int i=1;i<=vtx_no;++i) cout<<strcash[i]<<":"<<i<<" belongs to "<<BLG[i]<<endl;
memset(vis,false,sizeof(vis));
//for(int i=1;i<=scc;++i) cout<<syno[i].vow<<" "<<syno[i].len<<endl;
for(int i=;i<=scc;++i){
DFS(i);
}
//puts("after DFS:");for(int i=1;i<=scc;++i) cout<<syno[i].vow<<" "<<syno[i].len<<endl;
ll __X=,__Y=;
for(int i=;i<_n;++i){
int ob=BLG[dict[strcash[i]]];
__X+=syno[ob].vow;
__Y+=syno[ob].len;
}
cout<<__X<<" "<<__Y<<endl;
return ;
}
转念一想，所谓点之间的优劣比较不就是先比元音数，元音数同则比长度吗？这不就是 STL里pair 的比较吗！？要啥结构体，要啥重载< ！？
在算导上求scc那部分，有一个定理，有向图G=<V,E>的强连通分量与其逆图~G=<V,~E>的强连通分量是重合的。（逆图，，，沉思，，，
想一想，如果不缩点，在求解搜点时从每个点搜到其最优解点的路径是一条单向路径，同一个scc内的点能到的最优解是相同的，不同的scc也可能到相同的优解，它们的终点是相同的，终点相同我们可以做逆图！！！也就是从这个解按反向搜到可以到达这个解的所有点。
在建图时，有向边方向取逆，搜索时从最优的点（用间接排序）开始搜，如此只用一遍DFS。
#include <bits/stdc++.h>
using namespace std; #define IsVow(i) ((i)=='a'||(i)=='e'||(i)=='i'||(i)=='o'||(i)=='u')
typedef long long ll; string strcash[+]; map<string ,int > dict;
pair<ll,ll > word[+];
int word_no=; struct Edge{
int to;
int nxt;
}edges[+];
int head[+],tot; int id[+];
bool vis[+]; pair<ll,ll> make_word(string X){
ll len=X.length();
ll cnt=;
for(const auto & i:X){
if(IsVow(i)) cnt++;
}
return make_pair(cnt,len);
} void AddVtx(string X){
if(dict.count(X)==){
dict[X]=++word_no;
word[word_no]=make_word(X);
}
} void AddEdge(int u,int v){
edges[tot].to=v;
edges[tot].nxt=head[u];
head[u]=tot++;
} bool cmp(int i,int j){
return word[i]<word[j];
} void DFS(int u){
if(vis[u]) return;
vis[u]=true;
for(int i=head[u];i!=-;i=edges[i].nxt){
int v=edges[i].to;
//cout<<u<<"->"<<v<<endl;
if(!vis[v]){
word[v]=word[u];
//cout<<"DFS "<<v<<endl;
DFS(v);
}
}
} int main(){
ios::sync_with_stdio(false);cin.tie(); memset(head,-,sizeof(head));
tot=; int n,k;
cin>>n;
for(int i=;i<n;++i){
cin>>strcash[i];
AddVtx(strcash[i]);
}
cin>>k;
for(int i=;i<k;++i){
string f,t;cin>>f>>t;
AddVtx(f);
AddVtx(t);
AddEdge(dict[t],dict[f]);// ~G
} for(int i=;i<=word_no;++i)
id[i]=i;
sort(id+,id++word_no,cmp);
memset(vis,false,sizeof(vis));
for(int i=;i<=word_no;++i){
DFS(id[i]);
} ll X=,Y=;
for(int i=;i<n;++i){
int _no=dict[strcash[i]];
X+=word[_no].first;
Y+=word[_no].second;
}
cout<<X<<" "<<Y<<endl;
return ;
}