登录
← 返回首页 | 代码片段 › 3 图论 › 3.6 负环与差分约束 › 负环与差分约束 / 搜索
JSON MD

3.6 负环与差分约束

01分数规划 观光奶牛Sightseeing Cows
43 行
CPP JSON
【01分数规划(观光奶牛Sightseeing Cows)】 负环检测与差分约束系统模板,基于 SPFA/Bellman-Ford。 核心函数: void in(Re &x) — 核心算法函数 void add(Re x,Re y,Re z) — 加法更新 int SPFA(Re st,double mid) — SPFA最短路 核心结构体:QAQ 关键配置: N=1e4+5,M=5e5+5,inf=2e9
C++ 42 行 CPP
#include<cstring>
#include<cstdio>
#include<queue>
#define Re register int
using namespace std;
const int N=1e4+5,M=5e5+5,inf=2e9;
int x,y,z,n,m,o,T,to,A[N],cha[N],pan[N],head[N];double dis[N];
struct QAQ{int w,to,next;}a[M<<1];queue<int>Q;
inline void in(Re &x){
    Re fu=0;x=0;char ch=getchar();
    while(ch<'0'||ch>'9')fu|=ch=='-',ch=getchar();
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    x=fu?-x:x;
}
inline void add(Re x,Re y,Re z){a[++o].to=y,a[o].w=z,a[o].next=head[x],head[x]=o;}
inline int SPFA(Re st,double mid){
    for(Re i=0;i<=n;++i)dis[i]=-inf,pan[i]=cha[i]=0;
    dis[st]=0,cha[st]=pan[st]=1,Q.push(st);
    while(!Q.empty()){
        x=Q.front(),Q.pop();
        pan[x]=0;
        for(Re i=head[x];i;i=a[i].next)
            if(dis[to=a[i].to]<dis[x]+A[x]-mid*a[i].w){
                dis[to]=dis[x]+A[x]-mid*a[i].w;
                if(++cha[to]>n)return 1;
                if(!pan[to])Q.push(to);
            }
    }
    return 0;
}
int main(){
    in(n),in(m);
    for(Re i=1;i<=n;++i)in(A[i]);
    while(m--)in(x),in(y),in(z),add(x,y,z);
    double l=0,r=1000000,mid;
    while(r-l>1e-4){
        mid=(l+r)/2;
        if(SPFA(1,mid))l=mid;
        else r=mid;
    }
    printf("%.2lf",l);
}
判负环 SPFA
42 行
CPP JSON
【判负环(SPFA)】 负环检测与差分约束系统模板,基于 SPFA/Bellman-Ford。 核心函数: void add(Re x,Re y,Re z) — 加法更新 void in(Re &x) — 核心算法函数 int SPFA(Re st) — SPFA最短路 核心结构体:QAQ 关键配置: N=2003,M=3e5+3,inf=2e9 说明:if(++chu[to]>=n)return 1;
C++ 41 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#define LL long long
#define Re register int
using namespace std;
const int N=2003,M=3e5+3,inf=2e9;
int n,m,x,y,z,o,T,pan[N],chu[N],dis[N],head[N];queue<int>Q;
struct QAQ{int w,to,next;}a[M<<1];
inline void add(Re x,Re y,Re z){a[++o].w=z,a[o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline int SPFA(Re st){
    for(Re i=1;i<=n;++i)dis[i]=inf,chu[i]=pan[i]=0;
    while(!Q.empty())Q.pop();
    Q.push(st),dis[st]=0,chu[st]=0,pan[st]=1;
    while(!Q.empty()){
        Re x=Q.front();Q.pop();pan[x]=0;
        for(Re i=head[x],to;i;i=a[i].next)
            if(dis[to=a[i].to]>dis[x]+a[i].w){
                dis[to]=dis[x]+a[i].w;
                if((chu[to]=chu[x]+1)>=n)return 1;
//                if(++chu[to]>=n)return 1;
                if(!pan[to])pan[to]=1,Q.push(to);
            }
    }
    return 0;
}
int main(){
    in(T);
    while(T--){
        in(n),in(m),memset(head,0,sizeof(head)),o=0;
        while(m--){in(x),in(y),in(z),add(x,y,z);if(z>=0)add(y,x,z);}
        puts(SPFA(1)?"YES":"NO");
    }
}
差分约束系统 糖果
49 行
CPP JSON
【差分约束系统(糖果)】 负环检测与差分约束系统模板,基于 SPFA/Bellman-Ford。 核心函数: void add(Re x,Re y,Re z) — 加法更新 void in(Re &x) — 核心算法函数 int SPFA(Re st,Re ed) — SPFA最短路 核心结构体:QAQ 关键配置: N=1e5+5,M=3e5+5,inf=2e9
C++ 48 行 CPP
#include<cstring>
#include<cstdio>
#include<queue>
#define Re register int
using namespace std;
const int N=1e5+5,M=3e5+5,inf=2e9;
int x,y,n,m,o,op,chu[N],dis[N],pan[N],head[N];long long ans;
struct QAQ{int w,to,next;}a[M];queue<int>Q;
inline void add(Re x,Re y,Re z){a[++o].to=y,a[o].w=z,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
	Re fu=0;x=0;char ch=getchar();
	while(ch<'0'||ch>'9')fu|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	x=fu?-x:x;
}
inline int SPFA(Re st,Re ed){
	for(Re i=0;i<=n;++i)dis[i]=-inf,chu[i]=0;
	dis[st]=0,chu[st]=pan[st]=1,Q.push(st);
	while(!Q.empty()){
		x=Q.front(),Q.pop();
		pan[x]=0;
		for(Re i=head[x],to;i;i=a[i].next)
			if(dis[to=a[i].to]<dis[x]+a[i].w){
				dis[to]=dis[x]+a[i].w;
				if((chu[to]=chu[x]+1)>n+1)return 1;
				if(!pan[to])pan[to]=1,Q.push(to);
			}
	}
	return 0;
}
int main(){
	in(n),in(m);
	for(Re i=n;i>=1;--i)add(0,i,1); //a[i]>=a[0]=1,a[i]-a[0]>=1
	while(m--){
		in(op),in(x),in(y);
		if(op<2)add(y,x,0),add(x,y,0);
		else if(op<3)add(x,y,1);//a[x]<a[y]: a[y]-a[x]>=1
		else if(op<4)add(y,x,0);//a[x]>=a[y]: a[x]-a[y]>=0
		else if(op<5)add(y,x,1);//a[x]>a[y]: a[x]-a[y]>=1
		else add(x,y,0);//a[x]<=a[y]: a[y]-a[x]>=0
		if(!(op%2)&&x==y){puts("-1");return 0;}
	}
	if(SPFA(0,n))puts("-1");
	else{
		for(Re i=1;i<=n;++i)ans+=dis[i];
		printf("%lld",ans);
	}
}
已复制