欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

T145192 【2020.8.23NOIP模拟赛】最优路线【DP&Floyd】

程序员文章站 2022-03-23 09:14:42
这道题主要思想就是修改 FloydFloydFloyd 为一个奇怪的 DPDPDP ?然后各种玄学优化+卡常,这样就能 O(n3)O(n^3)O(n3) 切掉这道题。我们定义 ansansansi,j 作为转移变量,表示 iii 号点到 jjj 号点的min⁡(最大路径长度×路径上的最大点权)\min(最大路径长度 \times 路径上的最大点权)min(最大路径长度×路径上的最大点权)可得动态转移方程:ans[i][j]=min⁡(ans[i][j],max⁡(dq2[i],max⁡(dq2[....

T145192 【2020.8.23NOIP模拟赛】最优路线【DP&Floyd】
这道题主要思想就是修改 FloydFloyd 为一个奇怪的 DPDP ?
然后各种玄学优化+卡常,这样就能 O(n3)O(n^3) 切掉这道题。

我们定义 ansansi,j 作为转移变量,表示 ii 号点到 jj 号点的
min(×)\min(最大路径长度 \times 路径上的最大点权)
可得动态转移方程:
ans[i][j]=min(ans[i][j],max(dq2[i],max(dq2[j],dq2[k]))a[i][j])ans[i][j]=\min(ans[i][j],\max(dq2[i],\max(dq2[j],dq2[k]))*a[i][j])
这里解释一下各种数组的含义:

  • popo 表示点权和边权
  • aa 是两点之间的最大边权
  • dq2dq2 是记录点权

代码解释

#pragma GCC optimize(2)
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;

long long a[501][501],ans[501][501],dq2[1000010];
long long n,m,x,y,w;

struct node
{
	long long dq,bh;
}po[1000010];
inline bool cmp(const node&a, const node&b)
{
	return a.dq<b.dq;
}
inline int read()
{
	register int X=0;
	register bool flag=1;
	register char ch=getchar();
	while(ch<'0'||ch>'9')
	 {
	   if(ch=='-')
	     flag=0; 
		 ch=getchar();
	 }
	while(ch>='0'&&ch<='9')
	 {
	    X=(X<<1)+(X<<3)+ch-'0';
		ch=getchar();
	 }
	if(flag) 
	  return X;
	return ~(X-1);
}
int main()
{
	memset(ans,0x7f,sizeof(ans));
	memset(a,0x7f,sizeof(a));
    n=read(),m=read();
    for(register int i=1; i<=n; i++)
     {
     	po[i].dq=read();
        dq2[i]=po[i].dq,po[i].bh=i,ans[i][i]=0;
     }
    sort(po+1,po+1+n,cmp);
    for(register int i=1; i<=m; i++)
     {
     	x=read(),y=read(),w=read();
     	a[x][y]=w,a[y][x]=w;
     	ans[x][y]=ans[y][x]=min(ans[x][y],a[x][y]*max(dq2[x],dq2[y]));  //初始化ans,输入一次做一次
     }
    for(register int h=1; h<=n; h++)
     {
     	long long k=po[h].bh;  //记录中转点
	    for(register int i=1; i<=n; i++)
	     for(register int j=1; j<=n; j++)
	      if(a[i][j]>max(a[i][k],a[k][j]))
	       {
	    	  a[i][j]=max(a[i][k],a[k][j]);  //先找最大边权
	    	  ans[i][j]=min(ans[i][j],max(dq2[i],max(dq2[j],dq2[k]))*a[i][j]); //DP
	       }
     }
    for(register int i=1; i<=n; i++)
     {
       for(register int j=1; j<=n; j++)
        {
      	  if(i==j)
      	    printf("0 ");
      	  else if(ans[i][j]==0)
      	    printf("-1 ");
      	  else
      	    printf("%lld ",ans[i][j]);
        }
	   printf("\n");
     }
    return 0;
}

本文地址:https://blog.csdn.net/Jackma_mayichao/article/details/108187565