洛谷P3588 [POI2015]PUS"/>
洛谷P3588 [POI2015]PUS
题面
sol:说了是线段树优化建图的模板。。。
就是把一整个区间的点连到一个点上,然后用那个点来连需要连一整个区间的点就可以了,就把边的条数优化成n*log(n)了
#include <queue> #include <cstdio> #include <iostream> using namespace std; const int N=500005,M=5000005; int n,s,m,tot=0,Next[M],to[M],val[M],head[M],cnt=0,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)>>1;}}Tree[N<<2]; #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)>>1;build(l,mid,c1); build(mid+1,r,c2); add(Tree[c1].num,Tree[x].num,0); add(Tree[c2].num,Tree[x].num,0); } 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,0);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+1,r,c2,v); } inline bool Kahn() {int i,x; queue<int>q; for(i=1;i<=cnt;i++){if(!in1[i])q.push(i);if(!dis[i])dis[i]=1;arr[i]=0;}while(!q.empty()){x=q.front(); q.pop(); arr[x]=1;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 0;} if(!--in1[to[i]])q.push(to[i]);}}for(i=1;i<=cnt;i++)if(!arr[i]||dis[i]>1000000000){printf("NIE\n");return 0;} return 1; } int main() {int i,j,x,y,l,r,k,pre; scanf("%d%d%d",&n,&s,&m); cnt=n; build(1,n,1); for(i=1;i<=s;i++){scanf("%d%d",&x,&y);a[x]=dis[x]=y;}for(i=1;i<=m;i++){scanf("%d%d%d",&l,&r,&k); pre=l-1; cnt++;for(j=1;j<=k;j++){scanf("%d",&x); add(cnt,x,1); if(x>pre+1)ins(pre+1,x-1,1,cnt); pre=x;}if(x<r)ins(x+1,r,1,cnt);}if(!Kahn())return 0; printf("TAK\n"); for(i=1;i<=n;i++)printf("%d ",dis[i]);printf("\n"); }View Code
转载于:.html
更多推荐
洛谷P3588 [POI2015]PUS
发布评论