二分+floyed算法

解题思路:floyed算法求所有点对最短距离，用二分算法求答案。时间复杂度：O（n^3*log(n*50000))

注意事项:

参考代码:

#include

using namespace std;

#define maxn 105

typedef long long ll;

int n;

ll q;

int dis[maxn][maxn],tu[maxn][maxn],low[maxn][maxn];

int change[maxn];//记录第i座城市改善了几次道路 

void tutodis(int day){

for(int i=1;i<=n;i++){

change[i]=day/n;

if(i<=day%n)change[i]++;

} 

for(int i=1;i<=n;i++){

for(int j=1;j<=n;j++){

dis[i][j]=max(tu[i][j]-change[i]-change[j],low[i][j]);

}

}

}

ll floyed(){

ll ret=0; 

for(int k=1;k<=n;k++){

for(int i=1;i<=n;i++){

for(int j=1;j<=n;j++){

if(dis[i][j]>dis[i][k]+dis[k][j]){

dis[i][j]=dis[i][k]+dis[k][j];

}

}

}

}

for(int i=1;i<=n;i++){

for(int j=1;j<=n;j++){

ret+=dis[i][j];

}

}

//cout<<ret<<endl;

return ret;

}

void debug(int l,int r){

cout<<"l="<<l<<",r="<<r<<",mid="<<(l+r)/2<<endl;

/*for(int i=1;i<=n;i++){

for(int j=1;j<=n;j++){

cout<<dis[i][j]<<' ';

}

cout<<endl;

}*/

}

int main(){

scanf("%d%lld",&n,&q);

for(int i=1;i<=n;i++){

for(int j=1;j<=n;j++){

scanf("%d",&tu[i][j]);

}

}

for(int i=1;i<=n;i++){

for(int j=1;j<=n;j++){

scanf("%d",&low[i][j]);

}

}

for(int i=1;i<=n;i++){

for(int j=1;j<=n;j++){

dis[i][j]=low[i][j];

}

}

if(floyed()>q){

printf("-1");

return 0; 

}

int l=0,r=n*50000;

while(l<r){

//debug(l,r);

int mid=(l+r)>>1;//l<r时，l<=mid<r 

tutodis(mid);//将第mid天的tu，赋值给dis数组最开始为第0天 

if(floyed()<=q){

r=mid;

} 

else l=mid+1;

}

printf("%d",l);

return 0;

}