TYVJ P1577 泥泞的道路

题目链接：http://www.tyvj.cn/p/1577#

P1577 泥泞的道路

时间: 1000ms / 空间: 131072KiB / Java类名: Main

描述

公园中有n个景点，编号1~n，并由m条双向道路相连。由于昨天下雨，导致公园中的马路泥泞不堪，每条道路都有一个泥泞程度w。现有Q个游客依次向你求助，想从景点X走到景点Y，他希望找到一条道路，使得经过道路泥泞程度的最大值尽量小。你能设计一个在线算法，帮他们找到方案吗？

输入格式

第一行两个正整数n和m，表示景点数和道路数。
随后m行每行三个正整数x、y、w，用来描述一条道路，它连接x和y景点并且泥泞程度为w。
随后Q行，每行四个参数p1、p2、q1、q2，含义如下：
设数列Si表示你求得的第i个询问的结果（s0=1），则对于第i个询问：
X=(Si-1+p1)*p2 mod n + 1;
Y=(si-1+q1)*q2 mod n + 1;

输出格式

请对于每个询问，输出结果，即Si。

测试样例1

输入

4 4
1 2 2
2 3 1
1 3 3
3 4 5
2
3 1 0 2
1 1 2 1

输出

2
5
说明：第一个询问是{x=1，y=3}，第二个询问是{x=4，y=1}。

备注

对于30%的数据，n<=1000，m<=3000，Q<=1000；
对于100%的数据，n<=100000，m<=300000，Q<=100000；
对于100%的数据，0<=p1、p2、q1、q2<n，w<300000。

在线问。两点之间的边的最大值最小。

先MST构造一棵树。

然后LCA询问，可是这道题爆栈，加栈也没用，还有这种LCA也第一次写，WA不少。

DFS变成BFS应该可以A了

  1 #pragma comment(linker, "/STACK:1024000000,1024000000")

  2 #include<iostream>

  3 #include<algorithm>

  4 #include<cmath>

  5 #include<string.h>

  6 #include<vector>

  7 #include<stdio.h>

  8 

  9 

 10 using namespace std;

 11 #define N 623456

 12 struct node

 13 {

 14     int x,y,z;

 15 }a[N];

 16 

 17 int f[N];

 18 

 19 int find(int x)

 20 {

 21     if (f[x]!=x) f[x]=find(f[x]);

 22     return f[x];

 23 }

 24 

 25 struct nod

 26 {

 27   int v,c,next;

 28 }e[N<<];

 29 int head[N],tot;

 30 

 31 int cmp(node a,node b)

 32 {

 33     return a.z<b.z;

 34 }

 35 

 36 void add(int u,int v,int z)

 37 {

 38     e[tot].v=v;

 39     e[tot].c=z;

 40     e[tot].next=head[u];

 41     head[u]=tot++;

 42 }

 43 int dp[N][],dep[N];

 44 int dpmax[N][];

 45 

 46 void dfs(int u,int fa,int t,int z)

 47 {

 48     dp[u][]=fa;

 49     dpmax[u][]=z;

 50     dep[u]=t;

 51     for (int i=head[u];i!=-;i=e[i].next)

 52     {

 53         int v=e[i].v;

 54         if (v==fa) continue;

 55         //dpmax[v][0]=e[i].c;

 56         dfs(v,u,t+,e[i].c);

 57     }

 58 }

 59 

 60 int lca(int u,int v)

 61 {

 62     if (dep[u]<dep[v]) swap(u,v);

 63     int dif=dep[u]-dep[v];

 64 

 65     int res=;

 66     for (int i=;i<;i++)

 67     if ((dif>>i)&) res=max(res,dpmax[u][i]),u=dp[u][i];

 68 

 69     if (u==v) return res;

 70     for (int i=;i>=;i--)

 71     if (dp[u][i]!=dp[v][i]) {

 72             res=max(res,dpmax[u][i]),

 73             res=max(res,dpmax[v][i]);

 74             u=dp[u][i],v=dp[v][i];

 75     }

 76     if (u!=v) res=max(res,dpmax[u][]),res=max(res,dpmax[v][]);

 77     return res;

 78 }

 79 inline int read()

 80 {

 81     int x=,f=;char ch=getchar();

 82     while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

 83     while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

 84     return x*f;

 85 }

 86 int main()

 87 {

 88     int n,m;

 89   //  freopen("input.txt","r",stdin);

 90     memset(head,-,sizeof(head));

 91     tot=;

 92    // scanf("%d%d",&n,&m);

 93     n=read();

 94     m=read();

 95     for (int i=;i<=m;i++) //scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);

 96     a[i].x=read(),a[i].y=read(),a[i].z=read();

 97 

 98     sort(a+,a+m+,cmp);

 99     for (int i=;i<=n;i++) f[i]=i;

     for (int i=;i<=m;i++)

     {

         int x=find(a[i].x);

         int y=find(a[i].y);

         if (x!=y)

         {

             add(a[i].x,a[i].y,a[i].z);

             add(a[i].y,a[i].x,a[i].z);

             f[x]=y;

         }

     }

     dfs(,,,);

     //for (int i=1;i<=n;i++) cout<<dpmax[i][0]<<endl;

 

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

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

     dpmax[j][i]=max(dpmax[j][i-],dpmax[dp[j][i-]][i-]);

     dp[j][i]=dp[dp[j][i-]][i-];

     }

 

     int Q;

    // scanf("%d",&Q);

     Q=read();

     int ans=;

     while (Q--)

     {

         int p1,p2,q1,q2;

        // scanf("%d%d%d%d",&p1,&p2,&q1,&q2);

         p1=read(),p2=read(),q1=read(),q2=read();

         int x=1ll*(ans+p1)*p2%n+;

         int y=1ll*(ans+q1)*q2%n+;

       //  cout<<x<<y<<endl;

         ans=lca(x,y);

         printf("%d\n",ans);

     }

     return ;

 }

巴特西

TYVJ P1577 泥泞的道路

描述

输入格式

输出格式

测试样例1

输入

输出

备注

最新文章

热门文章