bzoj3218: a + b Problem

제목 의 명칭 은 나 를 끌 어 들 인 것 이다.
우선 이것 은 최소 절단 모형 입 니 다. 대 점 i, 연 S - > i: b [i], i - > T: w [i], i - > i ': p [i], i' - > j (이상): inf, 이렇게 해서 TLE 알고리즘 이 생 겼 습 니 다.
어 떡 하지?
그리고 vfk 는 n ^ 2 의 변 을 nlogn 으로 강제로 줄 였 습 니 다.
선분 트 리 를 사용 하 는 것 을 고려 하여 a 값 을 특정한 구간 에 있 는 점 을 새로운 점 으로 표시 합 니 다. 가중치 선분 트 리 에서 i - > ls [i]: inf, i - > rs [i]: inf, 대응 하 는 점 - > 잎 노드: inf.그러나 모든 점 이 이전의 점 에 만 영향 을 미 치기 때문에 주석 나무 가 필요 하고 모든 잎 노드 - > 앞의 나무 에 대응 하 는 점: inf.이렇게 하면 되 지만 방향 은 주의해 야 한다.
이렇게 처리 한 후에 변 수가 크게 줄 어 들 었 다. 그러면 문제 가 생 겼 다. dinic 의 복잡 도 는 얼마 입 니까? -O (n ^ 2 * m) O (m * sqrt (m) O (현학)
또한 dinic 는 if (! used) d [x] = 0 과 같은 최적화 도 있다.
그래도 느 려...

#include
#include
#include
#include
#define N 50005
#define M 500005
#define inf 1000000000
using namespace std;
int n,S,T,cnt,a[N],b[N],w[N],l[N],r[N],p[N],num[N],num_[N],Rt[N];
int first[M],to[M],flo[M],nxt[M],L=1;
int ls[M],rs[M],Num[M],sum;
int d[M],q[M],Ans,c[N*3],hz;
int read()
{
	int x=0;char c=getchar();
	while(c'9') c=getchar();
	while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
	return x;
}
void link(int x,int y,int z)
{
	to[++L]=y;flo[L]=z;nxt[L]=first[x];first[x]=L;
	to[++L]=x;flo[L]=0;nxt[L]=first[y];first[y]=L;
}
void Get(int k,int l,int r,int x,int y,int w)
{
	if (!k) return;
	if (x<=l&&r<=y)
	{
		link(w,Num[k],inf);
		return;
	}
	int mid=l+r>>1;
	if (x<=mid) Get(ls[k],l,mid,x,y,w);
	if (y>mid) Get(rs[k],mid+1,r,x,y,w);
}
void add(int &k,int p,int l,int r,int x,int w)
{
	if (!k) Num[k=++sum]=++cnt;
	if (l==r)
	{
		link(Num[k],w,inf);
		if (p) link(Num[k],Num[p],inf);
		return;
	}
	int mid=l+r>>1;
	if (x<=mid) rs[k]=rs[p],add(ls[k],ls[p],l,mid,x,w);
	else ls[k]=ls[p],add(rs[k],rs[p],mid+1,r,x,w);
}
bool BFS(int S,int T)
{
	memset(d,-1,sizeof d);
	int l=0,r=1,t;
	q[1]=S;d[S]=1;
	while(l

최적화 판

#include
#include
#include
#include
#define N 5005
#define M 500005
#define inf 1000000000
using namespace std;
int n,S,T,cnt,a[N],b[N],w[N],l[N],r[N],p[N],num[N],num_[N],Rt[N];
int first[M],to[M],flo[M],nxt[M],L=1;
int ls[M],rs[M],Num[M],sum;
int d[M],q[M],Ans,c[N],hz;
int read()
{
	int x=0;char c=getchar();
	while(c'9') c=getchar();
	while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
	return x;
}
void link(int x,int y,int z)
{
	to[++L]=y;flo[L]=z;nxt[L]=first[x];first[x]=L;
	to[++L]=x;flo[L]=0;nxt[L]=first[y];first[y]=L;
}
void Get(int k,int l,int r,int x,int y,int w)
{
	if (!k) return;
	if (x<=l&&r<=y)
	{
		link(w,Num[k],inf);
		return;
	}
	int mid=l+r>>1;
	if (x<=mid) Get(ls[k],l,mid,x,y,w);
	if (y>mid) Get(rs[k],mid+1,r,x,y,w);
}
void add(int &R,int p,int l,int r,int x,int w)
{
	int k,mid;
	Num[k=R=++sum]=++cnt;
	while(l>1;
		if (x<=mid) rs[k]=rs[p],Num[k=ls[k]=++sum]=++cnt,p=ls[p],r=mid;
		else ls[k]=ls[p],Num[k=rs[k]=++sum]=++cnt,p=rs[p],l=mid+1;
	}
	link(Num[k],w,inf);
	if (p) link(Num[k],Num[p],inf);
}
bool BFS(int S,int T)
{
	memset(d,-1,sizeof d);
	int l=0,r=1,t;
	q[1]=S;d[S]=1;
	while(l