区间加边，想到线段树优化
之前写过线段树优化最短路
那就YY一下线段树优化网络流
听说还可以贪心 QwQ
这个题多路增广优化不是很明显
喜闻乐见1A了
#include<cmath> #include<ctime> #include<cstdio> #include<cstring> #include<cstdlib> #include<complex> #include<iostream> #include<algorithm> #include<iomanip> #include<vector> #include<string> #include<bitset> #include<queue> #include<map> #include<set> using namespace std; typedef long long ll; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch<='9'&&ch>='0'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();} return x*f; } void print(ll x) {if(x<0)putchar('-'),x=-x;if(x>=10)print(x/10);putchar(x+'0');} const int N=75010,inf=0X3f3f3f3f; int n,m,root,cnt,S,T=N-1; int ecnt=1,last[N]; struct EDGE{int to,nt,val,ct;}e[N<<3]; inline void readd(int u,int v,int val,int ct) {e[++ecnt]=(EDGE){v,last[u],val,ct};last[u]=ecnt;} inline void add(int u,int v,int val,int ct) {readd(u,v,val,ct);readd(v,u,0,-ct);} struct seg_tree{int l,r,ls,rs;}tr[N]; void build(int &k,int l,int r,int fa) { k=++cnt; tr[k].l=l;tr[k].r=r; add(fa,k,r-l+1,0); if(l==r)return ; int mid=l+r>>1; build(tr[k].ls,l,mid,k); build(tr[k].rs,mid+1,r,k); } void modify(int k,int x,int y,int pos) { int l=tr[k].l,r=tr[k].r; if(l>=x&&r<=y){add(k,pos,1,0);return ;} int mid=l+r>>1; if(y<=mid)modify(tr[k].ls,x,y,pos); else if(x>mid)modify(tr[k].rs,x,y,pos); else modify(tr[k].ls,x,y,pos),modify(tr[k].rs,x,y,pos); } bool inq[N],vis[N]; int dis[N],q[N]; bool spfa() { memset(dis,-1,sizeof(dis)); memset(inq,0,sizeof(inq)); memset(vis,0,sizeof(vis)); register int i,j,u,head=0,tail=1; dis[S]=0;inq[0]=1;q[0]=0; while(head!=tail) { u=q[head++];if(!(head^N))head=0;inq[u]=0; for(i=last[u];i;i=e[i].nt) if(e[i].val&&dis[e[i].to]<dis[u]+e[i].ct) { dis[e[i].to]=dis[u]+e[i].ct; if(!inq[e[i].to]) {q[tail++]=e[i].to;inq[e[i].to]=1;if(!(tail^N))tail=0;} } } return dis[T]!=-1; } int ans=0; int dfs(int u,int lim) { if(u==T){ans+=dis[u]*lim;return lim;} vis[u]=1;int res=0; register int i,tmp; for(i=last[u];i;i=e[i].nt) if(e[i].val&&dis[e[i].to]==dis[u]+e[i].ct&&!vis[e[i].to]) { tmp=dfs(e[i].to,min(e[i].val,lim)); e[i].val-=tmp,e[i^1].val+=tmp;lim-=tmp;res+=tmp; if(!lim)break; } if(!res)dis[u]=-1; return res; } void maxcf() {while(spfa())dfs(S,inf);} int main() { n=read(); register int i; static int l[N],r[N],ct[N]; for(i=1;i<=n;i++){l[i]=read();r[i]=read();ct[i]=read();m=max(r[i],m);} build(root,1,m-1,0); for(i=1;i<=n;i++) { modify(1,l[i],r[i]-1,cnt+i); add(cnt+i,cnt+i+n,1,ct[i]);add(cnt+i+n,T,1,0); } maxcf();print(ans);puts(""); return 0; } /* 4 1 4 40 2 4 10 2 3 30 1 3 20 90 */