1 条题解
-
1
#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
- 上传者