[USACO26JAN1] Mooclear Reactor S
思路
将限制建双向边，设一个联通块的根为r t rtrt，则每个a i a_iai一定可以表示为a i = k × a r t + b a_i=k\times a_{rt}+bai=k×art+b，其中k ∈ { − 1 , 1 } k\in \left \{ -1,1 \right \}k∈{−1,1}。如果有环，那么每个a i a_iai的值就确定了，检查一下有多少a i a_iai产生动力即可。否则我们解出满足l i ≤ a i ≤ r i l_i\le a_i \le r_ili≤ai≤ri的a r t a_{rt}art取值范围。现在问题转换为：有若干线段，求一个点使包含这个点的线段数量最多。扫描线即可，时间复杂度O ( n log n ) O(n\log_{}{n})O(nlogn)，瓶颈在于排序。
代码
压行导致代码有点猎奇。
#include<bits/stdc++.h>usingnamespacestd;constintN=2e5+5;intt,n,m,cnt,l[N],r[N],tp[N],k[N],to[N<<1],nxt[N<<1],w[N<<1];voidadd(intx,inty,intz){to[++cnt]=y,w[cnt]=z,nxt[cnt]=tp[x],tp[x]=cnt;}boolbj[N],bjj[N],flag;longlongb[N],val;voidbfs(intx){queue<int>q;q.push(x),bj[x]=1,b[x]=0,k[x]=1,val=1000000000000000;while(!q.empty()){intx=q.front();q.pop();for(inti=tp[x];i;i=nxt[i])if(!bj[to[i]])b[to[i]]=w[i]-b[x],k[to[i]]=-k[x],bj[to[i]]=1,q.push(to[i]);elseif(!(k[to[i]]+k[x])&&b[to[i]]+b[x]!=w[i]||(k[to[i]]+k[x])&&(w[i]-b[x]-b[to[i]])%(k[x]+k[to[i]])||(k[to[i]]+k[x])&&val!=1000000000000000&&val!=(w[i]-b[x]-b[to[i]])/(k[x]+k[to[i]]))flag=1;elseif(k[to[i]]+k[x])val=(w[i]-b[x]-b[to[i]])/(k[x]+k[to[i]]);}}vector<pair<longlong,int>>sol;voiddfs1(intx){longlongll=k[x]==1?l[x]-b[x]:b[x]-r[x],rr=k[x]==1?r[x]-b[x]:b[x]-l[x];bjj[x]=1,sol.push_back({ll,1}),sol.push_back({rr+1,-1});for(inti=tp[x];i;i=nxt[i])if(!bjj[to[i]])dfs1(to[i]);}intdfs2(intx){bjj[x]=1;longlongv=k[x]*val+b[x];intsiz=(v>=l[x]&&v<=r[x]);for(inti=tp[x];i;i=nxt[i])if(!bjj[to[i]])siz+=dfs2(to[i]);returnsiz;}intmain(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>t;while(t--){cnt=flag=0;cin>>n>>m;for(inti=1;i<=n;i++)cin>>l[i];for(inti=1;i<=n;i++)cin>>r[i];while(m--){intx,y,z;cin>>x>>y>>z;add(x,y,z),add(y,x,z);}intans=0;for(inti=1;i<=n;i++)if(!bj[i]){bfs(i);if(val==1000000000000000){dfs1(i),sort(sol.begin(),sol.end());intsum=0,max1=0;for(intj=0;j<sol.size();j++)sum+=sol[j].second,max1=max(max1,sum);ans+=max1,sol.clear();}elseans+=dfs2(i);}cout<<(flag?-1:ans)<<"\n";for(inti=1;i<=n;i++)tp[i]=bj[i]=bjj[i]=0;}return0;}
