拓?fù)湫蚝虳AG有向無環(huán)圖聯(lián)系在一起,通常用于最短/長路的線性求解

裸題:1191. 家譜樹
1191. 家譜樹 - AcWing題庫
#include <iostream>
#include <cstring>
using namespace std;
const int N = 110, M = 10010;
int h[N], e[M], ne[M], idx;
int d[N], q[N], hh, tt = -1;
int n, m;
void add(int x, int y)
{
e[idx] = y, ne[idx] = h[x], h[x] = idx ++ ;
}
void topsort()
{
for (int i = 1; i <= n; ++ i )
if (!d[i]) q[ ++ tt ] = i;
while (tt >= hh )
{
int x = q[hh ++ ];
for (int i = h[x]; i != -1; i = ne[i])
{
int y = e[i];
if (-- d[y] == 0) q[++ tt] = y;
}
}
}
int main()
{
memset(h, -1, sizeof(h));
scanf("%d", &n);
for (int x = 1; x <= n; ++ x )
{
int y;
while (scanf("%d", &y), y)
{
add(x, y);
d[y] ++ ;
}
}
topsort();
for (int i = 0; i <= tt; ++ i )
printf("%d ", q[i]);
return 0;
}
差分約束+拓?fù)渑判颍?192. 獎(jiǎng)金
1192. 獎(jiǎng)金 - AcWing題庫
由于圖中所有邊權(quán)都是正數(shù),可以直接使用topsort求解差分約束問題
根據(jù)題意,要求一個(gè)最小值,使用最長路求解,轉(zhuǎn)化題目的條件:
A
>
=
B
+
1
A >= B + 1
A>=B+1與
x
i
>
=
x
0
+
100
x_i >= x_0 + 100
xi?>=x0?+100
x
0
x_0
x0?為一個(gè)虛擬源點(diǎn),向每個(gè)點(diǎn)連了一條權(quán)值為100的邊
若圖中存在環(huán),topsort的隊(duì)列長度將小于n,因?yàn)榄h(huán)的起點(diǎn)無法進(jìn)入隊(duì)列
先用topsort判斷圖中是否存在環(huán),若不存在,根據(jù)拓?fù)湫虮闅v圖,求解最長路
#include <iostream>
#include <cstring>
using namespace std;
const int N = 10010, M = 30010;
int h[N], e[M], ne[M], w[M], idx;
int q[N], d[N], hh, tt = -1;
int dis[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 topsort()
{
q[ ++ tt ] = 0;
while (tt >= hh)
{
int x = q[hh ++ ];
for (int i = h[x]; i != -1; i = ne[i] )
{
int y = e[i];
if ( -- d[y] == 0) q[ ++ tt ] = y;
}
}
return tt == n;
}
int main()
{
memset(h, -1, sizeof(h));
scanf("%d%d", &n, &m);
for (int i = 0; i < m; ++ i )
{
int x, y;
scanf("%d%d", &x, &y);
add(y, x, 1);
d[x] ++ ;
}
for (int i = 1; i <= n; ++ i ) add(0, i, 100), d[i] ++ ;
if (!topsort()) puts("Poor Xed");
else
{
for (int k = 0; k <= tt; ++ k )
{
int x = q[k];
for (int i = h[x]; i != -1; i = ne[i])
{
int y = e[i];
dis[y] = max(dis[y], dis[x] + w[i]);
}
}
int sum = 0;
for (int i = 1; i <= n; ++ i ) sum += dis[i];
printf("%d\n", sum);
}
return 0;
}
debug:最后的遍歷沒有按照拓?fù)湫?/p>
for (int x = 0; x <= tt; ++ x )
{
for (int i = h[x]; i != -1; i = ne[i])
{
int y = e[i];
dis[y] = max(dis[y], dis[x] + w[i]);
}
}
集合+拓?fù)湫颍?64. 可達(dá)性統(tǒng)計(jì)
[164. 可達(dá)性統(tǒng)計(jì) - AcWing題庫](https://www.acwing.com/problem/content/description/166/
從集合的角度思考,
f
(
i
)
f(i)
f(i)表示i這個(gè)點(diǎn)能到達(dá)的所有點(diǎn),i首先能到達(dá)自己,其次能達(dá)到
f
(
j
1
)
,
f
(
j
2
)
,
.
.
.
,
f
(
j
n
)
f(j_1), f(j_2), ... , f(j_n)
f(j1?),f(j2?),...,f(jn?),假設(shè)i與n個(gè)點(diǎn)直接相連
那么要求
f
(
i
)
f(i)
f(i),就必須求出
f
(
j
1
)
,
f
(
j
2
)
,
.
.
.
,
f
(
j
n
)
f(j_1), f(j_2), ... , f(j_n)
f(j1?),f(j2?),...,f(jn?),即拓?fù)渑判蛑形挥趇之后的所有點(diǎn)的
f
(
j
)
f(j)
f(j)
所以這題先拓?fù)渑判?,再根?jù)拓?fù)渑判虻哪嫘颍?span id="n5n3t3z" class="katex--inline">
f
(
i
)
f(i)
f(i)
如何表示集合
f
(
i
)
f(i)
f(i)?用STL的容器bitset
,假設(shè)圖中有N個(gè)點(diǎn),那么bitset的長度為N,每個(gè)點(diǎn)都用一個(gè)bitset記錄其集合,1表示i能遞達(dá)這個(gè)點(diǎn),0表示不能遞達(dá)
那么
f
(
i
)
=
f
(
j
1
)
∩
f
(
j
2
)
∩
.
.
.
∩
f
(
j
n
)
f(i) = f(j_1)∩ f(j_2)∩ ...∩f(j_n)
f(i)=f(j1?)∩f(j2?)∩...∩f(jn?)
關(guān)于bitset
的使用,bitset
之間支持|=
運(yùn)算,count()輸出bitset
中1的個(gè)數(shù)
#include <iostream>
#include <cstring>
#include <bitset>
using namespace std;
const int N = 30010, M = N;
int h[N], e[M], ne[M], idx;
int q[N], d[N], hh, tt = -1;
bitset<N> f[N];
int n, m;
void add(int x, int y)
{
e[idx] = y, ne[idx] = h[x], h[x] = idx ++ ;
}
void topsort()
{
for (int i = 1; i <= n; ++ i )
if (!d[i]) q[ ++ tt ] = i;
while (tt >= hh)
{
int x = q[hh ++ ];
for (int i = h[x]; i != -1; i = ne[i])
{
int y = e[i];
if ( -- d[y] == 0) q[ ++ tt ] = y;
}
}
}
int main()
{
memset(h, -1, sizeof(h));
scanf("%d%d", &n, &m);
for (int i = 0; i < m; ++ i )
{
int x, y;
scanf("%d%d", &x, &y);
add(x, y);
d[y] ++ ;
}
topsort();
for (int i = tt; i >= 0; -- i )
{
int x = q[i];
f[x][x] = 1;
for (int i = h[x]; i != -1; i = ne[i])
{
int y = e[i];
f[x] |= f[y];
}
}
for (int i = 1; i <= n; ++ i ) printf("%d\n", f[i].count());
return 0;
}
差分約束+拓?fù)湫颍?56. 車站分級(jí)
456. 車站分級(jí) - AcWing題庫
分析題意:對(duì)于每一條路線,未經(jīng)過的站點(diǎn)的等級(jí)一定小于經(jīng)過的站點(diǎn)等級(jí),并且最低的站點(diǎn)等級(jí)為1級(jí)
題目要求所有等級(jí)劃分中的最少等級(jí)數(shù),用最長路求最小值。將以上條件轉(zhuǎn)換成差分約束中的兩個(gè)條件:
B
>
=
A
+
1
B >= A + 1
B>=A+1,
x
i
>
=
x
0
+
1
x_i >= x_0 + 1
xi?>=x0?+1
x
0
x_0
x0?為虛擬源點(diǎn),通過
x
0
x_0
x0?能到達(dá)圖中的所有點(diǎn),那么就一定能遞達(dá)所有邊
由于每條路線路都會(huì)建立n * m
條邊,極端情況下可能會(huì)爆空間,所以考慮如何優(yōu)化
一條路徑中未經(jīng)過的站點(diǎn)將向經(jīng)過的站點(diǎn)連接一條權(quán)值為1的邊,一共n * m
條,由于這些邊的權(quán)值相同,可以在這些邊中創(chuàng)建一個(gè)虛擬點(diǎn)v,未經(jīng)過的點(diǎn)分別向v連一條權(quán)值為0的邊,v向經(jīng)過的點(diǎn)分別連接一條權(quán)值為1的邊。這樣,從未經(jīng)過的點(diǎn)到經(jīng)過的點(diǎn)的權(quán)值和依然為1,但是需要建立的邊數(shù)為n + m
,此時(shí)的邊數(shù)在極端情況下也不會(huì)爆空間文章來源:http://www.zghlxwxcb.cn/news/detail-650546.html
#include <iostream>
#include <cstring>
using namespace std;
const int N = 2010, M = 1e6 + 10;
int h[N], e[M], ne[M], w[M], idx;
int d[N], q[N], hh, tt = -1;
bool st[N]; int dis[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 ++ ;
}
void topsort()
{
for (int i = 1; i <= n + m; ++ i )
if (!d[i]) q[ ++ tt ] = i;
while (tt >= hh)
{
int x = q[hh ++ ];
for (int i = h[x]; i != -1; i = ne[i])
{
int y = e[i];
if (-- d[y] == 0) q[ ++ tt ] = y;
}
}
}
int main()
{
memset(h, -1, sizeof(h));
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; ++ i )
{
memset(st, false, sizeof(st));
int t, start = n, end = 0;
scanf("%d", &t);
while (t -- )
{
int x;
scanf("%d", &x);
st[x] = true;
start = min(start, x), end = max(end, x);
}
int v = n + i;
for (int i = start; i <= end; ++ i )
{
if (st[i]) add(v, i, 1), d[i] ++ ;
else add(i, v, 0), d[v] ++ ;
}
}
topsort();
for (int i = 1; i <= n; ++ i ) dis[i] = 1;
for (int i = 1; i <= tt; ++ i )
{
int x = q[i];
for (int i = h[x]; i != -1; i = ne[i])
{
int y = e[i];
dis[y] = max(dis[y], dis[x] + w[i]);
}
}
int res = 0;
for (int i = 1; i <= n; ++ i ) res = max(res, dis[i]);
printf("%d\n", res);
return 0;
}
debug:w[M]
寫成了w[N]
,又是這樣,然后debug了半天,了文章來源地址http://www.zghlxwxcb.cn/news/detail-650546.html
到了這里,關(guān)于第三章 圖論 No.13拓?fù)渑判虻奈恼戮徒榻B完了。如果您還想了解更多內(nèi)容,請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章,希望大家以后多多支持TOY模板網(wǎng)!