[atARC098F]Donation

贪心，一定在最后一次经过某节点时付出$b_{u}$，条件是付出后$W\ge \max(a_{i}-b_{i},0)$（同时也可以仅考虑这个限制，因为$W$在过程中不会增大）

假设“最后一次经过”的顺序为$p_{1},p_{2},...,p_{n}$，则要保证存在$p_{i}$到$p_{i+1}$的路径不经过$p_{1},...,p_{i-1}$，也即对于任意一个后缀，其点集的导出子图连通

倒序模拟这个过程（因为有连通的限制），二分枚举$d=W-\sum_{i=1}^{n}b_{i}$，那么可以看作从一个点（$p_{n}$）开始拓展，找到相邻的$x$满足$d\ge a_{x}-b_{x}$，则可以拓展$x$（作为$p_{n-1}$），重复此过程直至拓展整张图

由于拓展只会增加$d$，因此可以贪心拓展，用优先队列维护最小的$a_{x}-b_{x}$去拓展一定最优，此时时间复杂度为$o(n^{2}\log^{2}n)$（因为要枚举$p_{n}$，还有优先队列），无法通过

仍然先枚举$p_{n}$，令$v$为$a_{v}-b_{v}$最大的位置，$G'$为删除$v$后$p_{n}$所在的连通块，从上面的过程来看，在这个贪心下，只有拓展完$G'$后才可能拓展$v$，同时当拓展完$v$后整张图一定都可以拓展

因此，合法条件变为两个：1.$G'$能拓展完；2.$G'$拓展完后$d\ge a_{v}-b_{v}$，前者是一个子问题，可以继续找到最大的$v'$来处理，直至最后$|V|=1$（即为起点）

将这个结构构成一棵树（类似点分树，只是将重心换成$a_{v}-b_{v}$最大的位置），根据上面的条件，即要求找到$a_{x}-b_{x}\le d$的位置，满足$s_{x}+d\ge a_{fa}-b_{fa}$（其中$s_{x}$为$x$子树中$b$的和）直至根

如何建出这棵树，可以从小到大枚举$a_{i}-b_{i}$，然后去合并相邻且比他小的位置作为儿子，再用并查集维护即可

由于后者的条件与起点关系不大，可以看作从根出发，找到合法且$a_{x}-b_{x}$最小的位置，判断与$d$的大小即可，此时时间复杂度为$o(n\log n)$

还可以枚举起点的位置来做到$o(n)$，即先忽略$a_{x}-b_{x}\le d$的限制，求出每一个位置上最小的$d$，记为$f_{k}$，转移为$f_{k}=\max(f_{fa},a_{fa}-b_{fa}-s_{k})$，答案为$\min_{1\le i\le n}\max(f_{i},a_{i}-b_{i})$

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 #define N 100005

 4 #define ll long long

 5 struct ji{

 6     int nex,to;

 7 }edge[N<<1];

 8 vector<int>v[N];

 9 int E,n,m,x,y,ans,head[N],a[N],id[N],rk[N],fa[N],f[N];

10 ll s[N];

11 bool cmp(int x,int y){

12     return a[x]<a[y];

13 }

14 void add(int x,int y){

15     edge[E].nex=head[x];

16     edge[E].to=y;

17     head[x]=E++;

18 }

19 int find(int k){

20     if (k==fa[k])return k;

21     return fa[k]=find(fa[k]);

22 }

23 void merge(int x,int y){

24     x=find(x),y=find(y);

25     if (x!=y){

26         fa[x]=y;

27         s[y]+=s[x];

28         v[y].push_back(x);

29     }

30 }

31 void dfs(int k){

32     ans=min(ans,max(f[k],a[k]));

33     for(int i=0;i<v[k].size();i++){

34         f[v[k][i]]=f[k];

35         if (a[k]>s[v[k][i]])f[v[k][i]]=max(f[k],(int)(a[k]-s[v[k][i]]));

36         dfs(v[k][i]);

37     }

38 }

39 int main(){

40     scanf("%d%d",&n,&m);

41     memset(head,-1,sizeof(head));

42     for(int i=1;i<=n;i++){

43         scanf("%d%lld",&a[i],&s[i]);

44         a[i]=max(a[i]-s[i],0LL);

45         id[i]=fa[i]=i;

46     }

47     sort(id+1,id+n+1,cmp);

48     for(int i=1;i<=n;i++)rk[id[i]]=i;

49     for(int i=1;i<=m;i++){

50         scanf("%d%d",&x,&y);

51         add(x,y);

52         add(y,x);

53     }

54     for(int i=1;i<=n;i++)

55         for(int j=head[id[i]];j!=-1;j=edge[j].nex)

56             if (rk[edge[j].to]<i)merge(edge[j].to,id[i]);

57     ans=a[id[n]];

58     dfs(id[n]);

59     printf("%lld",ans+s[id[n]]);

60 }

巴特西

[atARC098F]Donation

最新文章

热门文章