【BZOJ4276】[ONTAK2015]Bajtman i Okrągły Robin

2016.03.22 15:07 Tue | 47次阅读 | 旧日oi | 固定链接 | 源码

题解

线段树优化加边+费用流

对于每个时间间隔,和汇点连一条容量1的边,代表可以制止一个人。
对于每一个人,建一个点,和源点连容量1,费用c的边,对于这个人的a,b,对a到b-1这些点连容量1,费用0的边。
然后跑最大费用最大流就行了。
裸加边边数太大,用线段树优化一下就好了。
据说还有贪心做法……

mycode

#include <bits/stdc++.h>
using namespace std;
#define N 100005
#define inf 0x3f3f3f3f
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
int n,tot,S,T;
int no[N];
int h[N],tp=1;
struct edge{int to,next,val,cost;}e[3000005];
void ae(int u,int v,int w,int c){e[++tp].to=v;e[tp].next=h[u];e[tp].val=w;e[tp].cost=c;h[u]=tp;}
void add(int u,int v,int w,int c){ae(u,v,w,c);ae(v,u,0,-c);}
int build(int l,int r,int rt)
{
    if(l==r) return no[rt]=l;
    int mid=(l+r)>>1;
    int x=build(lson),y=build(rson);
    no[rt]=++tot;
    add(no[rt],x,inf,0);add(no[rt],y,inf,0);
    return no[rt];
}
void ins(int l,int r,int rt,int L,int R,int c)
{
    if(L==l&&R==r) {add(c,no[rt],1,0);return;}
    int mid=(l+r)>>1;
    if(R<=mid) ins(lson,L,R,c);
    else if(L>mid) ins(rson,L,R,c);
    else ins(lson,L,mid,c),ins(rson,mid+1,R,c);
}
queue<int> q;
int fr[N],fa[N],dis[N];
bool vis[N];
bool spfa()
{
    memset(dis,0x3f,sizeof(dis));dis[S]=0;
    q.push(S);
    while(!q.empty())
    {
        int u=q.front();q.pop();vis[u]=0;
        for(int v,i=h[u];i;i=e[i].next)
        if(e[i].val&&dis[v=e[i].to]>dis[u]+e[i].cost)
        {
            dis[v]=dis[u]+e[i].cost;
            fa[v]=u;fr[v]=i;
            if(!vis[v]) 
            {
                vis[v]=1;
                q.push(v);
            }
        }
    }
    return dis[T]<0x3f3f3f3f;
}
int dinic()
{
    int ret=0;
    while(spfa())
    {   
        ret+=dis[T];
        int now=T;
        while(now)
        {
            e[fr[now]].val--;
            e[fr[now]^1].val++;
            now=fa[now];
        }
    }
    return ret;
}
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("tt.in","r",stdin);
    #endif
    cin>>n;
    tot=n;
    build(1,n-1,1);
    for(int a,b,c,i=1;i<=n;i++)
    {
        scanf("%d%d%d",&a,&b,&c);
        add(S,++tot,1,-c);
        ins(1,n-1,1,a,b-1,tot);
    }
    T=++tot;
    for(int i=1;i<=n;i++) add(i,T,1,0);
    printf("%d\n",-dinic());
}