套匯問題，從源點做SPFA，如果有一個點入隊次數大于v次（v表示點的個數）則圖中存在負權回路，能夠套匯，如果不存在負權回路，則判斷下源點到自身的最長路是否大于自身，使用SPFA時松弛操作需要做調整
#include<iostream>
#include<cstdio>
#include<string.h>
#include <stdlib.h>
#include <math.h>
using namespace std;
const int maxn=2000;
double dist[maxn]={0},rate[maxn][maxn]={{0}},ope[maxn][maxn]={{0}},v;
int n,m,s,cnt[maxn]={0};
bool spfa(int scr)
{
???int l=0,r=1,que[10000]={0},visit[maxn]={0},temp;
???que[++l]=scr;
???dist[scr]=v;
???cnt[scr]=1;
???while(l<=r)
??? {
???????temp=que[l++];
???????visit[temp]=0;
???????for(int i=1;i<=n;i++)
???????{
???????????if (rate[temp][i]>0 &&dist[i]<(dist[temp]-ope[temp][i])*rate[temp][i])
???????????{
???????????????dist[i]=(dist[temp]-ope[temp][i])*rate[temp][i];
??????????????? if (visit[i]==0)
???????????????{
??????????????????? visit[i]=1;
??????????????????? que[++r]=i;
??????????????????? cnt[i]++;
??????????????????? if (cnt[i]>=n)returntrue;
??????????????? }
???????????}
???????}
??? }
???return dist[s]>v;
}
int main()
{
???int x,y;
???scanf("%d%d%d%lf",&n,&m,&s,&v);
???for(int i=1;i<=m;i++)
??? {
???????scanf("%d%d",&x,&y);
???????scanf("%lf%lf%lf%lf",&rate[x][y],&ope[x][y],&rate[y][x],&ope[y][x]);
??? }
???if(spfa(s))printf("YES\n");else printf("NO\n");
?
???return 0;
}
)
)
)
)
