裸題：904. 蟲洞
904. 蟲洞 - AcWing題庫
// 蟲洞是負(fù)權(quán)且單向邊，道路是正權(quán)且雙向邊，題目較裸，判斷有無負(fù)環(huán)即可
#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;
}
這個==真的服，調(diào)半天，還有，鄰接表的大小又設(shè)置錯了
01分?jǐn)?shù)規(guī)劃：361. 觀光奶牛
361. 觀光奶牛 - AcWing題庫
在圖論問題中，所有形如：某個部分之和除以某個部分之和最大的問題，被稱為01分?jǐn)?shù)規(guī)劃，通常使用二分解決這類問題
根據(jù)題意，這道題的答案范圍在
(
0
,
1000
]
(0, 1000]
(0,1000]中，我們需要二分這個區(qū)間找到答案
若點權(quán)之和/邊權(quán)之和大于等于mid，則說明答案在
[
m
i
d
,
r
]
[mid, r]
[mid,r]之間
反之，點權(quán)之和/邊權(quán)小于mid，則說明答案在
[
l
,
m
i
d
]
[l, mid]
[l,mid]之間
根據(jù)這個二段性，我們能二分出ans，使得邊權(quán)之和/邊權(quán)之和的最大值 = ans
現(xiàn)在的問題是check如何實現(xiàn)？
整理不等式，如下圖：
一個常用的技巧：若圖中的環(huán)既有點權(quán)又有邊權(quán)，那么可以將點權(quán)加到出邊或者入邊上
那么不等式的求和可以提到外面，結(jié)合這個技巧，將點權(quán)和邊權(quán)結(jié)合
若一條邊由x->y，權(quán)值為w，那么將其權(quán)值設(shè)置為
f
x
?
m
i
d
?
w
f_x-mid*w
fx??mid?w，
f
x
f_x
fx?為x的點權(quán)
問題就轉(zhuǎn)換成了圖中是否存在一個正環(huán)？
求正環(huán)只要修改三角不等式即可：dis[y] < dis[x] + w[i]
總結(jié)下：check判斷圖中是否存在一個環(huán)，其點權(quán)之和/邊權(quán)之和大于等于mid，轉(zhuǎn)換成圖中是否存在一個正環(huán)（或權(quán)值和為0的環(huán)），若存在，則l = mid，否則r = mid，
- 思考題目的二段性
- 根據(jù)不等式重置邊/點權(quán)
- 根據(jù)不等式判斷題目的具體問題：負(fù)環(huán)/最小生成樹/最短路
#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：點權(quán)需要從數(shù)組1號下標(biāo)開始讀取
特殊建圖與01分?jǐn)?shù)規(guī)劃+trick：1165. 單詞環(huán)
1165. 單詞環(huán) - AcWing題庫
估算一下這題的數(shù)據(jù)量，如果按照題意建圖，不僅爆空間還會爆時間，所以這題需要考慮其他建圖方式
題目給定的建圖方式是：單詞為點，若兩單詞能相連，那么邊的權(quán)值為1
考慮新的建圖方式，以單詞的前兩個字符為起點，最后兩個字符為終點，建立一條有向邊，權(quán)值為單詞的長度。這種建圖方式中，點的數(shù)量最多為26 * 26，邊的數(shù)量為
1
0
5
10^5
105
其次，題目要求環(huán)中所有單詞的長度之和 / 環(huán)中的單詞數(shù)量最大，顯然是01分?jǐn)?shù)規(guī)劃
二分答案，答案的范圍是
(
0
,
1000
]
(0, 1000]
(0,1000]，最大的答案為每個單詞長度都是1000，而最小的答案0是取不到的，最小的情況應(yīng)該是1，0用來表示無解
整理不等式，重新設(shè)置邊權(quán)為
w
i
?
1
?
m
i
d
w_i - 1 * mid
wi??1?mid，1是由環(huán)中點的數(shù)量累加后（第二個式子）再把累加提到外面（第三個等式）得到的
check：每次根據(jù)mid判斷圖中是否存在正環(huán)或零環(huán)，若存在返回true，反之返回false
trick：如果spfa更新了很多次還沒有結(jié)束循環(huán)，那么有極大概率可以認(rèn)為圖中存在環(huán)，這里設(shè)置閾值為10000（點數(shù)的十幾倍），當(dāng)循環(huán)次數(shù)超過該值時，直接認(rèn)為圖中存在環(huán)、
不過這樣的trick在正規(guī)比賽中不會出現(xiàn)文章來源：http://www.zghlxwxcb.cn/news/detail-635136.html
#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;
}
debug：dis數(shù)組的類型開成int，想著邊的權(quán)值為整數(shù)，int就行，然而邊權(quán)被重置，類型是浮點數(shù)文章來源地址http://www.zghlxwxcb.cn/news/detail-635136.html
到了這里，關(guān)于第三章 圖論 No.6負(fù)環(huán)之01分?jǐn)?shù)規(guī)劃與特殊建圖方式的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
