【UR #2】跳蚤公路-白红宇

【UR #2】跳蚤公路

阅读量：7044 次

发布时间：2019-06-28

本文共 4369 字，大约阅读时间需要 14 分钟。

参照yjc方法。也就是地铁环线那个题。

求每个点不在负环内的x的取值范围。然后所有1到j能到i的j的范围取交。得到答案。

每个边形如kx+b的直线，每个环也是

每个点不在负环内的x取值范围是区间，

两次二分，

第一次二分区间左端点，第二次右端点。

如果没有负环，左端点往左偏，右端点往右偏

否则，记录负环的构成：k*mid+b的k的正负，可以得到mid应该往哪里偏。

注意SPFA找负环：

记录has[x]表示到x的最短路已经经过了多少个点，

dis[x]最短路，fr[x]是最短路的前驱，pre[x]是最短路前驱指向x的边

发现has[x]>n的时候，证明出现了负环。但是x不一定在负环上！

不断跳fr[x]找到整个环重复的第一个点z。

再fr[z]找到整个环。

emmm，一个问题是，负环上的点不会被其他点松弛导致fr[*]找不到负环吗？

由于SPFA的BFS性质，以及has[x]>n才会判断出有负环，

所以整个负环上的点，在判断has[*]>n之前，要么不会被松弛、或者松弛后要么找到新的负环、要么会被这个负环再次松弛，

总之这个环确实能找出来。

代码：

目前（2019.6.17）UOJ最优解

#include
     
      #define reg register int#define il inline#define fi first#define se second#define mk(a,b) make_pair(a,b)#define numb (ch^'0')#define pb push_back#define solid const auto &#define enter cout<
      
       using namespace std;typedef long long ll;template
       
        il void rd(T &x){    char ch;x=0;bool fl=false;while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);    for(x=numb;isdigit(ch=getchar());x=x*10+numb);(fl==true)&&(x=-x);}template
        
         il void output(T x){
    if(x/10)output(x/10);putchar(x%10+'0');}template
         
          il void ot(T x){
    if(x<0) putchar('-'),x=-x;output(x);putchar(' ');}template
          
           il void prt(T a[],int st,int nd){ for(reg i=st;i<=nd;++i) ot(a[i]);putchar('\n');}namespace Modulo{const int mod=998244353;il int ad(int x,int y){ return x+y>=mod?x+y-mod:x+y;}il int sub(int x,int y){ return ad(x,mod-y);}il int mul(int x,int y){ return (ll)x*y%mod;}il void inc(int &x,int y){x=ad(x,y);}il void inc2(int &x,int y){x=mul(x,y);}il int qm(int x,int y=mod-2){ int ret=1;while(y){ if(y&1) ret=mul(x,ret);x=mul(x,x);y>>=1;}return ret;}template
           
            il int ad(const int a,const int b,const Args &...args) { return ad(ad(a,b),args...);}template
            
             il int mul(const int a,const int b,const Args &...args) { return mul(mul(a,b),args...);}}// using namespace Modulo;namespace Miracle{const int N=105;const int M=10005;const ll inf=1e14;int n,m;struct edge{ int x,y,k,b;}b[M];struct node{ int nxt,to; int k,b; ll val(ll x){ return k*x+b; }}e[2*M];int hd[N],cnt;void add(int x,int y,int k,int b){ e[++cnt].nxt=hd[x]; e[cnt].to=y; e[cnt].k=k;e[cnt].b=b; hd[x]=cnt;}int c[N],df,dfn[N],low[N];int scc;int f[N][N];int sta[N],top,in[N];int sz[N];void tarjan(int x){ dfn[x]=low[x]=++df; sta[++top]=x;in[x]=1; for(reg i=hd[x];i;i=e[i].nxt){ int y=e[i].to; if(!dfn[y]){ tarjan(y); low[x]=min(low[x],low[y]); }else if(in[y]) low[x]=min(low[x],dfn[y]); } if(low[x]==dfn[x]){ ++scc; int z; do{ z=sta[top--]; in[z]=0; c[z]=scc; ++sz[scc]; }while(z!=x); }}struct seg{ ll l,r; seg(){l=-inf,r=inf;} seg(ll le,ll ri){ l=le;r=ri; } bool empty(){ return l>r; } bool full(){ return (l==-inf)&&(r==inf); } seg friend operator &(seg a,seg b){ return seg(max(a.l,b.l),min(a.r,b.r)); } seg friend operator |(seg a,seg b){ if(a.empty()) return b; if(b.empty()) return a; return seg(min(a.l,b.l),max(a.r,b.r)); }}lim[N];ll dis[N];int pre[N];int fr[N];int has[N];queue
             
              q;bool vis[N];int spfa(int s,ll mid,int n){ //-1 need small; 1: need big ;0 ok while(!q.empty()) q.pop(); memset(dis,0x3f,sizeof dis); memset(vis,0,sizeof vis); // memset(pre,0,sizeof pre); // memset(has,0,sizeof has); dis[s]=0;has[s]=1; q.push(s); while(!q.empty()){ int x=q.front();q.pop(); // cout<<" xx "<
              
               <
               
                dis[x]+e[i].val(mid)){ dis[y]=dis[x]+e[i].val(mid); pre[y]=i; fr[y]=x; has[y]=has[x]+1; if(has[y]>n){ //has fuhuan // cout<<" fuhuan !!!"<
                
                 >1; // cout<
                 
                  <<" "<
                  
                   <<" : "<
                   
                    <
                    
                     >1; int lp=spfa(s,mid,sz[id]); if(lp==-1){ R=mid-1; }else if(lp==1){ L=mid+1; }else{ ar=mid; L=mid+1; } } // cout<<" ar "<
                     
                      <