解题思路: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;
}
0.0分
1 人评分
数组输出 (C语言代码)错误???浏览:567 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:561 |
C语言程序设计教程(第三版)课后习题6.11 (C语言代码)浏览:2081 |
printf基础练习2 (有点不明白)浏览:845 |
DNA (C语言描述,蓝桥杯)浏览:1555 |
C语言程序设计教程(第三版)课后习题8.4 (C语言代码)浏览:529 |
矩阵乘方 (C语言代码)浏览:1031 |
C语言程序设计教程(第三版)课后习题7.5 (C语言代码)浏览:686 |
C语言程序设计教程(第三版)课后习题8.9 (C语言代码)浏览:510 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:385 |