经过笔者的多次实践(失败),在此温馨提示:用SPFA判负环时一定要特别小心! 首先SPFA有BFS和DFS两种实现方式,两者的判负环方式也是不同的.       BFS是用一个num数组,num[x]表示从1到x的最短路径包含的边数,当执行松弛操作d[y]=d[x]+w时,同样更新num[y]=num[x]+1,若此时发现num[y]>=n,则图中有负环(显然,n个点n条不重的边,必定又环).DFS则是换了一种思路:把d数组的初值置为0,这样就能保证走过的路径和一直为负,排除了大量无关路径.但是

题目链接:http://poj.org/problem?id=3621 Sightseeing Cows Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 11526   Accepted: 3930 Description Farmer John has decided to reward his cows for their hard work by taking them on a tour of the big ci

Currency Exchange Time Limit:1000MS     Memory Limit:30000KB     64bit IO Format:%I64d & %I64u Submit Status Practice POJ 1860 Description Several currency exchange points are working in our city. Let us suppose that each point specializes in two par

题目连接:http://poj.org/problem?id=1860 题意:有多种从a到b的汇率,在你汇钱的过程中还需要支付手续费,那么你所得的钱是 money=(nowmoney-手续费)*rate,现在问你有v钱,从s开始出发交换钱能不能赚钱. 分析:如何存在正环,能无限增加钱,肯定可以赚了,因此用spfa判一下即可 #include <cstdio> #include <cstring> #include <string> #include <cmath&

d[i]代表从起点出发可以获得最多的钱数,松弛是d[v]=r*d[u],求最长路,看有没有正环 然后这题输入有毒,千万别用cin 因为是大输入,组数比较多,然后找字符串用strcmp就好,千万不要用map 这题刚开始我T了(用的map),还以为组数很多卡spfa呢,然后我上网看了看都是floyd的,然后我用floyd写了一发,891ms过了 然后我感觉spfa的复杂度也不是很大,就是看有没有正环,所以我觉得可能是map+cin的锅,然后改了一发,用的spfa,47ms过 真是,算了,实质是本蒟蒻

题目链接:http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=25957 思路:由于路线为一个环,将路径上的权值改为c-p*d,那么然后建图,那么我们只需判断图中是否存在权值和为正的环,这个用spfa即可. #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<queue&g

转载来源:優YoU  http://user.qzone.qq.com/289065406/blog/1299337940 提示:关键在于反向利用Bellman-Ford算法 题目大意 有多种汇币,汇币之间可以交换,这需要手续费,当你用100A币交换B币时,A到B的汇率是29.75,手续费是0.39,那么你可以得到(100 - 0.39) * 29.75 = 2963.3975 B币.问s币的金额经过交换最终得到的s币金额数能否增加 货币的交换是可以重复多次的,所以我们需要找出是否存在正权回路,

目录 一.BFS法判负环 二.DFS法判负环 三.SPFA判正环 一.BFS法判负环 Code: #include<bits/stdc++.h> #define re register #define INF 0x3f3f3f3f using namespace std; int n,m; int first[8000],next[8000],go[8000],tot,cost[8000]; int dist[8000],vis[8000],add[8000]; inline void add

Farmer John has decided to reward his cows for their hard work by taking them on a tour of the big city! The cows must decide how best to spend their free time. Fortunately, they have a detailed city map showing the L (2 ≤ L ≤ 1000) major landmarks (

Description John在他的农场中闲逛时发现了许多虫洞.虫洞可以看作一条十分奇特的有向边,并可以使你返回到过去的一个时刻(相对你进入虫洞之前).John的每个农场有M条小路(无向边)连接着N (从1..N标号)块地,并有W个虫洞.其中1<=N<=500,1<=M<=2500,1<=W<=200. 现在John想借助这些虫洞来回到过去(出发时刻之前),请你告诉他能办到吗. John将向你提供F(1<=F<=5)个农场的地图.没有小路会耗费你超过100

Wormholes Time Limit: 2000MS Memory Limit: 65536K Total Submissions: 42366 Accepted: 15560 传送门 Description While exploring his many farms, Farmer John has discovered a number of amazing wormholes. A wormhole is very peculiar because it is a one-way p

BZOJ 4898 [APIO2017] 商旅 | SPFA判负环 分数规划 更清真的题面链接:https://files.cnblogs.com/files/winmt/merchant%28zh_CN%29.pdf 题解 --APIO2017那天我似乎在--北京一日游-- [更新]诶?我--我Rank1了?//虽然只有不几个人做这道题 正经的题解: 二分答案,如果存在一种环路使得[总获利/总路程 > mid],那么这个环路的[总(获利 - 路程 * mid)]一定大于0,换句话说,把边权换成

bfs版spfa void spfa(){ queue<int> q; ;i<=n;i++) dis[i]=inf; q.push();dis[]=;vis[]=; while(!q.empty()){ int u=q.front();q.pop(); for(int i=head[u];i;i=e[i].next){ int v=e[i].v,w=e[i].w; if(dis[v]>dis[u]+w){ dis[v]=dis[u]+w; if(!vis[v]){ vis[v]=;

传送门 答案只保留了6位小数WA了两次233. 这就是一个简单的01分数规划. 直接二分答案,根据图中有没有负环存在进行调整. 注意二分边界. 另外dfs版spfa判负环真心快很多. 代码: #include<bits/stdc++.h> #define N 3005 #define M 10005 using namespace std; inline int read(){ int ans=0; char ch=getchar(); while(!isdigit(ch))ch=getcha

题目描述 “那是一条神奇的天路诶~,把第一个神犇送上天堂~”,XDM先生唱着这首“亲切”的歌曲,一道猥琐题目的灵感在脑中出现了. 和C_SUNSHINE大神商量后,这道猥琐的题目终于出现在本次试题上了,旨在难到一帮大脑不够灵活的OIer们(JOHNKRAM真的不是说你……). 言归正传,小X的梦中,他在西藏开了一家大型旅游公司,现在,他要为西藏的各个景点设计一组铁路线.但是,小X发现,来旅游的游客都很挑剔,他们乘 火车在各个景点间游览,景点的趣味当然是不用说啦,关键是路上.试想,若是乘火车一圈转

PS:此题数组名皆引用:戳我 题目大意:有n个点m条有向边的图,边上有花费,点上有收益,点可以多次经过,但是收益不叠加,边也可以多次经过,但是费用叠加.求一个环使得收益和/花费和最大,输出这个比值. 显然这就是经典的分数规划题啊,就是最优比率环,那么就二分答案,将所有边(u,v)的边权改为[v的点权-(u,v)原边权*mid](因为d[i]=a[i]-L*b[i]),然后判一下是否有正环,有的话就说明有更优的答案(F(L)=sigma(a[i]*x[i])-L*sigma(b[i]*x[i])>

poj 2049(二分+spfa判负环) 给你一堆字符串,若字符串x的后两个字符和y的前两个字符相连,那么x可向y连边.问字符串环的平均最小值是多少.1 ≤ n ≤ 100000,有多组数据. 首先根据套路,二分是显然的.然后跑一下spfa判断正环就行了. 然而我被no solution坑了十次提交.. #include <cctype> #include <cstdio> #include <cstring> using namespace std; const in

[HNOI2009]最小圈 分数规划 spfa判负环 题面 思路难,代码简单. 题目求圈上最小平均值,问题可看为一个0/1规划问题,每个边有\(a[i],b[i]\)两个属性,\(a[i]=w(u,v),b[i]=1\),问题转化为\(min(\frac{\sum^{k}_{i=1}a[i]}{\sum^{k}_{j=1}b[j]})\) 分数规划考虑二分答案,当前\(mid\)可能为答案当且仅当: \[ \frac{\sum^{k}_{i=1}a[i]}{\sum^{k}_{j=1}b[j]}

题目链接:http://poj.org/problem?id=3259 Wormholes Time Limit: 2000MS   Memory Limit: 65536K Total Submissions:75598   Accepted: 28136 Description While exploring his many farms, Farmer John has discovered a number of amazing wormholes. A wormhole is very

void DFS_SPFA(int u){   if(flag) return; vis[u]=true;   for(int i=head[u];i;i=edges[i].nxt){   if(flag) return; int v=edges[i].v;   if(d[u]+edges[i].t<d[v]){           d[v]=d[u]+edges[i].t;           if(vis[v]){           flag=true;                 r

题目链接:http://poj.org/problem?id=3259 题目大意是给你n个点,m条双向边,w条负权单向边.问你是否有负环(虫洞). 这个就是spfa判负环的模版题,中间的cnt数组就是记录这个点松弛进队的次数,次数超过点的个数的话,就说明存在负环使其不断松弛. #include <iostream> #include <cstdio> #include <cstring> #include <queue> using namespace st