首页 > 其他 > 详细

Berland Beauty

时间:2020-02-07 21:04:03      阅读:58      评论:0      收藏:0      [点我收藏+]

F - Berland Beauty

因为这道题的 n 只有5000的范围,所以直接暴力用\(O(n^2)\)的写法也是可以的,只需要先 dfs 一遍,把每一条边都赋为其可能达到的最大值,然后再把所有的数据再 check 一遍即可。当然这道题也可以用树链剖分来进行优化。

// Created by CAD on 2020/2/7.
#include <bits/stdc++.h>

#define fi first
#define se second
#define inf 0x3f3f3f3f
#define pii pair<int,int>
#define piii pair<pair<int,int>,int>
using namespace std;
const int maxn=5005;
int e[maxn];
piii q[maxn];
vector<pii> g[maxn];
bool dfs(int f,int s,int t,int c){
    if(s==t) return 1;
    bool bj=0;
    for(auto i:g[s]){
        int v=i.fi;
        if(v!=f) if(dfs(s,v,t,c)) e[i.se]=max(e[i.se],c),bj=1;
    }
    return bj;
}
bool check(int f,int s,int t,int &ans){
    if(s==t) return 1;
    bool bj=0;
    for(auto i:g[s]){
        int v=i.fi;
        if(v!=f) if(check(s,v,t,ans)) ans=min(ans,e[i.se]),bj=1;
    }
    return bj;
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0);
    int n;  cin>>n;
    for(int i=1;i<=n-1;++i){
        int u,v;    cin>>u>>v;
        g[u].push_back({v,i}),g[v].push_back({u,i});
    }
    int Q;  cin>>Q;
    for(int i=1;i<=Q;++i){
        int a,b,c;cin>>a>>b>>c;
        q[i]={{a,b},c};
        dfs(0,a,b,c);
    }
    for(int i=1;i<=Q;++i){
        int ans=inf;
        check(0,q[i].fi.fi,q[i].fi.se,ans);
        if(ans!=q[i].se) return puts("-1");
    }
    for(int i=1;i<=n-1;++i)
        if(e[i]) cout<<e[i]<<" ";
        else cout<<1<<" ";
}

Berland Beauty

原文:https://www.cnblogs.com/CADCADCAD/p/12274166.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!