P1967 货车运输树链剖分

题目描述

输入输出格式

输入格式：

第一行有两个用一个空格隔开的整数

接下来

接下来一行有一个整数 q，表示有 q 辆货车需要运货。

接下来 q 行，每行两个整数 x、y，之间用一个空格隔开，表示一辆货车需要从 x 城市运输货物到 y 城市，注意： x 不等于 y 。

输出格式：

输入输出样例

输入样例#1：复制

输出样例#1：复制

3
-1
3

说明

对于 $30\%30%的数据，0 < n < 1,000,0 < m < 10,000,0 < q< 1,0000<n<1,000,0<m<10,000,0<q<1,000；$

对于 $60\%60%的数据，0 < n < 1,000,0 < m < 50,000,0 < q< 1,0000<n<1,000,0<m<50,000,0<q<1,000；$

对于 $100\%100%的数据，0 < n < 10,000,0 < m < 50,000,0 < q< 30,000,0 ≤ z ≤ 100,0000<n<10,000,0<m<50,000,0<q<30,000,0≤z≤100,000。$

$冷静思考这就是求一个最大生成树然后在这一颗树上面求路径最短$

$然后我就被坑了发现其实并不一定是联通总是不能全过$

$后面加了这个才过的$

for ( int i = 1 ; i <= n ; i++ ) {
if ( id[i] ) continue;
dfs1 ( i, 0, 1 );
dfs2 ( i, i );
}

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <queue>
  4 #include <cmath>
  5 #include <algorithm>
  6 #include <set>
  7 #include <iostream>
  8 #include <map>
  9 #include <stack>
 10 #include <string>
 11 #include <vector>
 12 #define  pi acos(-1.0)
 13 #define  eps 1e-6
 14 #define  fi first
 15 #define  se second
 16 #define  lson l,mid,rt<<1
 17 #define  rson mid+1,r,rt<<1|1
 18 #define  rtl   rt<<1
 19 #define  rtr   rt<<1|1
 20 #define  mid   ((l+r)>>1)
 21 #define  bug         printf("******
")
 22 #define  mem(a,b)    memset(a,b,sizeof(a))
 23 #define  name2str(x) #x
 24 #define  fuck(x)     cout<<#x" = "<<x<<endl
 25 #define  f(a)        a*a
 26 #define  sf(n)       scanf("%d", &n)
 27 #define  sff(a,b)    scanf("%d %d", &a, &b)
 28 #define  sfff(a,b,c) scanf("%d %d %d", &a, &b, &c)
 29 #define  sffff(a,b,c,d) scanf("%d %d %d %d", &a, &b, &c, &d)
 30 #define  pf          prLLf
 31 #define  FRE(i,a,b)  for(i = a; i <= b; i++)
 32 #define  FREE(i,a,b) for(i = a; i >= b; i--)
 33 #define  FRL(i,a,b)  for(i = a; i < b; i++)
 34 #define  FRLL(i,a,b) for(i = a; i > b; i--)
 35 #define  FIN         freopen("in.txt","r",stdin)
 36 #define  gcd(a,b)    __gcd(a,b)
 37 #define  lowbit(x)   x&-x
 38 #pragma comment(linker, "/STACK:1024000000,1024000000")
 39 using namespace std;
 40 typedef long long  LL;
 41 typedef unsigned long long ULL;
 42 const int mod = 1e9 + 7;
 43 const int maxn = 5e4;
 44 const int INF = 0x7fffffff;
 45 const LL INFLL = 0x3f3f3f3f3f3f3f3fLL;
 46 int n, m, tot, head[maxn];
 47 int tree[maxn << 1], w1[maxn], rk[maxn];
 48 int son[maxn], id[maxn], fa[maxn], dep[maxn], sz[maxn], top[maxn], cnt;
 49 int father[maxn];
 50 struct Edge {
 51     int v, nxt, w;
 52 } edge[maxn];
 53 void init() {
 54     tot = cnt = 0;
 55     mem ( head, -1 );
 56     mem ( son, -1 );
 57 }
 58 void add ( int u, int v, int w ) {
 59     edge[tot].v = v;
 60     edge[tot].w = w;
 61     edge[tot].nxt = head[u];
 62     head[u] = tot++;
 63 }
 64 void dfs1 ( int u, int f, int deep ) {
 65     dep[u] = deep;
 66     fa[u] = f;
 67     sz[u] = 1;
 68     for ( int i = head[u]; ~i; i = edge[i].nxt ) {
 69         int v = edge[i].v;
 70         if ( v == f ) continue;
 71         w1[v] = edge[i].w;
 72         dfs1 ( v, u, deep + 1 );
 73         sz[u] += sz[v];
 74         if ( sz[son[u]] < sz[v] ) son[u] = v;
 75     }
 76 }
 77 void dfs2 ( int x, int topf ) {
 78     id[x] = ++cnt;
 79     rk[cnt] = x;
 80     top[x] = topf ;
 81     if ( son[x] == -1 ) return;
 82     dfs2 ( son[x], topf );
 83     for ( int i = head[x]; ~i; i = edge[i].nxt ) {
 84         int y = edge[i].v;
 85         if ( y == fa[x] || y == son[x] ) continue;
 86         dfs2 ( y, y );
 87     }
 88 }
 89 void build ( int l, int r, int rt ) {
 90     if ( l == r ) {
 91         tree[rt] = w1[rk[l]];
 92         return ;
 93     }
 94     build ( lson );
 95     build ( rson );
 96     tree[rt] = min ( tree[rtl], tree[rtr] );
 97 }
 98 int quary ( int L, int R, int l, int r, int rt ) {
 99     int ans = INF;
100     if ( L <= l && r <= R ) return tree[rt];
101     if ( L <= mid ) ans = min ( ans, quary ( L, R, lson ) );
102     if ( R > mid )  ans = min ( ans, quary ( L, R, rson ) );
103     return ans;
104 }
105 int qrange ( int x, int y ) {
106     int ans = INF;
107     while ( top[x] != top[y] ) {
108         if ( dep[top[x]] < dep[top[y]] ) swap ( x, y );
109         ans = min ( ans, quary ( id[top[x]], id[x], 1, n, 1 ) ) ;
110         x = fa[top[x]];
111     }
112     if ( x != y ) {
113         if ( dep[x] > dep[y] ) swap ( x, y );
114         ans = min ( ans, quary ( id[x] + 1, id[y], 1, n, 1 ) ) ;
115     }
116     return ans ;
117 }
118 struct node {
119     int u, v, w;
120 } qu[maxn];
121 int cmp ( node a, node b ) {
122     return a.w > b.w;
123 }
124 int Find ( int x ) {
125     return father[x] == x ? x : father[x] = Find ( father[x] );
126 }
127 int combine ( int x, int y ) {
128     int nx = Find ( x ), ny = Find ( y );
129     if ( nx != ny ) {
130         father[ny] = nx;
131         return 1;
132     }
133     return 0;
134 }
135 void krucal() {
136     int k = 0;
137     for ( int i = 0 ; i < m ; i++ ) {
138         if ( combine ( qu[i].u, qu[i].v ) ) {
139             k++;
140             add ( qu[i].u, qu[i].v, qu[i].w );
141             add ( qu[i].v, qu[i].u, qu[i].w );
142             if ( k == n - 1 ) break;
143         }
144     }
145 }
146 int main() {
147     scanf ( "%d%d", &n, &m );
148     init();
149     for ( int i = 0 ; i < m ; i++ ) scanf ( "%d%d%d", &qu[i].u, &qu[i].v, &qu[i].w );
150     for ( int i = 0 ; i <= n ; i++  ) father[i] = i;
151     sort ( qu, qu + m, cmp );
152     krucal();
153     for ( int i = 1 ; i <= n ; i++ ) {
154         if ( id[i] ) continue;
155         dfs1 ( i, 0, 1 );
156         dfs2 ( i, i );
157     }
158     build ( 1, n, 1 );
159     int q;
160     scanf ( "%d", &q );
161     while ( q-- ) {
162         int x, y;
163         scanf ( "%d%d", &x, &y );
164         if ( Find ( x ) == Find ( y ) ) printf ( "%d
", qrange ( x, y ) );
165         else printf ( "-1
" );
166     }
167     return 0;
168 }