南昌的网站推广公司,北京建筑信息网,成都网站建设成都网络公司,建设网站合同文档负环
图 G G G中存在一个回路#xff0c;该回路边权之和为负数#xff0c;称之为负环。
spfa求负环
方法1:统计每个点入队次数, 如果某个点入队n次, 说明存在负环。 证明#xff1a;一个点入队n次#xff0c;即被更新了n次。一个点每次被更新时所对应最短路的边数一定是…负环
图 G G G中存在一个回路该回路边权之和为负数称之为负环。
spfa求负环
方法1:统计每个点入队次数, 如果某个点入队n次, 说明存在负环。 证明一个点入队n次即被更新了n次。一个点每次被更新时所对应最短路的边数一定是递增的也正因此该点被更新n次那么该点对应的的最短路长度一定大于等于n即路径上点的个数至少为n1。根据抽屉原理路径中至少有一个顶点出现两次, 也就是路径中存在环路。 而算法保证只有距离减少才会更新, 所以环路权值之和为负数。
方法2:统计从起点到任意顶点最短路经过的边数, 若某点对应边数 c n t ≥ n cnt≥n cnt≥n, 则也说明负环。 方法2根据抽屉原理易证。 我们一般采用方法2才求负环。
acwing904.虫洞
spfa求负环模板题
#include iostream
#include cstring
using namespace std;
const int N 510, M 5210;
int h[N], w[M], e[M], ne[M], tot;
int dist[N];
int cnt[N];
bool st[N];
int q[N];
int t;
int n, m, k;
void add(int a, int b, int c)
{e[tot] b, ne[tot] h[a], w[tot] c, h[a] tot ;
}
bool spfa()
{memset(dist, 0, sizeof dist);memset(st, 0, sizeof st);memset(cnt, 0, sizeof cnt);int hh 0, tt 0;for (int i 1; i n; i ){st[i] 1;q[tt ] i;}while (hh ! tt){int t q[hh ];if (hh N) hh 0;st[t] 0;for (int i h[t]; ~i; i ne[i]){int j e[i];if (dist[j] dist[t] w[i]){dist[j] dist[t] w[i];cnt[j] cnt[t] 1;if (cnt[j] n) return true;if (st[j]) continue;st[j] 1;q[tt ] j;if (tt N) tt 0;}}}return false;
}
int main()
{cin t;while (t -- ){cin n m k;tot 0;memset(h, -1, sizeof h);while (m -- ){int a, b, c;cin a b c;add(a, b, c), add(b, a, c);}while (k -- ){int a, b, c;cin a b c;add(a, b, -c);}bool t spfa();if (t) puts(YES);else puts(NO);}return 0;
}acwing361.观光奶牛
本题要求我们求出环中存在的 ∑ f [ i ] ∑ t [ i ] \frac{\sum f[i]}{\sum t[i]} ∑t[i]∑f[i]的最大值如果直接对问题进行求解是有难度的考虑二分答案。首先易知答案的范围在 [ 1 / 1000 , 1000 ] [1/1000, 1000] [1/1000,1000]之间假设我们当前二分到的答案为 m i d mid mid,如果 a n s m i d ans mid ansmid,我们可以去左半区间进行寻找,反之我们去右半区间寻找。 ∑ f [ i ] ∑ t [ i ] m i d \frac{\sum f[i]}{\sum t[i]} mid ∑t[i]∑f[i]mid ∑ f [ i ] m i d ∗ ∑ t [ i ] \sum f[i] mid*\sum t[i] ∑f[i]mid∗∑t[i] ∑ f [ i ] − m i d ∗ ∑ t [ i ] 0 \sum f[i]-mid*\sum t[i] 0 ∑f[i]−mid∗∑t[i]0 ∑ ( f [ i ] − m i d ∗ t [ i ] ) 0 \sum (f[i]-mid*t[i]) 0 ∑(f[i]−mid∗t[i])0 ∑ ( m i d ∗ t [ i ] − f [ i ] ) 0 \sum (mid*t[i]-f[i]) 0 ∑(mid∗t[i]−f[i])0 经过转换后问题就等价于把图中边权换为 m i d ∗ t [ i ] − f [ i ] mid*t[i]-f[i] mid∗t[i]−f[i],然后判断图中是否存在负环存在负环则说明图中存在 ∑ f [ i ] ∑ t [ i ] m i d \frac{\sum f[i]}{\sum t[i]}mid ∑t[i]∑f[i]mid的环。
#include iostream
#include cstring
using namespace std;
const int N 1010, M 5010;
int h[N], e[M], ne[M], tot;
int wf[N], wt[M];
int q[N];
double dist[N];
int cnt[N];
bool st[N];
int n, m;
void add(int a, int b, int c)
{e[tot] b, ne[tot] h[a], wt[tot] c, h[a] tot ;
}
bool check(double x)
{memset(dist, 0, sizeof dist);memset(st, 0, sizeof st);memset(cnt, 0, sizeof cnt);int hh 0, tt 0;for (int i 1; i n; i ){st[i] 1;q[tt ] i;}while (hh ! tt){int t q[hh ];if (hh N) hh 0;st[t] 0;for (int i h[t]; ~i; i ne[i]){int j e[i];double w x * wt[i] - wf[t];if (dist[j] dist[t] w){dist[j] dist[t] w;cnt[j] cnt[t] 1;if (cnt[j] n) return true;if (st[j]) continue;st[j] 1;q[tt ] j;if (tt N) tt 0;}}}return false;
}
int main()
{cin n m;for (int i 1; i n; i )cin wf[i];memset(h, -1, sizeof h);for (int i 1; i m; i ){int a, b, c;cin a b c;add(a, b, c);}double l 0, r 1001;while (r - l 1e-4){double mid (l r) / 2;if (check(mid)) l mid;else r mid;}printf(%.2lf, l);return 0;
}acwing1165.单词环
我们第一感觉是把每一个单词看作一个节点这样一来节点总数 n 1 0 5 n10^5 n105最坏情况是所有单词都可以互相进行匹配这样一来边数 m 1 0 5 ∗ 1 0 5 1 0 10 m10^5*10^510^{10} m105∗1051010考虑其他建图方式。 我们可以把每个单词看作一条边这样一来边数 m 1 0 5 m10^5 m105,每个单词开头结尾两个字母为节点节点总数 n 26 ∗ 26 676 n26*26676 n26∗26676。 本题要求我们求所有环的 ∑ w [ i ] ∑ 1 \frac{\sum w[i]}{\sum 1} ∑1∑w[i]最大值。和上题相同二分答案答案区间为 [ 1 / 1000 , 1000 ] [1/1000,1000] [1/1000,1000]。 ∑ w [ i ] ∑ 1 m i d \frac{\sum w[i]}{\sum 1} mid ∑1∑w[i]mid ∑ w [ i ] m i d \sum w[i] mid ∑w[i]mid ∑ w [ i ] − m i d 0 \sum w[i]-mid 0 ∑w[i]−mid0 ∑ ( w [ i ] − m i d ) 0 \sum (w[i]-mid) 0 ∑(w[i]−mid)0 ∑ ( m i d − w [ i ] ) 0 \sum (mid-w[i]) 0 ∑(mid−w[i])0 经过转换后问题就等价于把图中边权换为 m i d − w [ i ] mid-w[i] mid−w[i],然后判断图中是否存在负环存在负环则说明图中存在 ∑ w [ i ] ∑ 1 m i d \frac{\sum w[i]}{\sum 1}mid ∑1∑w[i]mid的环。
#include iostream
#include cstring
using namespace std;
const int N 26 * 26 10, M 100010;
int h[N], e[M], ne[M], w[M], tot;
double dist[N];
bool st[N];
int cnt[N];
int q[N];
char s[1010];
int n;
void add(int a, int b, int c)
{e[tot] b, ne[tot] h[a], w[tot] c, h[a] tot ;
}
bool check(double mid)
{memset(st, 0, sizeof st);memset(dist, 0, sizeof dist);memset(cnt, 0, sizeof cnt);int hh 0, tt 0;for (int i 0; i 26 * 26; i ){q[tt ] i;st[i] 1;}int count 0;while (hh ! tt){int t q[hh ];st[t] 0;if (hh N) hh 0;for (int i h[t]; ~i; i ne[i]){int j e[i];double ww mid - w[i];if (dist[j] dist[t] ww){dist[j] dist[t] ww;cnt[j] cnt[t] 1;if ( count 10000) return true;if (cnt[j] N) return true;if (st[j]) continue;st[j] 1;q[tt ] j;if (tt N) tt 0;}}}return false;
}
int main()
{while (cin n, n){memset(h, -1, sizeof h);tot 0;for (int i 1; i n; i ){cin s;int len strlen(s);if (len 2) continue;int ll (s[0] - a) * 26 s[1] - a;int rr (s[len - 2] - a) * 26 s[len - 1] - a;add(ll, rr, len);}double l 0, r 1001;if (!check(0)) puts(No solution);else{while (r - l 1e-4){double mid (l r) / 2;if (check(mid)) l mid;else r mid;}printf(%.2lf\n, r);}}return 0;
}
