[BZOJ4383/Luogu3588][POI2015]Pustynia(差分约束,线段树,拓扑)

发布于 2018-05-07  146 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ4383/Luogu3588][POI2015]Pustynia(差分约束,线段树,拓扑)

Description

给定一,个长度为n的正整数序列a,每个数都在1到$10^9$范围内,告诉你其中s个数,并给出m条信息,每条信息包含三个数l,r,k以及接下来k个正整数,表示$a[l],a[l+1],...,a[r-1],a[r]$里这k个数中的任意一个都比任意一个剩下的r-l+1-k个数大(严格大于,即没有等号)。请任意构造出一组满足条件的方案,或者判断无解。

Tag

差分约束,线段树,拓扑

解决思路

$$-$$
题目中给出是若干点大于另外一些点的限制,那么也就是一些点大于等于另一些点$+1$。按照差分约束的思想,对于$x>y$,连边$y->x$,边权为$1$。
但是这样连边是$O(n^2)$的。对于区间$[l,r]$中的$k$个点,把这个区间最多分成$k+1$个区间。从区间着手,我们可以想到用线段树优化连边。
具体来说,对于每一组$(l,r,k)$,新建一个点$node$,从$node$分别向这$k$个点连权为$1$的边,表示这$k$个点比这个新建点大。那么接下来的任务就是把剩下的$(r-l+1)-k$个点连到$node$上,权为$0$。考虑到区间,所以在把每一个区间拆分成$log$个放到线段树上,从这些线段树上的点引边到$node$。注意,线段树的点也要连边,即从儿子向父亲连权为$0$的边
那么,用拓扑排序求一边,得到每一个点的权值下界。无解有三种情况,一是出现环,无法完成拓扑;二是某个点本来给定了权值,但这个给定的权值比得到的下界还要小,这时也无解;三是注意到题目中给出的值域要求在$1e9$内,所以若出现某个下界大于$1e9$,则也无解。

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

#define ll long long
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))
#define lson (now<<1)
#define rson (lson|1)

const int maxN=101000;
const int maxQ=201000;
const int maxNode=(maxN<<2)+maxQ;
const int maxM=maxNode*10;
const int inf=2147483648;

int n,m,nodecnt;
int edgecnt=0,Head[maxNode],Next[maxM],V[maxM],W[maxM];
int Id[maxN],Input[maxN];
int Val[maxNode],Min[maxNode];
int Degree[maxNode],Queue[maxNode];

void Build(int now,int l,int r);
void Add_Edge(int u,int v,int w);
void Query(int now,int l,int r,int ql,int qr,int node);

int main()
{
    mem(Head,-1);mem(Val,-1);
    int know;
    scanf("%d%d%d",&n,&know,&m);
    Build(1,1,n);//初始化线段树上的连边,同时记录下每一个序列中的编号对应的线段树节点位置
    for (int i=1;i<=know;i++)
    {
        int pos,key;scanf("%d%d",&pos,&key);
        Val[Id[pos]]=Min[Id[pos]]=key;//对于已知的,直接赋值
    }
    for (int i=1;i<=m;i++)
    {
        int l,r,k;scanf("%d%d%d",&l,&r,&k);
        nodecnt++;
        for (int j=1;j<=k;j++) scanf("%d",&Input[j]);
        for (int j=1;j<=k;j++) Add_Edge(nodecnt,Id[Input[j]],1);//从新建点向这k个点连边
        Input[0]=l-1;Input[k+1]=r+1;
        for (int j=1;j<=k+1;j++) if ((Input[j-1]+1!=Input[j])&&(Input[j-1]!=Input[j])) Query(1,1,n,Input[j-1]+1,Input[j]-1,nodecnt);//从线段树节点连边
    }
    int h=0,t=0;//拓扑排序
    for (int i=1;i<=nodecnt;i++) if (Degree[i]==0) Queue[++h]=i;
    bool flag=1;
    do
    {
        int u=Queue[++t];
        Min[u]=max(Min[u],1);//注意值域下界为1
        if (Val[u]==-1) Val[u]=Min[u];
        else if (Val[u]<Min[u]){//原来有值,但小于下界,则无解
            flag=0;break;
        }
        for (int i=Head[u];i!=-1;i=Next[i])
        {
            Degree[V[i]]--;Min[V[i]]=max(Min[V[i]],Val[u]+W[i]);
            if (Degree[V[i]]==0) Queue[++h]=V[i];
        }
    }
    while (t!=h);
    for (int i=1;i<=n;i++) if (Val[Id[i]]>1e9) flag=0;//判断值域是否超过上限制
    if ((t!=nodecnt)||(flag==0)) printf("NIE\n");
    else
    {
        printf("TAK\n");
        for (int i=1;i<=n;i++) printf("%d ",Val[Id[i]]);
        printf("\n");
    }
    return 0;
}

void Build(int now,int l,int r)
{
    nodecnt=max(nodecnt,now);
    if (l==r){
        Id[l]=now;return;
    }
    int mid=(l+r)>>1;
    Add_Edge(lson,now,0);Add_Edge(rson,now,0);
    Build(lson,l,mid);Build(rson,mid+1,r);
    return;
}

void Add_Edge(int u,int v,int w)
{
    Degree[v]++;
    edgecnt++;Next[edgecnt]=Head[u];Head[u]=edgecnt;V[edgecnt]=v;W[edgecnt]=w;
    return;
}

void Query(int now,int l,int r,int ql,int qr,int node)//从线段树[ql,qr]区间的点连到node
{
    if ((l==ql)&&(r==qr)){
        Add_Edge(now,node,0);return;
    }
    int mid=(l+r)>>1;
    if (qr<=mid) Query(lson,l,mid,ql,qr,node);
    else if (ql>=mid+1) Query(rson,mid+1,r,ql,qr,node);
    else
    {
        Query(lson,l,mid,ql,mid,node);
        Query(rson,mid+1,r,mid+1,qr,node);
    }
    return;
}

$$-$$

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ4383/Luogu3588][POI2015]Pustynia(差分约束,线段树,拓扑)


HNCJ OIer