HDU 5487 Difference of Languages(BFS)

这题从昨天下午2点开始做，到现在才AC了。感觉就是好多题都能想出来，就是写完后debug很长时间，才能AC,是不熟练的原因吗？但愿孰能生巧吧。

BFS转移的是两个DFA的状态，用typedef pair<int,int> pi;map<pi,pi> pres; 两步储存前后状态的链接。

附上一组测坑数据：

/*
432
4 3 1
3
0 1 a
1 2 e
2 3 w
6 3 1
5
0 1 a
1 3 e
3 5 h
*/

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <map>

#include <queue>

#include <vector>

using namespace std;

int n1,m1,k1;

int n2,m2,k2;

const int maxn = ;

int ac1[maxn];

int ac2[maxn];

map<char,int> mp1;

map<int,char> mp2;

int g1[maxn][];

int g2[maxn][];

int vis[maxn][maxn];

typedef pair<int,int> pi;

map<pi,pi> pres;

int a[maxn][maxn];

int flag = ;

struct edge

{

    int st1,st2;

};

edge ans;

void pre()

{

    for(int i=;i<=;i++)

    {

        char c = 'a'+i-;

        mp1[c]=i;

        mp2[i]=c;

    }

}

void inin()

{

    for(int i=;i<maxn;i++)

    {

        ac1[i] = ;

        ac2[i] = ;

    }

    memset(g1,-,sizeof(g1));

    memset(g2,-,sizeof(g2));

    memset(vis,,sizeof(vis));

    memset(a,,sizeof(a));

    pres.clear();

}

bool check(int u,int c)

{

    if(ac1[u]!=ac2[c])

        return false;

    return true;

}

void bfs()

{

    queue<edge> q;

    edge cur;

    q.push((edge){,});

    ans = {,};

    flag = ;

    while(!q.empty())

    {

        cur = q.front();

        q.pop();

        if(!check(cur.st1,cur.st2))

        {

            ans = cur;

            flag = ;

            return;

        }

        for(int i=;i<=;i++)

        {

            int v1 = g1[cur.st1][i];

            int v2 = g2[cur.st2][i];

            if(!vis[v1][v2])

            {

                vis[v1][v2] = ;

                q.push((edge){v1,v2});

                pres[pi(v1,v2)] = make_pair(cur.st1,cur.st2);

                a[v1][v2] = i;

            }

        }

    }

}

int main()

{

    pre();

    int t;

    int kase = ;

    cin>>t;

    while(t--)

    {

        int u,v,x;

        char c;

        inin();

        cin>>n1>>m1>>k1;

        for(int i=;i<=k1;i++)

        {

             scanf("%d",&x);

             ac1[x] = ;

        }

        for(int i=;i<=m1;i++)

        {

            scanf("%d %d %c",&u,&v,&c);

            g1[u][mp1[c]] = v;

        }

        cin>>n2>>m2>>k2;

        for(int i=;i<=k2;i++)

        {

             scanf("%d",&x);

             ac2[x] = ;

        }

        for(int i=;i<=m2;i++)

        {

            scanf("%d %d %c",&u,&v,&c);

            g2[u][mp1[c]] = v;

        }

        g1[][] = ;

        g2[][] = ;

        for(int i=;i<=n1;i++)     //下面两步是防止 最后ac1[u]和ac2[c]索引为负。

            for(int j=;j<=;j++)

            if(g1[i][j]==-) g1[i][j]=n1;

        for(int i=;i<=n2;i++)

            for(int j=;j<=;j++)

            if(g2[i][j]==-) g2[i][j]=n2;

        bfs();

        printf("Case #%d: ",++kase);

        if(!flag)

        {

            printf("0\n");

            continue;

        }

        vector<int> buffer;

        pi cur;

        while(pres.count(pi(ans.st1,ans.st2))&&(ans.st1!=||ans.st2!=))

        {

            buffer.push_back(a[ans.st1][ans.st2]);

            cur = pres[pi(ans.st1,ans.st2)];

            ans.st1 = cur.first;

            ans.st2 = cur.second;

        }

        reverse(buffer.begin(),buffer.end());

        for(int i=;i<buffer.size();i++)

        {

            printf("%c",buffer[i]+'a'-);

        }

        printf("\n");

    }

    return ;

}

/*

432

4 3 1

3

0 1 a

1 2 e

2 3 w

6 3 1

5

0 1 a

1 3 e

3 5 h

*/

秒客网

HDU 5487 Difference of Languages(BFS)

相关文章