洛谷P3588 [POI2015]PUS

sol：说了是线段树优化建图的模板。。。

就是把一整个区间的点连到一个点上,然后用那个点来连需要连一整个区间的点就可以了,就把边的条数优化成n*log(n)了

#include <queue>

#include <cstdio>

#include <iostream>

using namespace std;

const int N=,M=;

int n,s,m,tot=,Next[M],to[M],val[M],head[M],cnt=,in1[N],dis[N],a[N],arr[N];

inline void add(int x,int y,int z){Next[++tot]=head[x];to[tot]=y;val[tot]=z;head[x]=tot;in1[y]++;}

struct segtree{int l,r,num;inline int mid(){return (l+r)>>;}}Tree[N<<];

#define c1 x<<1

#define c2 x<<1|1

inline void build(int l,int r,int x)

{

  Tree[x].l=l;Tree[x].r=r; if(l==r){Tree[x].num=l;return;} Tree[x].num=++cnt; int mid=(l+r)>>;

  build(l,mid,c1); build(mid+,r,c2); add(Tree[c1].num,Tree[x].num,); add(Tree[c2].num,Tree[x].num,);

}

inline void ins(int l,int r,int x,int v)

{

  if(Tree[x].l==l&&Tree[x].r==r){add(Tree[x].num,v,);return;} int mid=Tree[x].mid();

  if(r<=mid)ins(l,r,c1,v);else if(l>mid)ins(l,r,c2,v);else ins(l,mid,c1,v),ins(mid+,r,c2,v);

}

inline bool Kahn()

{

  int i,x; queue<int>q; for(i=;i<=cnt;i++){if(!in1[i])q.push(i);if(!dis[i])dis[i]=;arr[i]=;}

  while(!q.empty())

  {

    x=q.front(); q.pop(); arr[x]=;

    for(i=head[x];i;i=Next[i])

    {

      dis[to[i]]=max(dis[to[i]],dis[x]+val[i]); if(a[to[i]]&&dis[to[i]]>a[to[i]]){printf("NIE\n");return ;} if(!--in1[to[i]])q.push(to[i]);

    }

  }for(i=;i<=cnt;i++)if(!arr[i]||dis[i]>){printf("NIE\n");return ;} return ;

}

int main()

{

  int i,j,x,y,l,r,k,pre; scanf("%d%d%d",&n,&s,&m); cnt=n; build(,n,); for(i=;i<=s;i++){scanf("%d%d",&x,&y);a[x]=dis[x]=y;}

  for(i=;i<=m;i++)

  {

    scanf("%d%d%d",&l,&r,&k); pre=l-; cnt++;

    for(j=;j<=k;j++)

    {

        scanf("%d",&x); add(cnt,x,); if(x>pre+)ins(pre+,x-,,cnt); pre=x;

    }if(x<r)ins(x+,r,,cnt);

  }if(!Kahn())return ; printf("TAK\n"); for(i=;i<=n;i++)printf("%d ",dis[i]);printf("\n");

}