设计网站公司 讲湖南岚鸿,h5视频怎么制作教学,会员管理系统功能介绍,免费行情软件app网站下载大全[ARC098F] Donation 给出一个 \(N\) 个点 \(M\) 条边的无向连通图#xff0c;每个点的标号为 \(1\) 到 \(n\)#xff0c; 且有两个权值 \(A_i,B_i\)。第 \(i\) 条边连接了点 \(u_i\) 和 \(v_i\)。 最开始时你拥有一定数量的钱#xff0c;并且可以选择这张图上的任意一个点作… [ARC098F] Donation 给出一个 \(N\) 个点 \(M\) 条边的无向连通图每个点的标号为 \(1\) 到 \(n\) 且有两个权值 \(A_i,B_i\)。第 \(i\) 条边连接了点 \(u_i\) 和 \(v_i\)。 最开始时你拥有一定数量的钱并且可以选择这张图上的任意一个点作为起始点之后你从这个点开始沿着给定的边遍历这张图。每当你到达一个点 \(v\) 时你必须拥有至少 \(A_v\) 元。而当你到达了这个点后你可以选择向它捐献 \(B_v\) 元(当然也可以选择不捐献)当然你需要保证在每次捐献之后自己剩余的钱\(\geq 0\)。 你需要对所有的 \(n\) 个点都捐献一次求你一开始至少需要携带多少钱。 \(1\le N\le 10^5,N-1\le M\le 10^5,1\le A_i,B_i\le 10^9,1\le u_iv_i\le N\)保证题目给出的图联通。 考虑倒着来那么每个点的限制变成了需要至少 \(C_i\max\{A_i-B_i,0\}\) 钱才能到达到了之后能够得到 \(B_i\) 块钱。 \(\bigstar\texttt{Hint}\)后面没有想到的主要原因是没发现如果到达了一个 \(C_i\) 的点则所有 \(\le C_i\) 的点都可以随意经过。 这样想到用 \(\text{Kruskal}\) 重构树建立连通性越往上 \(C\) 越大在树上判断。 答案一定是由一个节点向根节点方向走到达 \(u\) 后将 \(u\) 的所有子树遍历后在向上走。 设 \(dp_{i}\) 表示从 \(i\) 子树中一点走到 \(i\) 所需要的最小初始钱数\(S_i\) 表示 \(i\) 为根的子树的 \(B\) 之和则根据儿子们如下转移 如果自己是叶子节点则 \(dp_{i}C_i\)。如果不是则 \(dp_{i}\min_v\{\max(dp_i,C_i-S_v)\}\)。 #define Maxn 100005
int n,m,tot,rt;
int bel[Maxn],A[Maxn],B[Maxn],C[Maxn],fa[Maxn];
int hea[Maxn],nex[Maxn1],ver[Maxn1];
ll dp[Maxn],sum[Maxn];
vectorint g[Maxn];
struct Point
{int num,a,b,c;Point(int _num0,int _a0,int _b0,int _c0):num(_num),a(_a),b(_b),c(_c){}bool friend operator (Point x,Point y){ return (x.c!y.c)?x.cy.c:x.numy.num; }
}d[Maxn];
int Find(int x){ return (fa[x]x)?x:(fa[x]Find(fa[x])); }
inline void add(int x,int y){ ver[tot]y,nex[tot]hea[x],hea[x]tot; }
void dfs(int x)
{if(!g[x].size()) { sum[x]B[x],dp[x]C[x]; return; }sum[x]B[x],dp[x]infll;for(int v:g[x])dfs(v),sum[x]sum[v],dp[x]min(dp[x],max(dp[v],C[x]-sum[v]));
}
int main()
{nrd(),mrd();for(int i1;in;i)A[i]rd(),B[i]rd(),C[i]max(A[i]-B[i],0),d[i]Point(i,A[i],B[i],C[i]),fa[i]i;for(int i1,x,y;im;i) xrd(),yrd(),add(x,y),add(y,x);sort(d1,dn1);for(int p1,x,y;pn;p){xd[p].num;for(int ihea[x];i;inex[i]){yFind(ver[i]);if(x!y (C[y]C[x] || (C[y]C[x] yx)))g[x].pb(y),fa[y]x;}}rtd[n].num,dfs(rt);printf(%lld\n,dp[rt]sum[rt]);return 0;
}
