POJ 2570 Fiber Network(Floyd传递闭包+状态压缩)

POJ 2570 Fiber Network(Floyd传递闭包+状态压缩)

http://poj.org/problem?id=2570

题意:有一个有向图,对于有向图的每条边上有一个公司名字的集合,代表该集合内的公司能提供该边的连通服务.现在我们给你q个查询.对于每个查询a和b,你要回答有哪些公司能提供从a到b的通路服务.

分析:

又是Floyd的传递闭包思想.我们用mp[i][j]=S来表示从i到j的通路集合S中的公司能提供,那么如果我们还知道mp[j][k]=S1的话.我们能推出mp[i][k] = S&S1. 其实S的二进制形式表示公司的集合.(即公司a在S中用第0位表示)

AC代码:

#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=200+10;
int mp[maxn][maxn];
#define ALL (1<<26)-1
int main()
{
    int n;
    while(scanf("%d",&n)==1&&n)
    {
        for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            mp[i][j] = i==j?ALL:0;
        int u,v;
        while(scanf("%d%d",&u,&v)==2&&u)
        {
            int val=0;
            char str[200];
            scanf("%s",str);
            int len=strlen(str);
            for(int i=0;i<len;i++)
                val |= 1<<(str[i]-'a');
            mp[u][v] =val;
        }
        for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            mp[i][j] |=mp[i][k]&mp[k][j];
        while(scanf("%d%d",&u,&v)==2&&u)
        {
            if(mp[u][v]==0) printf("-\n");
            else
            {
                for(int i=0;i<26;i++)if(mp[u][v]&(1<<i))
                    printf("%c",'a'+i);
                printf("\n");
            }
        }
        printf("\n");
    }
    return 0;
}