简答题 偏难
#23485

货车运输 【问题描述】 A 国有 n 座城市,编号从 1 到 n,城市之间有 m 条双向道路。每一条道路对车辆都有重量限制,简称限重。现在有 q 辆货车在运输货…

货车运输

【问题描述】

A 国有 n 座城市,编号从 1 到 n,城市之间有 m 条双向道路。每一条道路对车辆都有重量限制,简称限重。现在有 q 辆货车在运输货物,司机们想知道每辆车在不超过车辆限重的情况下,最多能运多重的货物。

【输入】

输入文件名为 truck.in。

输入文件第一行有两个用一个空格隔开的整数 n,m,表示 A 国有 n 座城市和 m 条道路。

接下来 m 行每行 3 个整数 x、y、z,每两个整数之间用一个空格隔开,表示从 x 号城市到 y 号城市有一条限重为 z 的道路。注意:x 不等于 y,两座城市之间可能有多条道路。

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

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

【输出】

输出文件名为 truck.out。

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

【输入输出样例】

【数据说明】

对于 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。

未登录也能判分,登录后才会记录
答案与解析
正确答案:<p style="text-align: left;">#include&lt;iostream&gt;</p><p style="text-align: left;">#include&lt;cstdio&gt;</p><p style="text-align: left;">#include&lt;cstring&gt;</p><p style="text-align: left;">#include&lt;cmath&gt;</p><p style="text-align: left;">#include&lt;algorithm&gt;</p><p style="text-align: left;">#define _for(i,a,b) for (int i=a;i&lt;=b;i++)</p><p style="text-align: left;">using namespace std;</p><p style="text-align: left;">const int N=1e4+5,M=5e4+5;//g[u][j]表示u到f[u][j]这条链上边权的最大值。</p><p style="text-align: left;">int n,m,fa[N],h[N],e[M],ne[M],w[M],idx,d[N],f[N][20],g[N][20];</p><p style="text-align: left;">struct node{</p><p style="text-align: left;">    int a,b,w;</p><p style="text-align: left;">    bool operator &lt;(const node&amp; rhs) const{</p><p style="text-align: left;">        return w&gt;rhs.w;</p><p style="text-align: left;">    }</p><p style="text-align: left;">}a[M];</p><p style="text-align: left;">inline void c_plus(){//可以忽略</p><p style="text-align: left;">    ios::sync_with_stdio(false);</p><p style="text-align: left;">    cin.tie(0);</p><p style="text-align: left;">    cout.tie(0);</p><p style="text-align: left;">}</p><p style="text-align: left;">inline void init_list(){//单链表</p><p style="text-align: left;">    idx=0;</p><p style="text-align: left;">    memset(h,-1,sizeof(h));</p><p style="text-align: left;">}</p><p style="text-align: left;">inline void add(int a,int b,int c){//同上</p><p style="text-align: left;">    e[idx]=b;</p><p style="text-align: left;">    w[idx]=c;</p><p style="text-align: left;">    ne[idx]=h[a];</p><p style="text-align: left;">    h[a]=idx++;</p><p style="text-align: left;">}</p><p style="text-align: left;">inline void init_set(){//并查集</p><p style="text-align: left;">    _for(i,1,n){</p><p style="text-align: left;">        fa[i]=i;</p><p style="text-align: left;">    }</p><p style="text-align: left;">}</p><p style="text-align: left;">int get(int x){//同上</p><p style="text-align: left;">    if (x==fa[x]){</p><p style="text-align: left;">        return x;</p><p style="text-align: left;">    }</p><p style="text-align: left;">    return fa[x]=get(fa[x]);</p><p style="text-align: left;">}</p><p style="text-align: left;">void kruskal(){//kruskal算法</p><p style="text-align: left;">    sort(a+1,a+m+1);</p><p style="text-align: left;">    _for(i,1,m){</p><p style="text-align: left;">        int x=get(a[i].a);</p><p style="text-align: left;">        int y=get(a[i].b);</p><p style="text-align: left;">        if (x!=y){</p><p style="text-align: left;">            fa[y]=x;</p><p style="text-align: left;">            add(a[i].a,a[i].b,a[i].w);</p><p style="text-align: left;">            add(a[i].b,a[i].a,a[i].w);</p><p style="text-align: left;">        }</p><p style="text-align: left;">    }</p><p style="text-align: left;">}</p><p style="text-align: left;">void dfs(int u){</p><p style="text-align: left;"><span style="white-space:pre"> </span>d[u]=d[f[u][0]]+1;</p><p style="text-align: left;"><span style="white-space:pre"> </span>for (int i=h[u];i!=-1;i=ne[i]){</p><p style="text-align: left;"><span style="white-space:pre"> </span>int j=e[i];</p><p style="text-align: left;"><span style="white-space:pre"> </span>if (j==f[u][0]){</p><p style="text-align: left;"><span style="white-space:pre"> </span>continue;</p><p style="text-align: left;">        }</p><p style="text-align: left;"><span style="white-space:pre"> </span>f[j][0]=u;</p><p style="text-align: left;">        g[j][0]=w[i];//我们需要在dfs函数里给g[v][0]赋初值,为每个结点v上面那条边的权值。</p><p style="text-align: left;"><span style="white-space:pre"> </span>dfs(j);</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;">}</p><p style="text-align: left;">int lca(int x,int y){//LCA算法</p><p style="text-align: left;">    if (get(x)!=get(y)){//判断是否合法,在不在一个连通块内</p><p style="text-align: left;">        return -1;</p><p style="text-align: left;">    }</p><p style="text-align: left;"><span style="white-space:pre"> </span>if (d[x]&lt;d[y]){</p><p style="text-align: left;"><span style="white-space:pre"> </span>swap(x,y);</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>int k=(int)(log2(d[x])),ans=0x7fffffff;//ans存答案</p><p style="text-align: left;"><span style="white-space:pre"> </span>for (int j=k;j&gt;=0;j--){</p><p style="text-align: left;"><span style="white-space:pre"> </span>if (d[f[x][j]]&gt;=d[y]){</p><p style="text-align: left;">            ans=min(ans,g[x][j]);//维护最大值</p><p style="text-align: left;"><span style="white-space:pre"> </span>x=f[x][j];</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>if (x==y){/</p><p style="text-align: left;"><span style="white-space:pre"> </span>goto output;</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>k=(int)(log2(d[x]));</p><p style="text-align: left;"><span style="white-space:pre"> </span>for (int j=k;j&gt;=0;j--){</p><p style="text-align: left;"><span style="white-space:pre"> </span>if (f[x][j]!=f[y][j]){</p><p style="text-align: left;">            ans=min(ans,min(g[x][j],g[y][j]));//维护最大值</p><p style="text-align: left;"><span style="white-space:pre"> </span>x=f[x][j];</p><p style="text-align: left;"><span style="white-space:pre"> </span>y=f[y][j];</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;">    ans=min(ans,min(g[x][0],g[y][0]));//最后还差一步才到达lca,因此还要算上最后两条边的最大值</p><p style="text-align: left;">    output:</p><p style="text-align: left;"><span style="white-space:pre"> </span>return ans;</p><p style="text-align: left;">}</p><p style="text-align: left;">int main(){</p><p style="text-align: left;">    freopen("truck.in","r",stdin);</p><p style="text-align: left;">    freopen("truck.out","w",stdout);</p><p style="text-align: left;">    c_plus();</p><p style="text-align: left;">    int q,x,y;</p><p style="text-align: left;">    cin&gt;&gt;n&gt;&gt;m;</p><p style="text-align: left;">    init_list();</p><p style="text-align: left;">    init_set();</p><p style="text-align: left;">    _for(i,1,m){</p><p style="text-align: left;">        cin&gt;&gt;a[i].a&gt;&gt;a[i].b&gt;&gt;a[i].w;</p><p style="text-align: left;">    }</p><p style="text-align: left;">    kruskal();</p><p style="text-align: left;">    _for(i,1,n){</p><p style="text-align: left;">        if (d[i]==0){//每个连通块都要遍历</p><p style="text-align: left;">            dfs(i);</p><p style="text-align: left;">        }</p><p style="text-align: left;">    }</p><p style="text-align: left;">    for (int j=1;(1&lt;&lt;j)&lt;=n;j++){</p><p style="text-align: left;">        _for(i,1,n){</p><p style="text-align: left;">            f[i][j]=f[f[i][j-1]][j-1];</p><p style="text-align: left;">            g[i][j]=min(g[i][j-1],g[f[i][j-1]][j-1]);//通过动态规划计算g数组剩余的值。</p><p style="text-align: left;">//转移方程很显然,就是把从i到f[i][j]这条链,拆成i到f[i][j-1]和f[i][j-1]到f[i][j]两条链,</p><p style="text-align: left;">//然后取最大值</p><p style="text-align: left;">        }</p><p style="text-align: left;">    }</p><p style="text-align: left;">    cin&gt;&gt;q;</p><p style="text-align: left;">    while (q--){</p><p style="text-align: left;">        cin&gt;&gt;x&gt;&gt;y;</p><p style="text-align: left;">        cout&lt;&lt;lca(x,y)&lt;&lt;endl;</p><p style="text-align: left;">    }</p><p style="text-align: left;">    return 0;</p><p style="text-align: left;">}</p>
这道题暂未补解析。