首页 > 其他 > 详细

[ARC098F] Donation

时间:2019-10-17 12:19:33      阅读:95      评论:0      收藏:0      [点我收藏+]

问题描述

给定一张 n个点,m条边的无向图。这张图的每个点有两个权值 ai,bi。你将会从这张图中选出一个点作为起点,随后开始遍历这张图。你能到达一个节点 i当且仅当你的手上有至少 ai 元钱。当你到达一个节点 i后,你可以选择对这个点捐赠bi 元。你需要对每个点捐赠一次。问你身上至少要带多少元钱?

输入格式

第一行两个数 n,m。

下 n 行,每行两个数 ai,bi。

下 m 行,每行两个数 ui,vi ,表示有一条从 ui到 vi 的边。

输出格式

输出一行一个整数,为答案。

样例输入

4 5
3 1
1 2
4 1
6 2
1 2
2 3
2 4
1 4
3 4

样例输出

6

解析

注意我们经过一个点的时候只需要花费一次,而且可以在任意时刻花费。那么显然的是我们对于每个重复经过的点,使其在最后一次经过时缴纳费用是最优的。

因此我们修改a的约束,建立数组c,使\(c[i]=max(a[i]-b[i],0)\)表示我们在任意时刻经过了i这个点,手中一定至少要拥有\(c_i\)的钱数。

我们可以贪心的想到先遍历\(c_i\)最大的点,那么删去这个点之后,我们就得到了若干个联通块。然后最优的方法明显是贡献了\(c_i\)之后进入了一个联通块之后就不再出来。

然后我们一层一层的递归,用子树的根去连上一层的根。这样我们就可以构造一棵所有子树的\(c_i\)都要小于根节点的树。

接下来可以直接DP,\(f[x]\)表示x的子树符合条件的最小初始钱数,\(s[x]\)表示x的子树的b值之和,即遍历完整棵子树在x所需的代价(不包括\(c[x]\))。\(f[x]\)初值为\(s[x]+c[x]\)表示最后在x点停下。然后枚举最后遍历的是哪棵子树,状态转移方程为
\[ f[x]=min(f[x],s[x]-s[y]+max(f[y],c[x])) \]

代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#define int long long
#define N 100002
using namespace std;
int head[N],ver[N*2],nxt[N*2],l;
int head1[N],ver1[N*2],nxt1[N*2],l1;
int n,m,i,j,a[N],b[N],c[N],fa[N],p[N],f[N],sum[N];
bool vis[N];
int read()
{
    char c=getchar();
    int w=0;
    while(c<'0'||c>'9') c=getchar();
    while(c<='9'&&c>='0'){
        w=w*10+c-'0';
        c=getchar();
    }
    return w;
}
void insert(int x,int y)
{
    l++;
    ver[l]=y;
    nxt[l]=head[x];
    head[x]=l;
}
void insert1(int x,int y)
{
    l1++;
    ver1[l1]=y;
    nxt1[l1]=head1[x];
    head1[x]=l1;
}
int my_comp(const int &x,const int &y)
{
    return c[x]<c[y];
}
int find(int x)
{
    if(fa[x]!=x) fa[x]=find(fa[x]);
    return fa[x];
}
void dfs(int x)
{
    sum[x]=b[x];
    for(int i=head1[x];i;i=nxt1[i]){
        int y=ver1[i];
        dfs(y);
        sum[x]+=sum[y];
    }
    f[x]=sum[x]+c[x];
    for(int i=head1[x];i;i=nxt1[i]){
        int y=ver1[i];
        f[x]=min(f[x],sum[x]-sum[y]+max(f[y],c[x]));
    }
}
signed main()
{
    n=read();m=read();
    for(i=1;i<=n;i++){
        a[i]=read();b[i]=read();
        c[i]=max(a[i]-b[i],1LL*0);
    }
    for(i=1;i<=m;i++){
        int u=read(),v=read();
        insert(u,v);
        insert(v,u);
    }
    for(i=1;i<=n;i++) fa[i]=p[i]=i;
    sort(p+1,p+n+1,my_comp);
    for(i=1;i<=n;i++){
        int x=p[i];
        vis[x]=1;
        for(j=head[x];j;j=nxt[j]){
            int y=ver[j];
            if(vis[y]){
                int f=find(y);
                if(f!=x){
                    fa[f]=x;
                    insert1(x,f);
                }
            }
        }
    }
    dfs(p[n]);
    cout<<f[p[n]]<<endl;
    return 0;
}

[ARC098F] Donation

原文:https://www.cnblogs.com/LSlzf/p/11691098.html

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