P1967 货车运输【LCA】【生成树】

题目描述

A 国有

现在有

输入格式

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

接下来

接下来一行有一个整数

接下来

输出格式

输入输出样例

输入 #1

输出 #1

3
-1
3

思路

　　这题Floyd肯定是不能做的，考虑其他办法。

　　类似于静态树上求节点之间的最小边权可做。

　　显然这颗静态树的边权要尽可能的大，且注意到很多较小的重边是不用去跑的，所以考虑只把最大的边加入连通块，舍弃小的重边。

　　对于两座城市，如果不在同一个连通块内，当然是不能跑的，输出-1；

　　如果在同一个连通块内，因为边点和询问的数量级过大，显然正常的枚举是不足以胜任此题要求的。

　　这就涉及到静态树上求节点之间的最小边权问题。

　　对于这种问题，可以上树链剖分用线段树来维护，也可以用树上问题的经典解法LCA来求解。

　　在处理 f 数组的过程中维护一个 dis 数组用以表示点间最小边权值即可。

CODE

  1 #include <bits/stdc++.h>
  2 #define dbg(x) cout << #x << "=" << x << endl
  3 #define eps 1e-8
  4 #define pi acos(-1.0)
  5 
  6 using namespace std;
  7 typedef long long LL;
  8 
  9 template<class T>inline void read(T &res)
 10 {
 11     char c;T flag=1;
 12     while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0';
 13     while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;
 14 }
 15 
 16 namespace _buff {
 17     const size_t BUFF = 1 << 19;
 18     char ibuf[BUFF], *ib = ibuf, *ie = ibuf;
 19     char getc() {
 20         if (ib == ie) {
 21             ib = ibuf;
 22             ie = ibuf + fread(ibuf, 1, BUFF, stdin);
 23         }
 24         return ib == ie ? -1 : *ib++;
 25     }
 26 }
 27 
 28 int qread() {
 29     using namespace _buff;
 30     int ret = 0;
 31     bool pos = true;
 32     char c = getc();
 33     for (; (c < '0' || c > '9') && c != '-'; c = getc()) {
 34         assert(~c);
 35     }
 36     if (c == '-') {
 37         pos = false;
 38         c = getc();
 39     }
 40     for (; c >= '0' && c <= '9'; c = getc()) {
 41         ret = (ret << 3) + (ret << 1) + (c ^ 48);
 42     }
 43     return pos ? ret : -ret;
 44 }
 45 
 46 const int maxn = 1e5 + 7;
 47 
 48 int n, m, cnt;
 49 int head[maxn << 1], edge[maxn << 1], nxt[maxn << 1];
 50 int fa[maxn], f[maxn][30], depth[maxn], w[maxn << 1];
 51 int dis[maxn][30];
 52 
 53 bool vis[maxn];
 54 
 55 struct node {
 56     int u, v, w;
 57 } e[maxn << 1];
 58 
 59 bool cmp(node a, node b) {
 60     return a.w > b.w;
 61 }
 62 
 63 void BuildGraph(int u, int v, int c) {
 64     cnt++;
 65     edge[cnt] = v;
 66     nxt[cnt] = head[u];
 67     w[cnt] = c;
 68     head[u] = cnt;
 69 }
 70 
 71 int fid(int x) {
 72     return x == fa[x] ? x : fid(fa[x]);
 73 }
 74 
 75 void join() {
 76     sort(e+1, e+m+1, cmp);
 77     for ( int i = 1; i <= n; ++i ) {
 78         fa[i] = i;
 79     }
 80     for ( int i = 1; i <= m; ++i ) {
 81         int eu = fid(e[i].u), ev = fid(e[i].v);
 82         if(eu != ev) {
 83             fa[eu] = ev;
 84             BuildGraph(e[i].u, e[i].v, e[i].w);
 85             BuildGraph(e[i].v, e[i].u, e[i].w);
 86             //dbg(e[i].w);
 87         }
 88     }
 89 }
 90 
 91 void dfs(int x) {//找x和y的最近公共祖先
 92     vis[x] = 1;
 93     for ( int i = head[x]; i; i = nxt[i] ) {
 94         int y = edge[i];
 95         if(!vis[y]) {
 96             depth[y] = depth[x] + 1;
 97             f[y][0] = x;//y向上跳肯定是x
 98             dis[y][0] = w[i];
 99             dfs(y);
100         }
101     }
102 }
103 
104 int lca(int x, int y) {//查找xy的最近公共祖先
105     int ans = 0x3f3f3f3f;
106     if(fid(x) != fid(y)) {
107         return -1;
108     }
109     if(depth[x] < depth[y])
110         swap(x, y);//保证x是比y深的
111     for ( int i = 20; i >= 0; --i ) {
112         if(depth[f[x][i]] >= depth[y]) {//让x跳到和y同一层
113             ans = min(ans, dis[x][i]);
114             x = f[x][i];
115         }
116     }
117     if(x == y) {///重合态
118         return ans;
119     }
120     for ( int i = 20; i >= 0; --i ) {///不重合一起跳
121         if(f[x][i] != f[y][i]) {//父亲不同要跳一步
122             ans = min(ans, min(dis[y][i], dis[x][i]));
123             x = f[x][i], y = f[y][i];
124         }
125     }
126     ans = min(ans, min(dis[x][0], dis[y][0]));
127     return ans;///跳完最后一步
128 }
129 
130 int main()
131 {
132     scanf("%d %d", &n, &m);
133     for ( int i = 1; i <= m; ++i ) {
134         scanf("%d %d %d",&e[i].u, &e[i].v, &e[i].w);
135     }
136     join();
137     for ( int i = 1; i <= n; ++i ) {
138         if(!vis[i]) {
139             depth[i] = 1;
140             dfs(i);
141             f[i][0] = i;
142             dis[i][0] = 0x3f3f3f3f;
143         }
144     }
145     for ( int i = 1; i <= 20; ++i ) {
146         for ( int j = 1; j <= n; ++j ) {
147             f[j][i] = f[f[j][i - 1]][i - 1];
148             dis[j][i] = min(dis[j][i - 1], dis[f[j][i - 1]][i - 1]);
149             //printf("dis[%d][%d]:%d
",j,i-1,dis[j][i-1]);
150             //printf("dis[%d][%d]:%d

",fa[j][i-1],i-1,dis[fa[j][i-1]][i-1]);
151         }
152     }
153     int q;
154     cin >> q;
155     for ( int i = 1; i <= q; ++i ) {
156         int x, y;
157         scanf("%d %d", &x, & y);
158         printf("%d
",lca(x,y));
159     }
160     return 0;
161 }

View Code