洛谷 1841 [JSOI2007]重要的城市

发表于 | 更新于 | 阅读次数：
本文字数： 43 字 | 阅读时长 ≈ 1 分钟

题意简述

给你一个联通的无向简单图，请你求出有多少个点满足：删除之后，存在两点最短路增长了。
点数。（这个在某种程度上告诉了你这题用什么算法——博主注）

思路框架

一边一遍记录即珂。恕我直言，这简直是刚学就会做的水题

具体思路

设表示从到的路径上的一个关键断点（就是会让最短路边长的断点）。

先用的顺序枚举，做一个正常的。

（用矩阵记录图）

如果，说明就是断点。
如果，说明最短路不唯一，即：没有断点。

然后把所有的排序去重输出即可。由于值域很小，我们采用鸡排（鸡数排序）实现这一步排序去重，贼好写。

实现注意

  1. 没什么好注意的，题一个（然后我还调了好久，请问：我是什么
  2. 上面那个问题的答案：我是蒟蒻

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <bits/stdc++.h>
using namespace std;
namespace Flandre_Scarlet
{
	#define N 222
	#define F(i,l,r) for(int i=l;i<=r;++i)
	#define MEM(x,a) memset(x,a,sizeof(x))
	#define FK(x) MEM(x,0)
	int mp[N][N];
	int n,m;
	void Input()
	{
		scanf("%d%d",&n,&m);
		MEM(mp,0x3f);
		for(int i=1;i<=m;++i)
		{
			int a,b,c;
			scanf("%d%d%d",&a,&b,&c);
			mp[a][b]=mp[b][a]=c;//维护图
		}
	}
	
	int key[N][N];
	bool cxk[N];//怕不是这个数组名让我中了邪
	void Soviet()
	{
		F(k,1,n) F(i,1,n) F(j,1,n) if (i!=j) if (j!=k) if (i!=k)
                //一定要注意，i,j,k两两不等
		{
			if (mp[i][k]+mp[k][j]<mp[i][j])
			{
				key[i][j]=k;
				mp[i][j]=mp[i][k]+mp[k][j];
			}
			else if (mp[i][k]+mp[k][j]==mp[i][j])
			{
				key[i][j]=-1;//=-1表示没有
			}//就是上面那个转移
		}
		
		F(i,1,n) F(j,1,n)
		{
			if (~key[i][j]) cxk[key[i][j]]=1;//鸡排
		}
		
		bool flag=0;
		F(i,1,n)
		{
			if (cxk[i])
			{
				printf("%d ",i);
				flag=1;
			}
		}
		if (flag) putchar('\n');
		else puts("No important cities.");
	}
	#define Flan void
	Flan IsMyWife()
	{
		Input();
		Soviet();
	}
}
int main()
{
	Flandre_Scarlet::IsMyWife();
	return 0;
}

w