BZOJ 3218 A + B Problem (可持久化线段树+最小割)
2024-09-05 03:48:21
做法见dalao博客 geng4512的博客, 思路就是用线段树上的结点来进行区间连边.因为有一个只能往前面连的限制,所以还要可持久化.(duliu)
一直以来我都是写dinicdinicdinic做最大流,感觉加上弧优化等等效率还是蛮高的…但是这道题点数边数都是 nlognlognlog 级别的,让我发现还是SAP(ISAP?SAP(ISAP?SAP(ISAP?)最快啊…
这是dinicdinicdinic AC代码(加上弧优化 4112 ms, 不加 4072 ms)
#include <cstdio>
#include <cstring>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
template<typename T>inline void read(T &num) {
char ch; while((ch=getchar())<'0'||ch>'9');
for(num=0;ch>='0'&&ch<='9';num=num*10+ch-'0',ch=getchar());
}
const int N = 5005;
const int MAXN = N*20;
const int MAXM = 1000005;
const int inf = 1e9;
int n, fir[MAXN], S, T, cnt, sz;
struct edge { int to, nxt, c; }e[MAXM];
inline void add(int u, int v, int cc) {
e[cnt] = (edge){ v, fir[u], cc }; fir[u] = cnt++;
e[cnt] = (edge){ u, fir[v], 0 }; fir[v] = cnt++;
}
int dis[MAXN], vis[MAXN], info[MAXN], cur, q[MAXN];
inline bool bfs() {
int head = 0, tail = 0;
vis[S] = ++cur; q[tail++] = S; dis[S] = 0;
while(head < tail) {
int u = q[head++];
for(int i = fir[u]; ~i; i = e[i].nxt)
if(e[i].c && vis[e[i].to] != cur)
vis[e[i].to] = cur, dis[e[i].to] = dis[u] + 1, q[tail++] = e[i].to;
}
return vis[T] == cur;
}
int dfs(int u, int Max) {
if(u == T || !Max) return Max;
int flow=0, delta;
for(int i = fir[u]; ~i; i = e[i].nxt)
if(e[i].c && dis[e[i].to] == dis[u] + 1 && (delta=dfs(e[i].to, min(e[i].c, Max-flow)))) {
e[i].c -= delta, e[i^1].c += delta, flow += delta;
if(flow == Max) return flow;
}
if(!flow) dis[u] = -1;
return flow;
}
inline int dinic() {
int flow=0, x;
while(bfs()) while((x=dfs(S, inf))) flow+=x;
return flow;
}
int A[N], B[N], W[N], L[N], R[N], P[N], Q[N*3], sum, tot;
int rt[MAXN], ch[MAXN][2]; void Insert(int &rt, int p, int l, int r, int i) {
rt = ++sz;
if(l == r) {
add(rt+T, i, inf);
if(p) add(rt+T, p+T, inf);
return;
}
int mid = (l + r) >> 1;
if(A[i] <= mid) ch[rt][1] = ch[p][1], Insert(ch[rt][0], ch[p][0], l, mid, i);
else ch[rt][0] = ch[p][0], Insert(ch[rt][1], ch[p][1], mid+1, r, i);
if(ch[rt][0]) add(rt+T, ch[rt][0]+T, inf);
if(ch[rt][1]) add(rt+T, ch[rt][1]+T, inf);
} void Link(int rt, int l, int r, int i) {
if(L[i] <= l && r <= R[i]) { add(i+n, rt+T, inf); return; }
int mid = (l + r) >> 1;
if(L[i] <= mid && ch[rt][0]) Link(ch[rt][0], l, mid, i);
if(R[i] > mid && ch[rt][1]) Link(ch[rt][1], mid+1, r, i);
} int main () {
memset(fir, -1, sizeof fir);
read(n); S = 0, T = 2*n+1;
for(int i = 1; i <= n; ++i)
read(A[i]), read(B[i]), read(W[i]),
read(L[i]), read(R[i]), read(P[i]),
Q[++tot] = A[i], Q[++tot] = L[i], Q[++tot] = R[i], sum += B[i] + W[i];
sort(Q + 1, Q + tot + 1);
tot = unique(Q + 1, Q + tot + 1) - (Q + 1);
for(int i = 1; i <= n; ++i)
A[i] = lower_bound(Q + 1, Q + tot + 1, A[i]) - Q,
L[i] = lower_bound(Q + 1, Q + tot + 1, L[i]) - Q,
R[i] = lower_bound(Q + 1, Q + tot + 1, R[i]) - Q,
add(S, i, B[i]), add(i, T, W[i]), add(i, i+n, P[i]);
for(int i = 1; i <= n; ++i) {
if(i > 1) Link(rt[i-1], 1, tot, i);
Insert(rt[i], rt[i-1], 1, tot, i);
}
sz += T;
printf("%d\n", sum-dinic());
}
然后下面是SAP(ISAP?)SAP(ISAP?)SAP(ISAP?)的AC代码(444 ms!!!快了10倍!!)
#include <cstdio>
#include <cstring>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
char cb[1<<15],*cs=cb,*ct=cb;
#define getc() (cs==ct&&(ct=(cs=cb)+fread(cb,1,1<<15,stdin),cs==ct)?0:*cs++)
template<typename T>inline void read(T &num) {
char ch; while((ch=getc())<'0'||ch>'9');
for(num=0;ch>='0'&&ch<='9';num=num*10+ch-'0',ch=getc());
}
const int N = 5005;
const int MAXN = N*20;
const int MAXM = 1000005;
const int inf = 1e9;
int n, fir[MAXN], S, T, cnt, sz;
struct edge { int to, nxt, c; }e[MAXM];
inline void add(int u, int v, int cc) {
e[cnt] = (edge){ v, fir[u], cc }; fir[u] = cnt++;
e[cnt] = (edge){ u, fir[v], 0 }; fir[v] = cnt++;
}
int A[N], B[N], W[N], L[N], R[N], P[N], Q[N*3], sum, tot;
int rt[MAXN], ch[MAXN][2];
void Insert(int &rt, int p, int l, int r, int i) {
rt = ++sz;
if(l == r) {
add(rt+T, i, inf);
if(p) add(rt+T, p+T, inf);
return;
}
int mid = (l + r) >> 1;
if(A[i] <= mid) ch[rt][1] = ch[p][1], Insert(ch[rt][0], ch[p][0], l, mid, i);
else ch[rt][0] = ch[p][0], Insert(ch[rt][1], ch[p][1], mid+1, r, i);
if(ch[rt][0]) add(rt+T, ch[rt][0]+T, inf);
if(ch[rt][1]) add(rt+T, ch[rt][1]+T, inf);
}
void Link(int rt, int l, int r, int i) {
if(L[i] <= l && r <= R[i]) { add(i+n, rt+T, inf); return; }
int mid = (l + r) >> 1;
if(L[i] <= mid && ch[rt][0]) Link(ch[rt][0], l, mid, i);
if(R[i] > mid && ch[rt][1]) Link(ch[rt][1], mid+1, r, i);
}
namespace SAP {
int d[MAXN], vd[MAXN]; //sz表示总点数
int Aug(int u, int Max) {
if(u == T) return Max;
int delta, dmin = sz - 1, flow = 0, v;
for(int i = fir[u]; ~i; i = e[i].nxt) if(e[i].c) {
v = e[i].to;
if(d[v] + 1 == d[u]) {
delta = Aug(v, min(Max-flow, e[i].c));
e[i].c -= delta, e[i^1].c += delta, flow += delta;
if(d[S] >= sz || flow == Max) return flow;
}
if(dmin > d[v]) dmin = d[v];
}
if(!flow) {
--vd[d[u]];
if(!vd[d[u]]) d[S] = sz;
++vd[d[u] = dmin + 1];
}
return flow;
}
int sap() {
memset(d, 0, sizeof d);
memset(vd, 0, sizeof vd);
int flow = 0;
while(d[S] < sz)
flow += Aug(S, inf);
return flow;
}
}
int main () {
memset(fir, -1, sizeof fir);
read(n); S = 0, T = 2*n+1;
for(int i = 1; i <= n; ++i)
read(A[i]), read(B[i]), read(W[i]),
read(L[i]), read(R[i]), read(P[i]),
Q[++tot] = A[i], Q[++tot] = L[i], Q[++tot] = R[i], sum += B[i] + W[i];
sort(Q + 1, Q + tot + 1);
tot = unique(Q + 1, Q + tot + 1) - (Q + 1);
for(int i = 1; i <= n; ++i)
A[i] = lower_bound(Q + 1, Q + tot + 1, A[i]) - Q,
L[i] = lower_bound(Q + 1, Q + tot + 1, L[i]) - Q,
R[i] = lower_bound(Q + 1, Q + tot + 1, R[i]) - Q,
add(S, i, B[i]), add(i, T, W[i]), add(i, i+n, P[i]);
for(int i = 1; i <= n; ++i) {
if(i > 1) Link(rt[i-1], 1, tot, i);
Insert(rt[i], rt[i-1], 1, tot, i);
}
sz += T;
printf("%d\n", sum-SAP::sap());
}
最新文章
- 适配ios10（iTunes找不到构建版本）
- easyui datagrid 点击表头的事件
- JAVA基础知识之NIO.2——Path,Paths,Files
- Mybatis根据表自动生成相关代码
- openssl API网络通信
- Quartz 2D绘制简单图形
- 使用EntityFramework6完成增删查改和事务
- String StringBuilder以及StringBuffer
- 在windows上编译MatConvNet
- PHP MySQL Update
- MySQL增删改查常用语句命令
- （转）Eclipse中快速输入System.out.println()的快捷键
- UVA 10820 欧拉函数模板题
- Jupyter如何将numpy数据以图像形式展现？
- Android SDK + Appium 环境搭建
- pycharm如何解决新建的文件没有后缀的问题
- Laravel创建自定义 Artisan 控制台命令实例教程
- sqlserver数据库18456错误怎么解决？
- IO -阻塞，非阻塞， 同步，异步
- CodeForces - 140E：New Year Garland （组合数&&DP）