首页 > 代码库 > 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;}
View Code

 

还有一种做法就是反向建图,然后sort一下,优先从最优的开始dfs,最后就能得出结果,但是我不知道这样为什么一定正确,如果你知道,那么请评论告诉我吧:)

Codeforces Round #267 Div.2 D Fedor and Essay -- 强连通 DFS