做刷网站,专业网站建设是哪家,国内专业的网站建设,百度信息流广告推广Description 在忘记考虑负环之后#xff0c;黎瑟的算法又出错了。对于边带权的有向图 G (V, E)#xff0c;请找出一个点数最小的环#xff0c;使得 环上的边权和为负数。保证图中不包含重边和自环。 Input 第1两个整数n, m,表示图的点数和边数。 接下来的m行#xff0… Description 在忘记考虑负环之后黎瑟的算法又出错了。对于边带权的有向图 G (V, E)请找出一个点数最小的环使得 环上的边权和为负数。保证图中不包含重边和自环。 Input 第1两个整数n, m,表示图的点数和边数。 接下来的m行每三个整数ui, vi, wi表有一条从ui到vi权值为wi的有向边。 2 n 300 0 m n(n 1) 1 ui, vi n |wi| 10^4 Output 仅一行一个整数表示点数最小的环上的点数若图中不存在负环输出0。 Sample Input 3 6 1 2 -2 2 1 1 2 3 -10 3 2 10 3 1 -10 1 3 10 Sample Output 2 分析 求负环 Abellmax ford Bfloyed Cspfa扔下去。。。 设计状态 f[k][i][j]表示i到j经过k个点的最短路 枚举k和i, 如果存在f[k][i][i]是负数 那么就是一个负环 k可以通过倍增得到:f[k]—f[k-1],f[k-1] 这只是基本原理 具体实现有一些细节 其实我们需要进行两次floyed 第一次利用倍增的方法 维护好f[k][i][j] f[k][i][j]min(f[k-1][i][l]f[k-1][l][j]); 但是这样的话我们只知道走2^k步时的答案 想想第一次接触倍增是什么时候 没错LCA 那时候我们是怎么处理的呢 for (ilg;i0;i–) 这就相当于把答案二进制分解了 得出的答案1就是最终答案 这道题也是一样 我们要求的是不存在负环的最大步数 最大步数1即为答案 第一次floyed我们得到了一个k走2^k出现负环 那答案一定2^k 我们就把k从大到小循环 只要是f[k][i][i]0 ans(1 k) 当然还有一些细节要处理 还记得我们一开始记录了一个h邻接矩阵 在循环的开始 我们先调用一个全新的函数memecpy(a,b,sizeof(b)) 表示b中的信息全部复制到a 这个while循环我们可以一步一步看 首先memcpyg保存一下h数组的信息 设g记录了走x步时的floyed的答案 之后就进行了一次耳熟能详的floyed 用来判断在走2^kx步数的情况下 能不能走出负环 能把h数组的信息还原这个2^kx太大了不符合我们找最大非负环的限制 不能ans(1 k)h数组中的信息保留(走2^kx) 这个h/g数组就相当于记录没有负环的最大步数 ans记录走了多少步 最后输出ans1 tip 变量名不要搞错了 这里写代码片
#includecstdio
#includeiostream
#includecstringusing namespace std;const int N310;
const int lg10;
int n,m,f[lg][N][N],g[N][N],h[N][N],ans;void floyed()
{int i,j,k,l;for (k1;klg;k){bool ff0;for (l1;ln;l) //最外层循环折点 for (i1;in;i)for (j1;jn;j){f[k][i][j]min(f[k][i][j],f[k-1][i][l]f[k-1][l][j]);}for (i1;in;i)if (f[k][i][i]0) ff1;if (ff) break;if ((1k)n) //整张图都不存在负环 {puts(0);return;}}ans0;while (k0) //步数{memcpy(g,h,sizeof(h));bool ff0;for (l1;ln;l)for (i1;in;i)for (j1;jn;j)h[i][j]min(h[i][j],g[i][l]f[k][l][j]);for (i1;in;i)if (h[i][i]0) ff1;if (ff) memcpy(h,g,sizeof(g)); //恢复信息 else ans(1k);k--;} printf(%d,ans1);
}int main()
{scanf(%d%d,n,m);memset(f,0x33,sizeof(f));memset(h,0x33,sizeof(h));for (int i1;in;i) f[0][i][i]h[i][i]0; //h邻接矩阵 for (int i1;im;i) {int u,w,z;scanf(%d%d%d,u,w,z);f[0][u][w]z;}floyed();return 0;
}转载于:https://www.cnblogs.com/wutongtong3117/p/7673380.html
