题解 P1841 【[JSOI2007]重要的城市】
不得不说
如果我在考场上遇到这题
只能拿50分
一开始做这题的时候
哈哈哈哈哈我不在js省且07年我才两岁
什么也没想，看200的数据范围我就直接暴力（连复杂度都没算）
于是思路就是模拟
先用Floyd跑一遍所有点都没被炸掉的最短路
然后在把每一个点都炸一遍
例如炸点x
那么我再跑一遍Floyd
如果中转点遇到x
那么我就continue
再把跑完的最短路和一开始跑的最短路比较
如果当中dis[i][j]>炸点x后的dis[i][j]
那么x就是重要的城市
那么时间复杂度就是每个点都跑一个Floyd为n^4
所以代码大致是下面这样
有注释
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
const int INF=2e6;
int e[205][205],dis[205][205],m,n;//e邻接矩阵存边，dis[i][j]存i到j的最短路
priority_queue<int> q;//输出最短路时要排序
//从主程序开始阅读
bool check(int x)
{
int map[205][205];//当炸掉点x时全图最短路
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
map[i][j]=e[i][j];
}
//初始化
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
if(k==x)//如果中转点为x，那么不进行这次循环
continue;
map[i][j]=min(map[i][j],map[i][k]+map[k][j]);
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
if(map[i][j]>dis[i][j])
return true;//如果炸掉点x后的最短路比原最短路大，证明x是重要的城市
}
return false;//x不是重要的城市
}
int main()
{
cin>>n>>m;//读入边数m，点数n
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
if(i==j)
e[i][j]=dis[i][j]=0;
else
e[i][j]=dis[i][j]=INF;
}
//初始化
for(int i=1,x,y,u;i<=m;i++)
{
cin>>x>>y>>u;
e[x][y]=e[y][x]=dis[x][y]=dis[y][x]=u;
}//读入
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);//跑一遍Floyd
for(int i=1;i<=n;i++)
{
if(check(i))//检测它是不是重要城市，这个时候把目光转向check函数
q.push(-i);//懒得将q改成从小到大，直接推负数进去
}
if(q.empty()) cout<<"No important cities.";//队空代表无重要城市
else
{
while(!q.empty())
{
int v=-q.top();q.pop();
cout<<v<<' ';
}
}//输出
return 0;
}这个时候
这段代码只能过5个点
开了氧气黑科技可以过七个点
那么我们要换一种思路
（我也是想了一个晚上）
设cnt[i][j]表示i到j的最短路径条数
如果点x在i到j的最短路中出现了cnt[i][j]次
即i到j的最短路中每一条都要经过x的话
那么x一定为重要城市
OK
总结一下上面
除了任意两点之间的最短路之外
我们还需要cnt[i][j]和i到j的每一条最短路所经过的点
但是
这很难实现
其实是我不会
思考一下
第一点
在松弛中
i到j的路径中
如果通过点k可以使路径长度缩小
那么
i到j的最短路一定要经过k
第二点
如果松弛中发现e[i][j]==e[i][k]+e[k][j]
那么一定会不止一条最短路
这个时候我们以前发现经过的点都不一定走
所以
题目的思路就变成了这样
在松弛中
if(e[i][j]>e[i][k]+e[k][j])
{
e[i][j]=e[i][k]+e[k][j]; city[i][j]=k;//k是重要城市
}如果发现i到j不止一条最短路
那么从city[i][j]中移除点k
最后我们还有两步
一是题目要求的排序
二是我们算法的判重
那么两者综合
我们选用桶排序
定义一个bool形的数组
循环i至n和j至n
ans[city[i][j]]=true;
输出时
if(ans[i])
cout<<i;所以整道题的思路就是这样了
代码我就不打注释了
觉得我写的好记得给个赞哦~
下为代码
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
const int INF=2e6;
int e[205][205],city[205][205],m,n;
bool ans[205],cs;
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(i!=j)
e[i][j]=INF;
for(int i=1,x,y,u;i<=m;i++)
{
cin>>x>>y>>u;
e[x][y]=e[y][x]=u;
}
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
if(i!=k)
for(int j=1;j<=n;j++)
if(i!=j&&j!=k)
{
if(e[i][j]>e[i][k]+e[k][j])
{
e[i][j]=e[i][k]+e[k][j];
city[i][j]=k;
}
else if(e[i][j]==e[i][k]+e[k][j])
city[i][j]=-1;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(city[i][j]!=-1)
ans[city[i][j]]=true;
for(int i=1;i<=n;i++)
if(ans[i])
cout<<i<<' ',cs=true;
if(!cs)
cout<<"No important cities.";
return 0;
}