当前位置: 代码迷 >> 综合 >> [JSOI2007]重要的城市(x)(洛谷1841)
  详细解决方案

[JSOI2007]重要的城市(x)(洛谷1841)

热度:62   发布时间:2023-12-14 17:22:08.0

标签:DP,最短路

题目描述

参加jsoi冬令营的同学最近发现,由于南航校内修路截断了原来通向计算中心的路,导致去的路程比原先增加了近一公里。而食堂门前施工虽然也截断了原来通向计算中心的路,却没有使路程增加,因为可以找到同样长度的路作替代。其实,问题的关键在于,路截断的地方是交通要点。

同样的情况也出现在城市间的交通中。某些城市如果出了问题,可能会引起其他很多城市的交通不便。另一些城市则影响不到别的城市的交通。jsoi冬令营的同学发现这是一个有趣的问题,于是决定研究这个问题。

他们认为这样的城市是重要的:如果一个城市c被破坏后,存在两个不同的城市a和b(a, b均不等于c),a到b的最短距离增长了(或不通),则城市c是重要的。

jsoi冬令营的同学面对着一张教练组交给他们的城市间交通图,他们希望能找出所有重要的城市。现在就请你来解决这个问题。

输入输出格式

输入格式:

第一行两个整数N,M,N为城市数,M为道路数

接下来M行,每行三个整数,表示两个城市之间的无向边,以及之间的路的长度

输出格式:

一行,按递增次序输出若干的数,表示重要的城市。

输入输出样例

输入样例#1:

4 4

1 2 1

2 3 1

4 1 2

4 3 2

输出样例#1:

2

说明

30%的数据:N≤20

60%的数据:N≤100

100%的数据:N≤200,M≤N×(N?1)/2,0<c≤10000  c即路的长度。

保证不出现重边和自环

感谢@赵昕鹏 和@qq2477259579提供程序

如果没有点的话需要输出一行

“No important cities.”

去掉引号

 

分析:

给定一张连通图,那么任意两点之间的最短路就可以确定

求哪些点会影响其余任意两点之间的最短路

满足图中不出现重边和自环

直接用Floyd跑最短路,如果通过该点中转减少了其余两点的最短路径,那么这点即为所求,实质上运用了DP和贪心的思想

Code

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define LL long long
#define mem(x,num) memset(x,num,sizeof x)
using namespace std;inline int read()
{int f=1,x=0;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;
}
const int maxn=206,maxm=20006,inf=0x3f3f3f;
int n,m,b[maxn][maxn],c[maxn][maxn],flag[maxn],Map[maxn][maxn];
int ans[maxn],cnt=0;
int main()
{mem(Map,inf);mem(b,0);mem(c,0);n=read(),m=read();rep(i,1,m){int u=read(),v=read(),w=read();Map[u][v]=Map[v][u]=w;}rep(i,1,n)Map[i][i]=0;rep(k,1,n)rep(i,1,n) rep(j,1,n)if(i!=k&&i!=j&&j!=k){if(Map[i][k]+Map[k][j]<Map[i][j]){Map[i][j]=Map[i][k]+Map[k][j];b[i][j]=1,c[i][j]=k;}else if(Map[i][k]+Map[k][j]==Map[i][j])b[i][j]=0;}rep(i,1,n)rep(j,1,n)if(i!=j)if(b[i][j]&&c[i][j]!=0&&flag[c[i][j]]==0){ans[++cnt]=c[i][j];flag[c[i][j]]=1;}if(cnt==0){printf("No important cities.\n");return 0;}sort(ans+1,ans+1+cnt);rep(i,1,cnt)printf("%d ",ans[i]);return 0;
}