题意:

给一棵树,边权未知,现在给m组约束,每组约束给出从u到v路径中的最小值,现在让你给出一组边权,使得符合之前的约束,不能给出输出-1

思路:

因为n较小,对于每组约束我们可以直接暴力修改路径上的权值,如果边的权值小于当前约束的最小值,则将权值修改,最后再根据每组约束暴力走一遍路径看路径是否满足要求,如果不满足则输出-1,最后还得对那些没有修改过的边随意赋值

#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
#define inf 0x3f3f3f3f
using namespace std;
const int maxn=;
int id[maxn][maxn],edge[maxn][maxn],fa[maxn],f[maxn],dep[maxn];
//id记录从i到j这条边的编号,edge记录边的权值,fa记录i的父亲是谁,f记录边的权值 ,dep记录深度
vector<int> a[maxn];
int from[maxn],to[maxn],mi[maxn];
int n,m,u,v,w;
void dfs(int x,int p)//处理出父亲与深度
{
fa[x]=p,dep[x]=dep[p]+;
for(int i=;i<a[x].size();i++)
if(a[x][i]!=p) dfs(a[x][i],x);
}
void dfs2(int x,int p)
{
for(int i=;i<a[x].size();i++){
if(a[x][i]!=p){
int to=a[x][i];
f[id[x][to]]=edge[x][to];
dfs2(a[x][i],x);
}
}
}
void solve()
{
scanf("%d",&m);
for(int i=;i<=m;i++){
scanf("%d%d%d",&from[i],&to[i],&mi[i]);
if(dep[from[i]]<dep[to[i]]) swap(from[i],to[i]);
int k1=from[i],k2=to[i],mini=mi[i];
while(dep[k1]!=dep[k2]){
int p=fa[k1];
if(edge[p][k1]<=mini) edge[p][k1]=edge[k1][p]=mini;
k1=p;
}
while(k1!=k2){
int p1=fa[k1],p2=fa[k2];
if(edge[p1][k1]<=mini) edge[p1][k1]=edge[k1][p1]=mini;
if(edge[p2][k2]<=mini) edge[p2][k2]=edge[k2][p2]=mini;
k1=p1,k2=p2;
}
}
for(int i=;i<=m;i++){
int x=inf;
int k1=from[i],k2=to[i],mini=mi[i];
if(dep[k1]<dep[k2]) swap(k1,k2);
while(dep[k1]!=dep[k2]){
int p=fa[k1];
x=min(x,edge[p][k1]);
k1=p;
}
while(k1!=k2){
int p1=fa[k1],p2=fa[k2];
x=min(x,edge[p1][k1]);
x=min(x,edge[p2][k2]);
k1=p1,k2=p2;
}
if(x!=mini){ cout<<-<<endl;return;}
}
dfs2(,);
for(int i=;i<n;i++){
if(!f[i]) cout<<<<" ";
else cout<<f[i]<<" ";
}
}
int main()
{
scanf("%d",&n);
for(int i=;i<n;i++){
scanf("%d%d",&u,&v);
a[u].push_back(v);
a[v].push_back(u);
id[u][v]=id[v][u]=i;
}
dfs(,);
solve();
return ;
}

最新文章

  1. 创建 Monitor 并测试 - 每天5分钟玩转 OpenStack(124)
  2. 创建Azure DS 虚拟机并附加SSD硬盘
  3. JavaScript模块化---AMD规范
  4. C#winform导出数据到Excel的类
  5. 转:linux执行shell脚本的方式及一些区别
  6. FLEX中Tree默认展开全部节点
  7. 解决 Boot Camp 虚拟机升级到 Windows 10 后 Parallels Desktop 不能识别的问题
  8. [置顶] window.open()你真的会了吗?
  9. POJ2155:Matrix(二维树状数组,经典)
  10. Java String charAt()方法
  11. UOJ #269. 【清华集训2016】如何优雅地求和
  12. Fullcalendar改版后发布到IIS或者tomcat里面前端加载数据不显示的问题
  13. c++入门之类与内存
  14. Java并发编程之ThreadGroup
  15. jQuery 自执行函数
  16. RabbitMQ for CentOS安装教程
  17. asp.net mvc maproute定义可变数量的自定义片断变量
  18. DataFrame 取值
  19. apache基金会项目及甲骨文项目汇总
  20. C# HttpClientHelper请求

热门文章

  1. LeetCode 1 Two Sum——在数组上遍历出花样
  2. window10 自带虚拟机输入ip addr 不显示ip,显示字母加数字
  3. 牛客国庆days赛 地铁
  4. leetcode.310最小高度树
  5. 用本地自定义域名访问远程服务器,并支持websocket和cookie
  6. 接口自动化测试框架 -- reudom
  7. llinux重启、用户切换、注销命令
  8. JDK12 的下载和没有jre的解决及环境配置
  9. 【重要】Pro Git 第二版 简体中文
  10. vue兄弟组件传值——事件总线