首页 > 代码库 > Codeforces Round #267 Div.2 D Fedor and Essay -- 强连通 DFS
Codeforces Round #267 Div.2 D Fedor and Essay -- 强连通 DFS
题意:给一篇文章,再给一些单词替换关系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 __int64using namespace std;#define N 100007struct Edge{ int v,next;}G[4*N],G2[4*N];string ss[N];map<string,int> 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<int> 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<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=1;i<=m;i++) { sa = "", sb = ""; cin>>sa>>sb; len = sa.length(); int cntR = 0; for(j=0;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 = 0; for(j=0;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=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,最后就能得出结果,但是我不知道这样为什么一定正确,如果你知道,那么请评论告诉我吧:)
Codeforces Round #267 Div.2 D Fedor and Essay -- 强连通 DFS
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。