P14978 [USACO26JAN1] Mooclear Reactor S题解

zpy12345 · 2026-01-23 16:02:44 · 题解

[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;
}