首页 > 代码库 > 【bzoj4276】[ONTAK2015]Bajtman i Okr?g?y Robin 线段树优化建图+费用流
【bzoj4276】[ONTAK2015]Bajtman i Okr?g?y Robin 线段树优化建图+费用流
题目描述
有n个强盗，其中第i个强盗会在[a[i],a[i]+1]，[a[i]+1,a[i]+2]，...，[b[i]-1,b[i]]这么多段长度为1时间中选出一个时间进行抢劫，并计划抢走c[i]元。作为保安，你在每一段长度为1的时间内最多只能制止一个强盗，那么你最多可以挽回多少损失呢？
输入
第一行包含一个正整数n(1<=n<=5000)，表示强盗的个数。
接下来n行，每行包含三个正整数a[i],b[i],c[i](1<=a[i]<b[i]<=5000,1<=c[i]<=10000)，依次描述每一个强盗。
输出
输出一个整数，即可以挽回的损失的最大值。
样例输入
4
1 4 40
2 4 10
2 3 30
1 3 20
样例输出
90
题目大意
有n个强盗，其中第i个强盗会在[a[i],b[i]]这段时间内进行抢劫，并计划抢走c[i]元。作为保安，你在每一段长度为1的时间内最多只能制止一个强盗，那么你最多可以挽回多少损失呢？
题解
线段树优化建图+费用流（+语文题）
想要做这道题，必须先读懂题（个人觉得题目描述有问题，所以重新翻译了一遍）
读懂题以后发现是费用流，先将b[i]--，把时间段转化为点；然后连边S->强盗，容量为1，费用为c[i]；强盗->a[i]、a[i]+1、...、b[i]，容量为1，费用为0；时间k->T，容量为1，费用为0。跑最大费用最大流即为答案。
但是这样边数过多，考虑到时间是一段连续的区间，所以可以使用线段树优化建图。
建立线段树，从父节点向子节点连容量为inf，费用为0的边；S->强盗，容量为1，费用为c[i]；对于每个强盗，找到[a[i],b[i]]对应的区间，该强盗向这些区间连边，容量为1，费用为0；叶子结点向T连边，容量为1，费用为0。这张图的最大费用最大流即为答案。
另外此题的spfa费用流必须加inq（在队列中）优化，否则会TLE。
#include <cstdio>#include <cstring>#include <queue>#define N 30000#define M 3000000#define lson l , mid , x << 1#define rson mid + 1 , r , x << 1 | 1using namespace std;const int inf = 1 << 30;queue<int> q;int a[N] , b[N] , c[N] , head[N] , to[M] , val[M] , cost[M] , next[M] , cnt = 1 , s , t , dis[N] , from[N] , pre[N] , inq[N];inline int read(){ int ret = 0; char ch = getchar(); while(ch < ‘0‘ || ch > ‘9‘) ch = getchar(); while(ch >= ‘0‘ && ch <= ‘9‘) ret = (ret << 3) + (ret << 1) + ch - ‘0‘ , ch = getchar(); return ret;}void add(int x , int y , int v , int c){ to[++cnt] = y , val[cnt] = v , cost[cnt] = c , next[cnt] = head[x] , head[x] = cnt; to[++cnt] = x , val[cnt] = 0 , cost[cnt] = -c , next[cnt] = head[y] , head[y] = cnt;}bool spfa(){ int x , i; memset(from , -1 , sizeof(from)); memset(dis , 0x3f , sizeof(dis)); dis[s] = 0 , q.push(s); while(!q.empty()) { x = q.front() , q.pop() , inq[x] = 0; for(i = head[x] ; i ; i = next[i]) { if(val[i] && dis[to[i]] > dis[x] + cost[i]) { dis[to[i]] = dis[x] + cost[i] , from[to[i]] = x , pre[to[i]] = i; if(!inq[to[i]]) inq[to[i]] = 1 , q.push(to[i]); } } } return ~from[t];}int mincost(){ int ans = 0 , i , k; while(spfa()) { k = inf; for(i = t ; i != s ; i = from[i]) k = min(k , val[pre[i]]); ans += k * dis[t]; for(i = t ; i != s ; i = from[i]) val[pre[i]] -= k , val[pre[i] ^ 1] += k; } return ans;}void build(int l , int r , int x){ if(l == r) { add(x , t , 1 , 0); return; } int mid = (l + r) >> 1; build(lson) , build(rson); add(x , x << 1 , inf , 0) , add(x , x << 1 | 1 , inf , 0);}void update(int b , int e , int k , int l , int r , int x){ if(b <= l && r <= e) { add(k , x , 1 , 0); return; } int mid = (l + r) >> 1; if(b <= mid) update(b , e , k , lson); if(e > mid) update(b , e , k , rson);}int main(){ int n , m = 0 , i; n = read(); for(i = 1 ; i <= n ; i ++ ) a[i] = read() , b[i] = read() - 1 , c[i] = read() , m = max(m , b[i]); s = 0 , t = 4 * m , build(1 , m , 1); for(i = 1 ; i <= n ; i ++ ) add(s , t + i , 1 , -c[i]) , update(a[i] , b[i] , t + i , 1 , m , 1); printf("%d\n" , -mincost()); return 0;}
【bzoj4276】[ONTAK2015]Bajtman i Okr?g?y Robin 线段树优化建图+费用流
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。