noip2013 貨車運輸 （求解生成樹路徑上的最短邊：倍增求最近共祖先+最大生成樹Kruskal）

P1843貨車運輸 Accepted 标簽： NOIP提高組2013

描述

A 國有 n 座城市，編号從 1 到 n，城市之間有 m 條雙向道路。每一條道路對車輛都有重量限制，簡稱限重。現在有 q 輛貨車在運輸貨物，司機們想知道每輛車在不超過車輛限重的情況下，最多能運多重的貨物。

格式

輸入格式

第一行有兩個用一個空格隔開的整數 n，m，表示 A 國有 n 座城市和 m 條道路。

接下來 m 行每行 3 個整數 x、y、z，每兩個整數之間用一個空格隔開，表示從 x 号城市到 y 号城市有一條限重為 z 的道路。注意：x 不等于 y，兩座城市之間可能有多條道路。

接下來一行有一個整數 q，表示有 q 輛貨車需要運貨。

接下來 q 行，每行兩個整數 x、y，之間用一個空格隔開，表示一輛貨車需要從 x 城市運輸貨物到 y 城市，注意：x 不等于 y。

輸出格式

輸出共有 q 行，每行一個整數，表示對于每一輛貨車，它的最大載重是多少。如果貨車不能到達目的地，輸出-1。

樣例1

樣例輸入1[複制]

4 3 
1 2 4 
2 3 3 
3 1 1 
3
1 3 
1 4 
1 3
      

樣例輸出1[複制]

3
-1
3
      

限制

每個測試點1s。

提示

對于 30%的資料，0 < n < 1,000，0 < m < 10,000，0 < q < 1,000； 

對于 60%的資料，0 < n < 1,000，0 < m < 50,000，0 < q < 1,000； 

對于 100%的資料，0 < n < 10,000，0 < m < 50,000，0 < q < 30,000，0 ≤ z ≤ 100,000。

來源

NOIP 2013 提高組 Day 1

解析：基本思路：kruskal求最大生成樹，那麼從 x 到 y 的最大運輸量即為，在最大生成樹上，從 x 到 y 得這條路徑上的最短邊。

           1.kruskal求最大生成樹，這個就不講了，網上資料很多，和求最小生成樹是一樣的思路。

           2.求解在最大生成樹上，從 x 到 y 的路徑上的的最短邊。

              這裡采用倍增的方法，up[i][j]表示從 i 向上走2^j步所到達的點，up[i][0]即為 i 的父節點，len[i][j]即為從 i 向上走2^j步的路徑上的最短邊。

              deep[i]記錄 i 在樹中的深度。

              ①求解 x 與 y 的最近公共祖先。

                  若 x 與 y 的深度不一緻，這裡假設 x 更深，那麼就把 x 通過倍增向上移動deep[x]-deep[y]步，使得 x 與 y的深度相等。之後，就把 x 與 y向上同等倍增移動，直到彙聚一點，該點即為x與y的最近公共祖先。

              ②在上述求最近公共祖先的過程中，動态記錄下最短邊長度即可。

代碼：

#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#define ms(a) memset(a,0,sizeof(a))
using namespace std;

const int maxn=1e4;
const int maxm=5e4;
int n,m;
int f[maxn+10],deep[maxn+10];
int up[maxn+10][15+3],len[maxn+10][15+3];
struct tnode{
	int x,y,z;
}q[maxm+10];
struct node{
	int d,w;
	node *next;
}*h[maxn+10];

int getin()
{
  int ans=0;char tmp;
  while(!isdigit(tmp=getchar()));
  do ans=(ans<<3)+(ans<<1)+tmp-'0';
  while(isdigit(tmp=getchar()));
  return ans;
}

bool cmp_q(tnode a,tnode b)
{
  return a.z>b.z;
}

int find(int x)
{
  if(f[x]==x)return x;
  return f[x]=find(f[x]);
}

void add(int u,int v,int w)
{
  node *p=new node;
  (*p).d=v,(*p).w=w;
  (*p).next=h[u],h[u]=p;
}

void build_tree(int rt)
{
  int i,j,k; node *p;
  for(p=h[rt];p;p=(*p).next)
    {
      if((*p).d==up[rt][0])continue;
      k=(*p).d,deep[k]=deep[rt]+1;
      up[k][0]=rt,len[k][0]=(*p).w;
      for(i=1;i<=15;i++)
        {
          j=up[k][i-1];
          if(up[j][i-1]==0)break;
          up[k][i]=up[j][i-1];
          len[k][i]=min(len[k][i-1],len[j][i-1]);
		}
	  build_tree(k);
	}
}

int get(int x,int y)
{
  int t,i,ans=1e5;
  if(deep[x]<deep[y])swap(x,y);
  t=deep[x]-deep[y];
  for(i=0;i<=15;i++)if((1<<i)&t)
    {
      ans=min(ans,len[x][i]);
	  x=up[x][i]; 
	}
  for(i=15;i>=0;i--)
    if(up[x][i]!=up[y][i])
	  {
	    ans=min(ans,len[x][i]);
	    ans=min(ans,len[y][i]);
	    x=up[x][i],y=up[y][i];
	  }
  if(x==y)return ans;
  return min(ans,min(len[x][0],len[y][0]));
}

int main()
{
  int i,s,x,y;
  n=getin(),m=getin();
  for(i=1;i<=m;i++)
    {
      q[i].x=getin(),q[i].y=getin();
      q[i].z=getin();
	}
  sort(q+1,q+1+m,cmp_q);
  for(i=1;i<=n;i++)f[i]=i,h[i]=NULL;
  for(s=0,i=1;i<=m;i++)
    {
      x=find(q[i].x),y=find(q[i].y);
      if(x==y)continue;
      f[x]=y,s++;
      add(q[i].x,q[i].y,q[i].z);
      add(q[i].y,q[i].x,q[i].z);
	  if(s==n-1)break;
	}
  ms(up),ms(len),ms(deep);
  for(i=1;i<=n;i++)if(deep[i]==0)build_tree(i);
  for(s=getin(),i=1;i<=s;i++)
    {
      x=getin(),y=getin();
      if(find(x)!=find(y))printf("-1\n");
	  else printf("%d\n",get(x,y));
	}
  return 0;
}