收获挺大的一道题。
这里的限制大小可以做差分约束，从$y o x$连$1$，表示$yle x-1$即$y<x$，然后跑最长路求解。
但是，如果这样每次$k+1$个小区间每个点都向$k$个断点连边显然爆炸。。考虑优化建边。
发现这里是每个小区间各点连边，所以可以线段树优化，不过每个小区间都要向$k$个点连边还是爆炸，这时候，考虑一种类似于线段树建边里面区间向区间的连边方式：这一边的各个拆分的小区间向一个虚点连边，这个虚点再向另一个区间拆分的小区间连边，保证了边数=区间数=$log$级别。那这里也类似，只要把$k+1$小段每一段的拆分区间全连上虚点，然后虚点连向$k$个点就行了，本质还是线段树建边的类比。由于保证了$sum k$，所以边数在$sum klog n$级别。
然后，这样一张图是和原图等价的，这时我们要做一个差分约束的求解。不过，注意到，只要这里面出现了环，那肯定是正环（因为线段树图和原图等价，原图全是$1$边），肯定就无解。如果没有环，那么就是个DAG，这时我们并不用很蠢的跑spfa（因为容易被卡，比如说链），直接拓扑排序更新max就行了。最后注意一下不合法（超过$1e9$或超过原来给定值）就行了。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<cmath> 6 #include<queue> 7 #define mst(x) memset(x,0,sizeof x) 8 #define dbg(x) cerr << #x << " = " << x <<endl 9 #define dbg2(x,y) cerr<< #x <<" = "<< x <<" "<< #y <<" = "<< y <<endl 10 using namespace std; 11 typedef long long ll; 12 typedef double db; 13 typedef pair<int,int> pii; 14 template<typename T>inline T _min(T A,T B){return A<B?A:B;} 15 template<typename T>inline T _max(T A,T B){return A>B?A:B;} 16 template<typename T>inline char MIN(T&A,T B){return A>B?(A=B,1):0;} 17 template<typename T>inline char MAX(T&A,T B){return A<B?(A=B,1):0;} 18 template<typename T>inline void _swap(T&A,T&B){A^=B^=A^=B;} 19 template<typename T>inline T read(T&x){ 20 x=0;int f=0;char c;while(!isdigit(c=getchar()))if(c=='-')f=1; 21 while(isdigit(c))x=x*10+(c&15),c=getchar();return f?x=-x:x; 22 } 23 const int N=1e5+7; 24 int org[N],val[N<<2],deg[N<<2]; 25 int n,s,m,cnt,res; 26 struct thxorz{ 27 int head[N<<2],nxt[N*100],to[N*100],tot; 28 bool w[N*100]; 29 inline void add(int x,int y,int z){to[++tot]=y,nxt[tot]=head[x],head[x]=tot,w[tot]=z,++deg[y];} 30 }G; 31 struct SGT{ 32 int id[N<<2]; 33 #define lc i<<1 34 #define rc i<<1|1 35 void build(int i,int L,int R){ 36 if(L==R){id[i]=L;return;} 37 int mid=L+R>>1;id[i]=++cnt; 38 build(lc,L,mid),build(rc,mid+1,R); 39 G.add(id[lc],id[i],0),G.add(id[rc],id[i],0); 40 } 41 void update(int i,int L,int R,int ql,int qr){ 42 if(ql<=L&&qr>=R){G.add(id[i],cnt,0);return;} 43 int mid=L+R>>1; 44 if(ql<=mid)update(lc,L,mid,ql,qr); 45 if(qr>mid)update(rc,mid+1,R,ql,qr); 46 } 47 }T; 48 queue<int> q; 49 #define y G.to[j] 50 inline void topo(){ 51 for(register int i=1;i<=n;++i)if(!deg[i])q.push(i);//dbg(i); 52 while(!q.empty()){ 53 int x=q.front();q.pop();++res; 54 for(register int j=G.head[x];j;j=G.nxt[j]){ 55 MAX(val[y],val[x]+G.w[j]);//mistake 56 if(!(--deg[y]))q.push(y); 57 } 58 } 59 } 60 #undef y 61 int main(){//freopen("test.in","r",stdin);//freopen("test.ans","w",stdout); 62 cnt=read(n),read(s),read(m); 63 fill(val+1,val+n+n+m+1,1); 64 for(register int i=1,x;i<=s;++i)read(x),val[x]=read(org[x]); 65 T.build(1,1,n); 66 for(register int i=1,l,r,k;i<=m;++i){ 67 read(l),read(r),read(k);++cnt; 68 for(register int j=1,x,las=l-1;j<=k;++j,las=x){ 69 read(x);G.add(cnt,x,1); 70 if(las+1<x)T.update(1,1,n,las+1,x-1); 71 if(j==k&&x<r)T.update(1,1,n,x+1,r); 72 } 73 } 74 topo(); 75 if(res<cnt){puts("NIE");return 0;} 76 for(register int i=1;i<=n;++i)if(val[i]>1e9||org[i]&&val[i]>org[i]){puts("NIE");return 0;} 77 puts("TAK"); 78 for(register int i=1;i<=n;++i)printf("%d%c",val[i]," "[i==n]); 79 return 0; 80 }
这题给了我一点启示。。
首先，区间连边，铁定是要线段树优化的。。只是有时候可能并不是那么显然，所以就要靠改造。。
然后，这个差分约束求解，并不是非要跑spfa的，如果原图是DAG，可以拓扑，这一点再拓展一下，就可以线性求全正权图的差分约束了，update了一下这篇。BZOJ2330 糖果[差分约束方案+spfa?/tarjan]