门户网站建设厂商名录,短视频动漫怎么做出来的,海外网站推广,o2o是指的是什么文章目录 裸题#xff1a;904. 虫洞01分数规划#xff1a;361. 观光奶牛特殊建图与01分数规划trick#xff1a;1165. 单词环 裸题#xff1a;904. 虫洞
904. 虫洞 - AcWing题库
// 虫洞是负权且单向边#xff0c;道路是正权且双向边#xff0c;题目较裸#xff0c;判… 文章目录 裸题904. 虫洞01分数规划361. 观光奶牛特殊建图与01分数规划trick1165. 单词环 裸题904. 虫洞
904. 虫洞 - AcWing题库
// 虫洞是负权且单向边道路是正权且双向边题目较裸判断有无负环即可
#include iostream
#include cstring
using namespace std;const int N 510, M 6010;
int h[N], e[M], ne[M], w[M], idx;
int n, m, k;
int dis[N], cnt[N];
int q[N];
bool st[N];void add(int x, int y, int d)
{e[idx] y, ne[idx] h[x], w[idx] d, h[x] idx ;
}bool spfa()
{int tt 0, hh 0;memset(cnt, 0, sizeof(cnt));memset(dis, 0, sizeof(dis));memset(st, 0, sizeof(st));for (int i 1; i n; i ) st[i] true, q[tt ] i;while (hh ! tt){int x q[hh ];if (hh N) hh 0;st[x] false;for (int i h[x]; i ! -1; i ne[i]){int y e[i];if (dis[y] dis[x] w[i]){cnt[y] cnt[x] 1;if (cnt[y] n) return true;dis[y] dis[x] w[i];if (!st[y]) {st[y] true;q[tt ] y;if (tt N) tt 0;}}}}return false;
}int main()
{int T;scanf(%d, T);while (T -- ){memset(h, -1, sizeof(h));idx 0;scanf(%d%d%d, n, m, k);int x, y, d;for (int i 0; i m; i ){scanf(%d%d%d, x, y, d);add(x, y, d), add(y, x, d);}for (int i 0; i k; i ){scanf(%d%d%d, x, y, d);add(x, y, -d);}if (spfa()) puts(YES);else puts(NO);}return 0;
}这个真的服调半天还有邻接表的大小又设置错了 01分数规划361. 观光奶牛
361. 观光奶牛 - AcWing题库
在图论问题中所有形如某个部分之和除以某个部分之和最大的问题被称为01分数规划通常使用二分解决这类问题 根据题意这道题的答案范围在 ( 0 , 1000 ] (0, 1000] (0,1000]中我们需要二分这个区间找到答案 若点权之和/边权之和大于等于mid则说明答案在 [ m i d , r ] [mid, r] [mid,r]之间 反之点权之和/边权小于mid则说明答案在 [ l , m i d ] [l, mid] [l,mid]之间 根据这个二段性我们能二分出ans使得边权之和/边权之和的最大值 ans
现在的问题是check如何实现 整理不等式如下图
一个常用的技巧若图中的环既有点权又有边权那么可以将点权加到出边或者入边上 那么不等式的求和可以提到外面结合这个技巧将点权和边权结合 若一条边由x-y权值为w那么将其权值设置为 f x − m i d ∗ w f_x-mid*w fx−mid∗w f x f_x fx为x的点权 问题就转换成了图中是否存在一个正环 求正环只要修改三角不等式即可dis[y] dis[x] w[i]
总结下check判断图中是否存在一个环其点权之和/边权之和大于等于mid转换成图中是否存在一个正环或权值和为0的环若存在则l mid否则r mid
思考题目的二段性根据不等式重置边/点权根据不等式判断题目的具体问题负环/最小生成树/最短路
#include iostream
#include cstring
using namespace std;const int N 1010, M 5010;
int h[N], e[M], ne[M], w[M], idx;
int f[N];
double dis[N];
int cnt[N]; bool st[N];
int q[N];int n, m;void add(int x, int y, int d)
{e[idx] y, ne[idx] h[x], w[idx] d, h[x] idx ;
}bool check(double mid)
{memset(dis, 0, sizeof(dis));memset(cnt, 0, sizeof(cnt));int tt 0, hh 0;for (int i 1; i n; i ) st[i] true, q[tt ] i;while (hh ! tt){int x q[hh ];if (hh N) hh 0;st[x] false;for (int i h[x]; i ! -1; i ne[i]){int y e[i];if (dis[y] dis[x] f[x] - mid * w[i]){dis[y] dis[x] f[x] - mid * w[i];cnt[y] cnt[x] 1;if (cnt[y] n) return true;if(!st[y]){st[y] true;q[tt ] y;if (tt N) tt 0;}}}}return false;
}int main()
{memset(h, -1, sizeof(h));scanf(%d%d, n, m);for (int i 1; i n; i ) scanf(%d, f[i]);int x, y, d;for (int i 0; i m; i ){scanf(%d%d%d, x, y, d);add(x, y, d);}double l 0, r 1000;while (r - l 1e-4){double mid (l r) / 2;if (check(mid)) l mid;else r mid;}printf(%.2lf\n, r);return 0;
}debug点权需要从数组1号下标开始读取 特殊建图与01分数规划trick1165. 单词环
1165. 单词环 - AcWing题库
估算一下这题的数据量如果按照题意建图不仅爆空间还会爆时间所以这题需要考虑其他建图方式
题目给定的建图方式是单词为点若两单词能相连那么边的权值为1 考虑新的建图方式以单词的前两个字符为起点最后两个字符为终点建立一条有向边权值为单词的长度。这种建图方式中点的数量最多为26 * 26边的数量为 1 0 5 10^5 105
其次题目要求环中所有单词的长度之和 / 环中的单词数量最大显然是01分数规划 二分答案答案的范围是 ( 0 , 1000 ] (0, 1000] (0,1000]最大的答案为每个单词长度都是1000而最小的答案0是取不到的最小的情况应该是10用来表示无解 整理不等式重新设置边权为 w i − 1 ∗ m i d w_i - 1 * mid wi−1∗mid1是由环中点的数量累加后第二个式子再把累加提到外面第三个等式得到的 check每次根据mid判断图中是否存在正环或零环若存在返回true反之返回false
trick如果spfa更新了很多次还没有结束循环那么有极大概率可以认为图中存在环这里设置阈值为10000点数的十几倍当循环次数超过该值时直接认为图中存在环、 不过这样的trick在正规比赛中不会出现
#include iostream
#include cstring
using namespace std;const int N 27 * 27, M 1e5 10;
int h[N], e[M], ne[M], w[M], idx;
double dis[N];
int cnt[N], q[N];
bool st[N];void add(int x, int y, int d)
{e[idx] y, ne[idx] h[x], w[idx] d, h[x] idx ;
}bool check(double mid)
{memset(dis, 0, sizeof(dis));memset(cnt, 0, sizeof(cnt));int tt 0, hh 0, count 0;for (int i 0; i N - 1; i ) q[tt ] i, st[i] true;while (hh ! tt ){int x q[hh ];if (hh N) hh 0;st[x] false;for (int i h[x]; i ! -1; i ne[i]){int y e[i];if (dis[y] dis[x] w[i] - mid){cnt[y] cnt[x] 1;if (cnt[y] N) return true;if ( count 10000) return true;dis[y] dis[x] w[i] - mid;if (!st[y]){st[y] true;q[tt ] y;if (tt N) tt 0;}}}}return false;
}int main()
{int m;char str[1010];while (scanf(%d, m), m){memset(h, -1, sizeof(h));idx 0;for (int i 0; i m; i ){scanf(%s, str);int len strlen(str);if (len 2){int x (str[0] - a) * 26 str[1] - a;int y (str[len - 2] - a) * 26 str[len - 1] - a;add(x, y, len);}}double l 0, r 1000;while (r - l 1e-4){double mid (l r) / 2;if (check(mid)) l mid;else r mid;}if (r 1e-4) puts(No solution);else printf(%.2lf\n, r);}return 0;
}debugdis数组的类型开成int想着边的权值为整数int就行然而边权被重置类型是浮点数
