题解 JSOI2013 打地鼠

题面

luogu5263

解析

事先声明:

似乎并不用考虑左右手???

贪心地想一想它左手能走到右手右边那不如直接用右手走???

以上为个人猜测,并无证明...

但是迷之能过...

考虑用一个 bitset 维护每次打完后下次能打的地鼠.

然后直接拆点连边...

把左右手看为 $1$ 号和 $2$ 号地鼠,把 $i$ 分为 $i$ 和 $i+n$.

打完 $i$ 后若能打 $j$ 则连 $i+n->j$,费用为 $0$,

每个点连 $i->i+n$,费用为 $-p$.

最后 $S$ 连 $1$ 和 $2$,$i+n$ 连 $T$,跑最小费用最大流即可.

但显然会 TLE....

考虑优化一下,

对于 $i$,如果它连了 $j$,那么 $j$ 能连的所有点 $i$ 都不连了..

然后每个点 $i$ 连 $i->i+n$,费用为0,表示不选这个,但是给之前的提供一条路径...

code

#include <iostream>
#include <stdio.h>
#include <cstring>
#include <bitset>
#include <queue>
#include <cstdlib>
#define ll long long
#define filein(a) freopen(a".cpp","r",stdin)
#define fileout(a) freopen(a".cpp","w",stdout);
using namespace std;

inline int read(){
	int sum=0,f=1;char c=getchar();
	while((c<'0'||c>'9')&&c!=EOF){if(c=='-') f=-1;c=getchar();}
	while(c>='0'&&c<='9'&&c!=EOF){sum=sum*10+c-'0';c=getchar();}
	return sum*f;
}

const int N=10008;
const int M=1000005;
const int INF=0x3f3f3f3f;
struct edge{int to,next,v,w;}e[M];
struct node{int x,t,p;}a[N];
int n,V,S,T,ans;
int head[N],cnt=1;
int in[N],d[N],cur[N],v[N];
bitset<3008> G[3008],ret;
queue<int> que;

inline void add(int x,int y,int v,int w){
	e[++cnt]=(edge){head[x],y,v,w};head[x]=cnt;
	e[++cnt]=(edge){head[y],x,0,-w};head[y]=cnt;
}

inline bool SPFA(){
	memset(d,INF,sizeof(d));
	memcpy(cur,head,sizeof(cur));
	que.push(S);d[S]=0;
	while(!que.empty()){
		int x=que.front();que.pop();in[x]=0;
		for(int i=head[x];i;i=e[i].to){
			int k=e[i].next;
			if(!e[i].v||d[k]<=d[x]+e[i].w) continue;
			d[k]=d[x]+e[i].w;
			if(!in[k]) in[k]=1,que.push(k);
		}
	}
	return d[T]!=INF;
}

inline int dfs(int x,int mi){
	if(x==T||!mi) return mi;
	int flow=0;v[x]=1;
	for(int &i=cur[x];i;i=e[i].to){
		int k=e[i].next;
		if(v[k]||!e[i].v||d[k]!=d[x]+e[i].w) continue;
		int ret=dfs(k,min(mi,e[i].v));
		flow+=ret;mi-=ret;
		e[i].v-=ret;e[i^1].v+=ret;
		ans+=ret*e[i].w;
		if(!mi) break;
	}
	v[x]=0;
	return flow;
}

inline void DINIC(){
	while(SPFA()) dfs(S,INF);
}

int main(){
	n=read()+2;V=read();S=n*2+10;T=S+1;
	a[1].x=read();a[2].x=read();
	for(int i=3;i<=n;i++) a[i].x=read(),a[i].t=read(),a[i].p=read();
	for(int i=1;i<=n;i++) G[i].reset();
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			if(a[i].t<a[j].t&&(abs(a[i].x-a[j].x)<=V*(a[j].t-a[i].t))) G[i].set(j,1);
	for(int i=1;i<=n;i++){
		ret.reset();
		for(int j=1;j<=n;j++)
			if(G[i][j]&&!ret[j]) add(i+n,j,INF,0),ret|=G[j];		
	}
	for(int i=1;i<=n;i++){
		add(i,i+n,1,-a[i].p);
		add(i,i+n,INF,0);
	}
	add(S,1,1,0);add(S,2,1,0);
	for(int i=1;i<=n;i++) add(i+n,T,INF,0);
	DINIC();
	printf("%d\n",-ans);
	return 0;
}