常见网站攻击方式,做论坛网站 备案,网站建设功能表,企业官网营销推广正题
题目链接:https://www.ybtoj.com.cn/contest/70/problem/3 题目大意
一棵树nnn个节点#xff0c;每条边(x,y,a,b)(x,y,a,b)(x,y,a,b)#xff0c;可以花费111的代价让一条边的a,ba,ba,b都减去111#xff0c;但是不能小于000#xff0c;要求最少代价使得每条边满足yyy…正题
题目链接:https://www.ybtoj.com.cn/contest/70/problem/3 题目大意
一棵树nnn个节点每条边(x,y,a,b)(x,y,a,b)(x,y,a,b)可以花费111的代价让一条边的a,ba,ba,b都减去111但是不能小于000要求最少代价使得每条边满足yyy子树的边的aaa和不超过bbb。 解题思路
发现如果没有不能小于000的条件很好做这样我们肯定优先减去最下面的aia_iai即可然后减去上面时bib_ibi减少不会影响答案因为都已经满足下面的已经减完了。
但是有可能ababab此时aaa的权值就不能减完对于这些一定不能减去的权值我们之间让整条到根节点上的bbb减去这些值就好了。
时间复杂度O(n)O(n)O(n) codecodecode
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N2e510,inf1e18;
struct node{ll to,next;
}a[N*2];
ll n,tot,ls[N],w[N],lim[N],f[N];
void addl(ll x,ll y){a[tot].toy;a[tot].nextls[x];ls[x]tot;return;
}
ll dfs(ll x){ll sum0,k;for(ll ils[x];i;ia[i].next){ll ya[i].to;sumdfs(y);}kmax(0ll,w[x]-lim[x]);lim[x]-sum;w[x]-k;return sumk;
}
void solve(ll x){ll tmp0;for(ll ils[x];i;ia[i].next){ll ya[i].to;solve(y);f[x]f[y];tmpw[y];}f[x]max(f[x],tmp-lim[x]);w[x]tmp;return;
}
int main()
{freopen(tree.in,r,stdin);freopen(tree.out,w,stdout);scanf(%lld,n);for(ll i1;in;i){ll x,y,u,v;scanf(%lld%lld%lld%lld,x,y,u,v);addl(x,y);w[y]u;lim[y]v;}lim[1]inf;dfs(1);for(ll i1;in;i)if(lim[i]0)return printf(-1)0;solve(1);printf(%lld\n,f[1]);
}
