洛谷 P1078 NOIP2012普及组 文化之旅 题解【图论】

点击量：1477

这个题是普及组少见的图论题，因为数据范围是\(n\le 100\)，所以求最短路时可以用Floyd，比较方便。

一开始我做这个题时感觉这个排斥可以用并查集处理，因为访问过的文化不会再访问一遍，也相当于排斥了。但是题目中提到了i文化排斥j但j文化不一定排斥i，这样并查集的方法就无效了。

所以我们要在最短路上找突破口，就是对在路上经过的点所拥有的文化进行标记。加上几种判断并转移，我做的方法是复杂度\(\le O(N^4)\)的，因此这个题\(N\le 100\)的数据基本是能过的，（Floyd的常数当然是1了）当然了，if判断惩罚另说，实际上跑了52ms。

对Floyd插点做标记的解释

因为Floyd是插点找最短路，所以每次状态都会被记录，插的点的文化就会被记录在这条路里，比如若在i，j中插入k时没有矛盾且满足最短路，那么

for(int t=1;t<=n;t++)
    used[i][j][t]=used[i][k][t]||used[k][j][t];//任意一个为1则值为1
        used[i][j][c[k]]=true;
            f[i][j]=f[i][k]+f[k][j];

将两条路上的信息合并并更新k的信息，就可以得到新路径的值。

Code：

#include<cstdio>
#include<cstring>
int min(int x,int y){return x<y?x:y;}

int c[105],n;//c数组存文化种类
int a[105][105];//a数组存是否排斥
int f[105][105];//f数组存路径长度
bool used[105][105][105];//i,j,k表示i向j的边经过了文化k
void floyd()//求最短路并判断是否排斥或重复
{
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                if(!a[c[k]][c[i]]&&!a[c[j]][c[k]]&&!used[i][k][c[j]]&&!used[k][j][c[i]]&&f[i][k]+f[k][j]<f[i][j])
                {
                    for(int t=1;t<=n;t++)
                        used[i][j][t]=used[i][k][t]||used[k][j][t];//有一个式子为真则表达式值为真
                    used[i][j][c[k]]=true;
                    f[i][j]=f[i][k]+f[k][j];
                }
}
int main()
{
    memset(f,0x3f,sizeof(f));
    int k,m,s,t,u,v,w;
    scanf("%d%d%d%d%d",&n,&k,&m,&s,&t);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&c[i]);
        f[i][i]=0;//最短路初始化
    }
    for(int i=1;i<=k;i++)
        for(int j=1;j<=k;j++)
            scanf("%d",&a[i][j]);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&u,&v,&w);
        if(!a[c[v]][c[u]]&&c[u]!=c[v])//如果两个点排斥或文化相同则不能连边
            f[u][v]=min(w,f[u][v]);//两个点之间不止一条路
        if(!a[c[u]][c[v]]&&c[u]!=c[v])
            f[v][u]=min(w,f[v][u]);
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            used[i][j][c[i]]=true;//初始化条件
            used[i][j][c[j]]=true;
        }
    floyd();
    if(f[s][t]==0x3f3f3f3f)
        printf("-1\n");//不能到达
    else
        printf("%d\n",f[s][t]);
    return 0;
}