bzoj 4383 [POI2015]Pustynia

LINK：POI2015 Pustynia

题意不再说 比余下的数字要大 并且判断是否有解 且输出方案。

考虑差分约束模型。对于连边 由于每次的区间过大我们不可能暴力的去连边 所以考虑线段树优化建图。

复杂度：由于\(\sum k\leq 3*10^5\) 所以最多 Klogn条边 不过每次连边需要新建一个点 都是在可接受的范围之内。

考虑如何判断无解 对于 a>b 可以转换成 a>=b+1 变化一下形势 b<=a-1 a向b连一条边 这样做在输出方案好像会很别扭。

就原来的形式 a>=b+1 b向a连边 表示a至少是要>=b+1 我们不能跑spfa了 图过大。

但是考虑这张图的特殊性 这是一个有向无环图 如果有环那么必然无解。

考虑最后如何构造解 我们正向的topsort一下 然后类似dp的形式 求出解即可。

当然最后还需要判断值域是否合适。

const int MAXN=100010,maxn=2000010;
int n,m,v,flag,cnt,len,root;
int a[MAXN],f[maxn],q[maxn];
int lin[maxn],ver[maxn],nex[maxn],e[maxn],ru[maxn];
struct wy{int l,r;}t[MAXN<<2];
inline void add(int x,int y,int z)
{
    ver[++len]=y;
    nex[len]=lin[x];
    lin[x]=len;
    e[len]=z;
    ++ru[y];
}
inline void build(int &p,int l,int r)
{
    p=++cnt;
    if(l==r){add(p,l,0);return;}
    int mid=(l+r)>>1;
    build(l(p),l,mid);
    build(r(p),mid+1,r);
    add(p,l(p),0);add(p,r(p),0);
}
inline void change(int p,int l,int r,int L,int R,int x)
{
    if(L>R)return;
    if(L<=l&&R>=r){add(x,p,1);return;}
    int mid=(l+r)>>1;
    if(L<=mid)change(l(p),l,mid,L,R,x);
    if(R>mid)change(r(p),mid+1,r,L,R,x);
}
inline void topsort()
{
    int l=0,r=0;
    for(int i=1;i<=cnt;++i)
    {
        f[i]=INF;
        if(!ru[i])q[++r]=i;
    }
    while(++l<=r)
    {
        int x=q[l];
        if(f[x]<1){flag=1;return;}
        if(x<=n&&a[x])
        {
            if(f[x]<a[x]){flag=1;return;}
            else f[x]=a[x];
        }
        for(int i=lin[x];i;i=nex[i])
        {
            int tn=ver[i];
            f[tn]=min(f[tn],f[x]-e[i]);
            --ru[tn];if(!ru[tn])q[++r]=tn;
        }
    }
    for(int i=1;i<=cnt;++i)if(ru[i])flag=1;
}
int main()
{
    freopen("1.in","r",stdin);
    get(n);get(v);get(m);
    for(int i=1;i<=v;++i)
    {
        int x;
        get(x);get(a[x]);
        if(a[x]>INF)flag=1;
    }
    if(flag){puts("NIE");return 0;}
    cnt=n;build(root,1,n);
    rep(1,m,i)
    {
        int x,y,k,p;
        get(x);get(y);get(k);
        ++cnt;
        rep(1,k,j)
        {
            get(p);
            add(p,cnt,0);
            if(j==1){if(x<p)change(root,1,n,x,p-1,cnt);}
            else if(x+1!=p)change(root,1,n,x+1,p-1,cnt);
            x=p;
        }
        if(p<y)change(root,1,n,p+1,y,cnt);
    }
    topsort();
    if(flag){puts("NIE");return 0;}
    puts("TAK");
    rep(1,n,i)printf("%d ",f[i]);
    return 0;
}

bzoj 4383 [POI2015]Pustynia

原文：https://www.cnblogs.com/chdy/p/12466623.html