自动搬运

查看原文

来自洛谷，原作者为

	wuhan1234 **

搬运于2025-08-24 22:42:32，当前版本为作者最后更新于2023-04-10 07:53:16，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

1. 编程思路。

用二分法来求最少要经过多少天后 P 指标可以满足要求。

初始定义治理需要的最少天数 $left=0$，治理需要的最多天数可设为每个城市治理十万天，置 $right=100000\times n$，取 $left$ 和 $right$ 的中值 $mid$，计算经过 $mid$ 天治理后的 P 指标值。若 P 指标值满足要求，说明还有减少治理天数的希望，置 $right=mid-1$；若 P 指标值不满足要求，说明治理的天数不够，需要增加治理天数，置 $left=mid$。

在计算治理 $mid$ 天后的 P 指标值时，采用 Floyed 算法求任意两个城市间的最短距离（最小的灰尘度的值）。

2. 源程序。

#include <stdio.h>
#include <string.h>
int d[105][105];
int limit[105][105];
int n;
int min(int a,int b)
{
    return a<b?a:b;
}
int calc(int day)          // 计算经过day 天治理后的P指标值
{
    int tmp[105][105];     // 用于治理的辅助数组
	int i,j,k;
	for (i =0; i<n; i++)
		for (j =0; j<n; j++)
			tmp[i][j]=d[i][j];
	for (i =0; i<n; i++)
	{
		int val = day/n+(day%n>=i+1?1:0);
		for (j =0 ; j<n; j++)
		{
		    tmp[i][j]-=val;
		    if (tmp[i][j]<limit[i][j]) tmp[i][j]=limit[i][j];
		    tmp[j][i]-=val;
		    if (tmp[j][i]<limit[j][i]) tmp[j][i]=limit[j][i];
		}
	}
	for (k =0 ; k<n; k++)        // floyed 算法求最短路径
		for (i =0 ; i<n; i++)
			for (j =0 ; j<n; j++)
				tmp[i][j]=min(tmp[i][j],tmp[i][k]+tmp[k][j]);
	int res =0 ;
	for (i =0; i<n; i++)     // 计算治理后的P指标值
		for (j =0; j<n; j++)
			res+=tmp[i][j];
	return res ;
}
int main()
{
    int q;
	scanf("%d %d",&n,&q);
	int i,j;
	for (i =0; i<n; i++)
		for (j =0 ; j<n; j++)
			scanf("%d",&d[i][j]);
	for (i =0; i<n; i++)
		for (j =0 ; j<n; j++)
			scanf("%d",&limit[i][j]);
	int  left =0,right= 100000*n,ans =-1;
	while (left<=right)
	{
		int mid = (left+right)/2;
		if (calc(mid)<=q)
		{
			right= mid -1;
			ans = mid;
		}
		else
			left=mid+1;
	}
	printf("%d\n",ans);
	return 0;
}