详细介绍：P14978 [USACO26JAN1] Mooclear Reactor S题解

[USACO26JAN1] Mooclear Reactor S

思路

将限制建双向边，设一个联通块的根为$rt$，则每个 $a_i$一定允许表示为$a_i=k\times a_{rt}+b$，其中 $k\in \left\{-1,1\right\}$。如果有环，那么每个$a_i$的值就确定了，检查一下有多少$a_i$产生动力即可。否则我们解出满足$l_i\le a_i\le r_i$ 的 $a_{rt}$取值范围。现在问题转换为：有若干线段，求一个点使包含这个点的线段数量最多。扫描线即可，时间复杂度$O(n{\log }_{}n)$，瓶颈在于排序。

代码

压行导致代码有点猎奇。

#include<bits/stdc++.h>using namespace std;const int N=2e5+5;int t,n,m,cnt,l[N],r[N],tp[N],k[N],to[N<<1],nxt[N<<1],w[N<<1];void add(int x,int y,int z){to[++cnt]=y,w[cnt]=z,nxt[cnt]=tp[x],tp[x]=cnt;}bool bj[N],bjj[N],flag;long long b[N],val;void bfs(int x){queue<int> q;q.push(x),bj[x]=1,b[x]=0,k[x]=1,val=1000000000000000;while(!q.empty()){int x=q.front();q.pop();for(int i=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]);else if(!(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;else if(k[to[i]]+k[x]) val=(w[i]-b[x]-b[to[i]])/(k[x]+k[to[i]]);}}vector<pair<long long ,int> > sol;void dfs1(int x){long long ll=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(int i=tp[x];i;i=nxt[i]) if(!bjj[to[i]]) dfs1(to[i]);}int dfs2(int x){bjj[x]=1;long long v=k[x]*val+b[x];int siz=(v>=l[x]&&v<=r[x]);for(int i=tp[x];i;i=nxt[i]) if(!bjj[to[i]]) siz+=dfs2(to[i]);return siz;}int main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>t;while(t--){cnt=flag=0;cin>>n>>m;for(int i=1;i<=n;i++) cin>>l[i];for(int i=1;i<=n;i++) cin>>r[i];while(m--){int x,y,z;cin>>x>>y>>z;add(x,y,z),add(y,x,z);}int ans=0;for(int i=1;i<=n;i++)if(!bj[i]){bfs(i);if(val==1000000000000000){dfs1(i),sort(sol.begin(),sol.end());int sum=0,max1=0;for(int j=0;j<sol.size();j++) sum+=sol[j].second,max1=max(max1,sum);ans+=max1,sol.clear();}else ans+=dfs2(i);}cout<<(flag?-1:ans)<<"\n";for(int i=1;i<=n;i++) tp[i]=bj[i]=bjj[i]=0;}return 0;}