蓝桥杯2022年第十三届决赛真题-环境治理（二分 floyd算法）

解题思路:
明显答案有单调性，故可以使用二分，将灰尘度看为路径长度，可以使用最短路求解。
注意事项:
注意一些限制条件,复杂度(O(n^3logm))。
参考代码:

#include

using namespace std;

#define maxx 101000

#define int long long

#define INF 0x3f3f3f3f

int n,Q,l=0,r=0;

int G[102][102];

int all[102][102];

int lim[102][102];

int check(int i)

{

  int now=(i-1)%n;

  int sum=(i-1)/n;

  for(int i=0;i<n;++i)

   for(int j=0;j<n;++j)

    all[i][j]=G[i][j];

  for(int i=0;i<n;++i)

   for(int j=0;j<n;++j)

    {if(i<=now) --all[i][j];

    if(j<=now) --all[i][j];

    all[i][j]=all[i][j]-2*sum;

    all[i][j]=max(all[i][j],lim[i][j]);

    }

   for(int k=0;k<n;++k)

    for(int i=0;i<n;++i)

     for(int j=0;j<n;++j)

      all[i][j]=min(all[i][j],all[i][k]+all[k][j]);

       int ans=0;

   for(int i=0;i<n;++i)

     for(int j=0;j<n;++j)

      ans+=all[i][j];

      if(ans<=Q) return 1;

      else return 0;

}

signed main()

{

  cin>>n>>Q;

  for(int i=0;i<n;++i)

    for(int j=0;j<n;++j)

      cin>>G[i][j];

 for(int i=0;i<n;++i)

    for(int j=0;j<n;++j)

      cin>>lim[i][j];

  for(int i=0;i<n;++i)

    for(int j=0;j<n;++j)

     r=max(r,G[i][j]-lim[i][j]);

     r=r*n;

     if(!check(r)) {cout<<"-1"; return 0;}

     if(check(l)) {cout<<"0";return 0;}

   while(l<r)

    {

      int mid=(l+r)/2;

      if(!check(mid)) l=mid+1;

      else r=mid;

    }

    cout<<l;

}