BZOJ 3218 A + B Problem (可持久化线段树+最小割)

做法见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());
}