SOJ#49. 道路规划 题解

description：

小 $G$G是 $GT$GT国的国王，他的首都是一张 $n$n个点的完全无向图，其中点 $i$i和点 $j$j之间的无向边长度为 $Dis\left[i\right]\left[j\right]$Dis[i][j]，恰好点 $i$i和点 $j$j之间的最短路长度也是 $Dis\left[i\right]\left[j\right]$Dis[i][j]。

小 $G$G想知道，最少保留多少条道路，可以使点 $i$i和点 $j$j的最短路长度还是 $Dis\left[i\right]\left[j\right]$Dis[i][j]。

$1\le Dis\left[i\right]\left[j\right]\le 10^9$1≤Dis[i][j]≤109

solution：

• $20\%$20%

n<=5边数m=n∗(n−1)/2=10

$2^{10}枚举哪⼀一些边被选了了，⽤用floyd验算$210枚举哪⼀一些边被选了了，⽤用floyd验算

• $100\%$100%

$O\left(n^3\right)枚举i,j,k⼀一开始有n^2条边，对于所有i,j，如果存在k使得dis\left[i\right]\left[k\right]+dis\left[k\right]\left[j\right]=dis\left[i\right]\left[j\right]，则i,j之间的边可以删去$O(n3)枚举i,j,k⼀一开始有n2条边，对于所有i,j，如果存在k使得dis[i][k]+dis[k][j]=dis[i][j]，则i,j之间的边可以删去

code:

#include<cstdio>
using namespace std;
int a[305][305];
int main()
{
	freopen("road.in","r",stdin);
	freopen("road.out","w",stdout); 
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			scanf("%d",&a[i][j]);
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		for(int j=i+1;j<=n;j++)
		{
			for(int k=1;k<=n;k++)
			{
				if(a[i][j]==a[i][k]+a[k][j]&&i!=k&&j!=k)
				{
					ans++;
					break;
				}
			}
		}
	}
	printf("%d\n",n*(n-1)/2-ans);
	return 0;
}