货车运输

【题目描述】

A国有n座城市，编号从1~n，这些城市之间有m条双向道路，每一条道路对车辆都有限重。

现有q辆货车在运输货物，询问在不超过车辆限重的情况下，每辆车最多能运输多重的货物。

【输入描述】

第一行输入两个整数n、m，表示A国有n座城市和m条道路；

接下来m行，每行输入三个整数x、y、z，表示从x号城市到y号城市存在一条限重为z的道路；

接下来一行输入一个整数q，表示有q辆货车需要运输货物；

接下来q行，每行输入两个整数x、y，表示一辆货车需要从x城市运输货物到y城市。

【输出描述】

输出q行，每行包含一个整数，表示对于每一辆货车，它的最大载重是多少，如果货车不能到达目的地，输出-1。

【样例输入】

4 3

1 2 4

2 3 3

3 1 1

1 3

1 4

1 3

【样例输出】

-1

【数据范围及提示】

对于30%的数据，0 < n < 1000，0 < m < 10000，0 < q < 1000；

对于60%的数据，0 < n < 1000，0 < m < 50000，0 < q < 1000；

对于100%的数据，0 < n < 10000，0 < m < 50000，0 < q < 30000，0 ≤ z ≤ 100000。

源代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct Node1
{
    int X,Y,S;
}Map[50001];
struct Node2
{
    int S,To,Next;
}Edge[20001];
int m,n,Sum,Num(0),Number(0),F[10001],Head[10001],Deep[10001],f[10001][17],i[10001][17];
void Add(int t1,int t2,int t) //边表。
{
    Edge[++Num].S=t;
    Edge[Num].To=t2;
    Edge[Num].Next=Head[t1];
    Head[t1]=Num;
}
int Find(int t) //并查集。
{
    if (!F[t])
      return t;
    return F[t]=Find(F[t]);
}
bool Rule(Node1 t1,Node1 t2)
{
    return t1.S>t2.S;
}
void DFS(int T,int S) //DFS预处理。
{
    for (int a=Head[T];a;a=Edge[a].Next)
    {
        int t=Edge[a].To;
        if (!Deep[t]&&t!=1) //特判。
        {
            Deep[t]=Deep[T]+1;
            f[t][0]=T;
            i[t][0]=Edge[a].S; //类似于f[][]，存储往上的最大路。
            DFS(t,S+1);
        }
    }
}
void Get_Father() //统计父系。
{
    for (int b=1;b<=16;b++)
      for (int a=1;a<=n;a++)
      {
        f[a][b]=f[f[a][b-1]][b-1];
        i[a][b]=min(i[a][b-1],i[f[a][b-1]][b-1]);
      }
}
int Get_Same(int T,int S) //调整深度。
{
    for (int a=0;a<=16;a++)
      if ((1<<a)&S) //神奇的位运算比较大小。
      {
        Sum=min(Sum,i[T][a]);
        T=f[T][a];
      }
    return T;
}
int LCA(int t1,int t2) //倍增LCA。
{
    if ((t1!=1&&!Deep[t1])||(t2!=1&&!Deep[t2])) //特判，此节点不在树中。
      return -1;
    Sum=1000000000;
    if (Deep[t1]<Deep[t2])
      swap(t1,t2);
    t1=Get_Same(t1,Deep[t1]-Deep[t2]);
    if (t1==t2) //根节点。
      return Sum;
    for (int a=16;a>=0;a--)
      if (f[t1][a]!=f[t2][a])
      {
        Sum=min(Sum,min(i[t1][a],i[t2][a])); //一样在更新。
        t1=f[t1][a];
        t2=f[t2][a];
      }
    return min(Sum,min(i[t1][0],i[t2][0]));
}
int main() //最大生成树+倍增LCA，蒟蒻搞了一上午！
{
    memset(i,0x3f,sizeof(i));
    scanf("%d%d",&n,&m);
    for (int a=0;a<m;a++)
      scanf("%d%d%d",&Map[a].X,&Map[a].Y,&Map[a].S);
    sort(Map,Map+m,Rule);
    for (int a=0;a<m;a++) //Kruskal算法。
    {
        int t1=Find(Map[a].X);
        int t2=Find(Map[a].Y);
        if (t1!=t2)
        {
            Add(Map[a].X,Map[a].Y,Map[a].S);
            Add(Map[a].Y,Map[a].X,Map[a].S);
            F[t2]=t1;
            Number++;
            if (Number==n-1)
              break;
        }
    }
    DFS(1,0); //倍增LCA。
    Get_Father();
    scanf("%d",&m);
    for (int a=0;a<m;a++)
    {
        int t1,t2;
        scanf("%d%d",&t1,&t2);
        printf("%d
",LCA(t1,t2));
    }
    return 0;
}