递归型SPFA+二分答案 || 负环 || BZOJ 4773

题解：

基本思路是二分答案，每次用Dfs型SPFA验证该答案是否合法。

一点细节我注释在代码里了。

代码：

 #include<cstdio>

 #include<cstring>

 using namespace std;

 inline int rd(){

     int x=,f=; char c=getchar();

     while(c<''||c>''){if(c=='-')f=-; c=getchar();}

     while(c>=''&&c<=''){x=x*+c-''; c=getchar();}

     return f*x;

 }

 const int maxn=,maxm=*,inf=(<<)-;

 int N,M,edge_head[maxn],num_edge=,u,v,w,Dis[maxn];

 bool vis[maxn],flag;

 struct Edge{ int to,nx,dis; }edge[maxm];

 inline void Add_edge(int from,int to,int dis){

     edge[++num_edge].nx=edge_head[from];

     edge[num_edge].to=to;

     edge[num_edge].dis=dis;

     edge_head[from]=num_edge;

     return;

 }

 inline void SPFA(int x,int now,int Limit){

 //判断是否存在当前位于x，现在已经用了now个点，点数不超过Limit的负环

     if(flag) return;

     for(int i=edge_head[x];i;i=edge[i].nx){

         int y=edge[i].to;

         if(Dis[y]>=Dis[x]+edge[i].dis){

             if(vis[y]){

                 flag=;

                 return;

             }

             else if(now+<=Limit){

                 vis[y]=;

                 Dis[y]=Dis[x]+edge[i].dis;

                 SPFA(y,now+,Limit);

                 vis[y]=;

                 //这里的Dis[y]不用回溯，其实是一种剪枝

             }

         }

     }

     return;

 }

 int main(){

     N=rd(); M=rd();

     for(int i=;i<=M;i++){

         u=rd(); v=rd(); w=rd();

         Add_edge(u,v,w);

     }

     flag=;

     for(int i=;i<=N;i++){

         memset(vis,,sizeof(vis));

         memset(Dis,,sizeof(Dis));

         vis[i]=;

         SPFA(i,,N);

         if(flag) break;

     }

     if(flag==){

         printf("0\n");

         return ;

     }

     int l=,r=N;

     while(l<=r){

         int mid=(l+r)>>;

         flag=;

         for(int i=;i<=N;i++){

             memset(vis,,sizeof(vis));

             memset(Dis,,sizeof(Dis));

             vis[i]=;

             SPFA(i,,mid);

             if(flag){

                 r=mid-;

                 break;

             }

         }

         if(!flag) l=mid+;

     }

     printf("%d\n",l);

     return ;

 }

---

By:AlenaNuna