【文化之旅】解题报告

这个题是普及组少见的图论题，因为数据范围是$n\le100$，所以求最短路时可以用Floyd，比较方便。 一开始我做这个题时感觉这个排斥可以用并查集处理，因为访问过的文化不会再访问一遍，也相当于排斥了。但是题目中提到了i文化排斥j但j文化不一定排斥i，这样并查集的方法就无效了。 所以我们要在最短路上找突破口，就是对在路上经过的点所拥有的文化进行标记。加上几种判断并转移，我做的方法是复杂度$<O(N^4)$的，因此这个题$N\le100$的数据基本是能过的，~~（Floyd的常数当然是1了）当然了，if判断惩罚另说~~，实际上跑了52ms。 ------------ ### 对Floyd插点做标记的解释 因为Floyd是插点找最短路，所以每次状态都会被记录，插的点的文化就会被记录在这条路里，比如若在i，j中插入k时没有矛盾且满足最短路，那么 ```cpp 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： ```cpp #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; } ```