1 条题解

  • 1
    @ 2022-8-25 9:44:34
    #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;
    }
    
    • 1

    信息

    ID
    4190
    时间
    1000ms
    内存
    500MiB
    难度
    6
    标签
    递交数
    2
    已通过
    2
    上传者