[loj539]旅游路线

考虑枚举加油的位置，当确定某次在第$i$个位置加油后，且下一次到$j$加油，那么$i$到$j$必然会选择不超过$c_{i}$条边且最长的路径，记作$d_{i,j}$

如果能求出$d_{i,j}$，再设$f_{q,i}$表示$q$元（恰好用完）从$i$出发的最长路，枚举$i$之后那一次加油点即可转移，由于$q\le n^{2}$，因此这里的复杂度为$o(n^{4})$

接下来，对其求一次前缀max再二分，即可对询问做到$o(t\log_{2}q)$的复杂度

现在还有一个问题，考虑如何预处理最开始的$d_{i,j}$

倍增，求出从$i$出发，走不超过$2^{k}$次走到$j$的最长路，通过枚举走$2^{k-1}$时的点来转移，可以做到$o(n^{3}\log_{2}c_{i})$

类似的，再对每一个点$i$做一次dp，同样枚举中专点转移即可，时间复杂度也是$o(n^{3}\log_{2}c_{i})$

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 #define N 105

 4 #define M 1005

 5 #define K 100005

 6 struct ji{

 7     int nex,to,len;

 8 }edge[M];

 9 struct qu{

10     int s,q,d;

11 }q[K];

12 int E,n,m,t,x,y,z,head[N],p[N],c[N],g[21][N][N],ff[N],f[N][N],ans[N*N][N];

13 void add(int x,int y,int z){

14     edge[E].nex=head[x];

15     edge[E].to=y;

16     edge[E].len=z;

17     head[x]=E++;

18 }

19 int main(){

20     scanf("%d%d%d%d",&n,&m,&c[0],&t);

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

22         scanf("%d%d",&p[i],&c[i]);

23         c[i]=min(c[i],c[0]);

24         if (!p[i]){

25             printf("orz");

26             return 0;

27         }

28     }

29     memset(head,-1,sizeof(head));

30     for(int i=1;i<=m;i++){

31         scanf("%d%d%d",&x,&y,&z);

32         add(x,y,z);

33     }

34     memset(g,-0x3f,sizeof(g));

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

36         g[0][i][i]=0;

37         for(int j=head[i];j!=-1;j=edge[j].nex)g[0][i][edge[j].to]=max(g[0][i][edge[j].to],edge[j].len);

38     }

39     for(int i=1;i<=20;i++)

40         for(int x=1;x<=n;x++)

41             for(int y=1;y<=n;y++)

42                 for(int z=1;z<=n;z++)

43                     g[i][x][y]=max(g[i][x][y],g[i-1][x][z]+g[i-1][z][y]);

44     memset(f,-1,sizeof(f));

45     for(int i=1;i<=n;i++)f[i][i]=0;

46     for(int x=1;x<=n;x++)

47         for(int i=0;i<=20;i++)

48             if (c[x]&(1<<i)){

49                 for(int y=1;y<=n;y++)ff[y]=f[x][y];

50                 for(int y=1;y<=n;y++)

51                     for(int z=1;z<=n;z++)

52                         if (ff[z]!=-1)f[x][y]=max(f[x][y],ff[z]+g[i][z][y]);

53             }

54     memset(ans,-0x3f,sizeof(ans));

55     for(int i=1;i<=n;i++)ans[0][i]=0;

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

57         for(int x=1;x<=n;x++)

58             if (p[x]<=i)

59                 for(int y=1;y<=n;y++)

60                     if (f[x][y]!=-1)ans[i][x]=max(ans[i][x],ans[i-p[x]][y]+f[x][y]);//o(n^4)

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

62         for(int j=1;j<=n;j++)ans[i][j]=max(ans[i][j],ans[i-1][j]);

63     for(int i=1;i<=t;i++){

64         scanf("%d%d%d",&x,&y,&z);

65         if (ans[y][x]<z)printf("-1\n");

66         else{

67             int l=0,r=y;

68             while (l<r){

69                 int mid=(l+r>>1);

70                 if (ans[mid][x]>=z)r=mid;

71                 else l=mid+1;

72             }

73             printf("%d\n",y-l);

74         }

75     }

76     return 0;

77 }

巴特西

[loj539]旅游路线

最新文章

热门文章