圖論(c++)

前言

這邊會放一些圖論的演算法,主要是為了方便自己以後複習,也希望能夠幫助到其他人,如果有任何問題歡迎在下方留言,我會盡快回覆。

拓樸排序

拓樸排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
const int N = 1E5 + 5;
vector<int> edge[N];

void Topological_sort(int V){
vector<int> res;
int enter_deg[N];
memset(enter_deg, 0, sizeof(enter_deg));
for(int i = 0; i < V; i++)
for(int cur : edge[i])
enter_deg[cur]++;
priority_queue<int, vector<int>, greater<int>> q;
for(int i = 0; i<V; i++)
if(enter_deg[i]==0)
q.push(i);
while(!q.empty()){
int cur = q.top(); q.pop();
res.eb(cur);
for(int ch : edge[cur]){
if(--enter_deg[ch] == 0)
q.push(ch);
}
}

bool is_dag=true;
for(int i = 0; i<V; i++)
if(enter_deg[i]!=0)
is_dag=false;
}

最小生成🌲

zerojudge a129

Kruskal's Algorithm

精神:Disjoint Set 找不形成環的最小邊

Kruskal's Algorithm O(N log N)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <bits/stdc++.h>
#define N 200005
#define edge pair<int, pair<int, int> >
#define u first
#define v second.first
#define w second.second
#define int long long
using namespace std;

int boss[N], n, m;
edge E[N];

bool cmp(edge a, edge b){
return a.w < b.w;
}

int find_boss(int x){
if(x == boss[x]) return x;
return boss[x] = find_boss(boss[x]); //路徑壓縮
}

signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
while(cin >> n >> m){
int num_edge = 0;
for(int i = 0; i<n; i++) boss[i] = i;
for(int i = 0; i<m; i++) cin >> E[i].u >> E[i].v >> E[i].w;
sort(E, E+m, cmp);
int ans = 0;
for(int i = 0; i<m; i++){
int a = find_boss(E[i].u), b = find_boss(E[i].v);
if(a!=b){
boss[b] = a;
ans += E[i].w;
num_edge++;
}
}
if(num_edge == n-1)
cout << ans << '\n';
else cout << "-1\n";
}

return 0;
}

Prim's Algorithm

精神:找不在樹上,距離樹各點最近的點

Prim's Algorithm (跟最短路徑的 Dijkstra 很像) O (N log N)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <bits/stdc++.h>
#define N 200005
#define pii pair<int, int>
#define w first
#define to second
#define int long long
using namespace std;

signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n, m;
while(cin >> n >> m){
vector<pii> E[N];
int num_edge = 0, ans = 0;
for(int i = 0, u, v, w; i<m; i++)
cin >> u >> v >> w, E[u].push_back({w,v}), E[v].push_back({w, u});
priority_queue<pii, vector<pii>, greater<pii>> q;
bool vis[N]; memset(vis, 0, sizeof(vis)); vis[0] = 1;
for(pii x : E[0]) q.push(x);
while(!q.empty()){
pii cur = q.top(); q.pop();
if(vis[cur.to]) continue;
vis[cur.to] = 1, num_edge++;
ans += cur.w;
for(pii x : E[cur.to]) q.push(x);
}

if(num_edge == n-1)
cout << ans << '\n';
else cout << "-1\n";
}

return 0;
}

最短路徑

zerojudge a874

Floyd-Warshall

精神: Dynamic Programming

Floyd-Warshall O (N^3) 全對全
1
2
3
4
5
6
// dis[i][j]: 初始化為i->j這條邊的權重
// 若沒被定義的就設定為INF
for(int k=1; k<=n; k++)
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
dis[i][j]=min(dis[i][j], dis[i][k]+dis[k][j]);

Dijkstra

精神: Greedy 找不在樹上,距離樹根最短的點

Dijkstra O (N log N) 單對全
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <bits/stdc++.h>
#define pii pair<int, int>
#define w first
#define to second
using namespace std;

const int INF = 1E9;

signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n;
while(cin >> n){
vector<pii> E[30];
char s, e;
int dis[30];
fill(dis, dis+30, INF);
bool vis[30] = {0};
char x, y;
for(int i =0, w; i< n; i++)
cin>>x>>y>>w, x-=(int)'A', y-=(int)'A', E[x].push_back({w,y}), E[y].push_back({w,x});
cin >> s >> e, s-='A', e-='A', dis[s] = 0;
priority_queue<pii, vector<pii>, greater<pii>> pq;
dis[s] = 0, pq.push({0,s});
while(!pq.empty()){
pii cur = pq.top(); pq.pop();
if(vis[cur.to]) continue;
vis[cur.to] = 1;
for(pii go : E[cur.to]){
if(dis[go.to] > dis[cur.to]+go.w){
dis[go.to] = dis[cur.to]+go.w;
pq.push({dis[go.to], go.to});
}
}
}
if(dis[e]==INF) cout << "NoRoute\n";
else cout << dis[e] << '\n';
}
}

雙連通分量、橋、割點

寫點題目

neoj165

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<bits/stdc++.h>
using namespace std;

//確認是一個有相無環圖 拓樸排序
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
while(t--){
int deg[100006];
vector<int> arr[100006];
priority_queue<int, vector<int>, greater<int> > Q;
queue<int> ans;
memset(deg, 0, sizeof(deg));
int n, m;
cin >> n >> m;
//由兩個整數 a 和 b ( 0 ≤ a , b ≤ n − 1 )組成,
//代表要攻破陣地 b 之前必須先攻破陣地 a ,其中陣地從 0 ~ n − 1 依序編號。
for(int i = 0, a, b; i<m; i++)
cin>>a>>b, arr[a].push_back(b), deg[b]++;
for(int i = 0; i<n; i++)
if(deg[i]==0)
Q.push(i);

while(!Q.empty()){
int tmp = Q.top();
Q.pop(); ans.push(tmp);
for(int i : arr[tmp]){
if(--deg[i]==0)
Q.push(i);
}
}
bool QAQ = false;
for(int i = 0; i<n; i++)
if(deg[i]) {QAQ=true; break;}
if(QAQ) cout << "QAQ";
else while(!ans.empty()){
cout << ans.front(), ans.pop();
if(ans.size()>=1)
cout << ' ';
}
cout << '\n';
}
}

neoj391

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<bits/stdc++.h>
#define N 101
#define pii pair<int, int>
#define w first
#define p second
#define int long long
using namespace std;

signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
while(t--){
// N代表可魚國內有幾個城市, M代表墨魚運輸公司提供幾種運輸方案
// S , E 分別代表你的工廠所在的城市以及你所要送去的城市。
// F 代表那隻富有的大可魚訂購了多少箱的可魚果。
int n,m,s,e,f;
vector<pii> P[N];
cin>>n>>m>>s>>e>>f;
//一定是全部一起送去最便宜
//邊權即送f過去的價錢
for(int i = 0; i<m; i++){
int a, b, c, d , cc, w;
//每個方案 P i 會從一個固定的起始城市 A i 運送東西到另一個固定的終點城市 B i
//,每運輸一箱的可魚果,你就必須付給墨魚運輸公司 C i 可魚幣。另外,
//若兩個方案的終點與起點相接,則可以不花任何額外費用的將貨物轉過去。不過由於你的運輸量太大了,
//墨魚運輸公司決定祭出優惠,若用方案 P i 運輸了超過 D i 箱的可魚果,
//多出來的部份每箱改收優惠價 C i ′ 可魚幣。
cin >> a >>b >>c >> d >>cc;
if(f<=d) w = c*f;
else w = c*d+(f-d)*cc;
P[a].push_back(make_pair(w, b));
}
priority_queue<pii,vector<pii>,greater<pii> > Q;//排序要看全中 所以w要在前面
Q.push(make_pair(0, s));
bool vis[N];
int d[N];
for(int i = 0; i<N; i++) d[i] = 1e18;
d[s] = 0;
memset(vis, 0, sizeof(vis));
while(!Q.empty()){
int pt = Q.top().p;
Q.pop();
if(!vis[pt]){
for(pii i: P[pt]){
int nP = i.p, nW = i.w;
if(d[pt]+nW < d[nP]){
d[nP] = d[pt]+nW;
Q.push(make_pair(d[nP],nP));
}
}
vis[pt] = true;
}
}
cout<<d[e]<<endl;
}
return 0;
}

neoj431

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <bits/stdc++.h>
#define MAX 500005
#define INF 1e18
#define int long long
#define pii pair<int, int>
#define weight first
#define val second
typedef long long LL;
using namespace std;
//城市、軌道、改的數量
int n,m,q;
vector< pii > ahead[MAX];
vector< pii > back[MAX];
int ahead_dis[MAX], back_dis[MAX];

/*
先建一條1->n的最短路
在把箭頭反過來建一條n->1的
新建的路是a->b
最後球1->n 跟 1->a + a->b + b->n 誰比較小誰就是答案
*/
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
memset(ahead_dis, 0, sizeof(ahead_dis));
memset(back_dis, 0, sizeof(back_dis));
cin >> n >> m >>q;
for(int i = 0; i<m; i++){
int a,b,w;
cin >> a >> b >> w;
ahead[a].push_back(make_pair(w,b));
back[b].push_back(make_pair(w,a));
}
for(int i = 0 ;i<MAX;i++){
ahead_dis[i] = INF, back_dis[i] = INF;
}
ahead_dis[1] = 0, back_dis[n] = 0;
bool visA[MAX], visB[MAX];
memset(visA, 0, sizeof(visA));
memset(visB, 0, sizeof(visB));
priority_queue<pii, vector<pii>, greater<pii> > QA;
priority_queue<pii, vector<pii>, greater<pii> > QB;
QA.push( make_pair(0,1));
QB.push( make_pair(0,n));
while(!QA.empty()){
int cur = QA.top().val;
QA.pop();
if(!visA[cur]){
for(pii i : ahead[cur]){
int v = i.val, w= i.weight;
if(ahead_dis[cur]+w < ahead_dis[v]){
ahead_dis[v] = ahead_dis[cur]+w;
QA.push(make_pair(ahead_dis[v],v));
}
}
visA[cur] = true;
}
}
while(!QB.empty()){
int cur = QB.top().val;
QB.pop();
if(!visB[cur]){
for(pii i : back[cur]){
int v = i.val, w= i.weight;
if(back_dis[cur]+w < back_dis[v]){
back_dis[v] = back_dis[cur]+w;
QB.push(make_pair(back_dis[v],v));
}
}
visB[cur] = true;
}
}
while(q--){
int a, b;
cin >> a >> b;
int ori = ahead_dis[n];
int aft = ahead_dis[a]+1+back_dis[b];
cout << min(ori, aft) << '\n';
}
return 0;
}

neoj394

neoj375

neoj736

neoj179

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <bits/stdc++.h>
#define Max 30005
#define pt first
#define cnt second
#define init(x) memset(x, 0, sizeof(x))
typedef long long LL;
using namespace std;

int n,m;
vector<int> edges[Max];
bool vis[Max], isAP[Max];
vector<pair<int, int> > AP;

int maxAP_child = 0, maxAP = Max;
int low[Max], lv[Max], CHcnt[Max];
int chcnt = 0;
void dfs(int root, int lev, int father){
lv[root] = lev;
vis[root] = true;
low[root] = lev;
int inChCnt = chcnt, wwwwwCnt = 0, son_cnt = 0;
bool isAP = false;
for(int ch : edges[root]){
if(ch==father || ch==root) continue;
if(vis[ch]) low[root] = min(low[root], lv[ch]);
else{
son_cnt++;
dfs(ch, lev+1, root);
low[root] = min(low[root], low[ch]);
chcnt++;
if(low[ch]>=lv[root] && lv[root]!=0) isAP=true, wwwwwCnt+=CHcnt[ch];
}
}
CHcnt[root] = chcnt-inChCnt+1;
// if(lv[root]==0 && son_cnt>1) isAP=true;
if(isAP) AP.push_back(make_pair(root, wwwwwCnt));
// cout << root << ' ' << CHcnt[root] << ' ' << low[root] << ' ' << lv[root]<<' '<<wwwwwCnt<< '\n';
}

//因為有🈹️點傳的人就會減少,所以如果沒有割點那就是傳0
//會變少的點就只有割點,透過記錄每個包含自己的樹的節點數,在遇到low[ch]>=lv[root]時把ch整棵樹加進去,
//最後就能得到可減少結點數,維護最大可減少節點數跟最小的最大可減少節點數的節點,最後就輸出這兩個
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
init(vis), init(low), init(isAP), init(lv), init(CHcnt);
cin >> n >> m;
for(int i = 0, x, y; i<m; i++)
cin >> x >> y, edges[x].push_back(y), edges[y].push_back(x);
int p;
cin >> p;
dfs(p, 0, -1);

for(auto ap : AP){
if(ap.cnt == maxAP_child) maxAP = min(maxAP,ap.pt);
if(ap.cnt > maxAP_child) maxAP = ap.pt;
maxAP_child = max(maxAP_child,ap.cnt);
}

if(maxAP_child == 0) cout <<"0\n";
else cout <<maxAP<<' '<< CHcnt[p]-maxAP_child << '\n';
return 0;
}

neoj183

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <bits/stdc++.h>
#define Max 1000006
#define init(x) memset(x, 0, sizeof(0))
typedef long long LL;
using namespace std;

int n,m;
vector<int> E[Max];
int lv[Max], low[Max];
bool vis[Max], AP[Max];

void dfs(int root, int lev, int father){
if(vis[root]) return;
vis[root]=true;
low[root] = lv[root] = lev;
int son_cnt = 0;
for(int ch : E[root]){
if(ch==father) continue;
if(vis[ch]) low[root] = min(low[root], lv[ch]);
else{
// cout << root << ' ' << ch << '\n';
son_cnt++;
dfs(ch, lev+1, root);
low[root] = min(low[root], low[ch]);
if(low[ch]>=lv[root] && lv[root]!=0) AP[root]=1;
}
}
if(lv[root] == 0 && son_cnt>1)
AP[root] = 1;
// cout << root << ' ' << low[root] << ' ' << lv[root] << ' ' << AP[root] << ' ' << son_cnt<< '\n';
}

int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
init(vis), init(low), init(lv), init(AP);
cin >> n >> m;
for(int i = 0, x, y;i<m; i++)
cin>>x>>y, E[x].push_back(y), E[y].push_back(x);
dfs(1,0,-1);
for(int i = 1; i<=n; i++)
if(AP[i])
cout << i << '\n';
return 0;
}

neoj184

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <bits/stdc++.h>
#define Max 1000006
#define init(x) memset(x, 0, sizeof(x))
#define edge(x,y) make_pair(min(x,y), max(x,y))
#define pii pair<int, int>
typedef long long LL;
using namespace std;

vector<int> E[Max];
int low[Max], lv[Max];
bool vis[Max];
//x<y
set<pii> bridge;
vector<pii> input;

void dfs(int root, int father){
if(vis[root]) return;
vis[root] = true;
low[root] = lv[root] = lv[father]+1;
for(int ch : E[root]){
if(ch!=father){
dfs(ch, root);
low[root] = min(low[ch],low[root]);
if(low[ch]>lv[root]) //從子孫回來的
bridge.insert(edge(ch,root));
}
}
}

int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n, m;
init(low), init(lv), init(vis);
cin >> n >> m;
for(int i = 0,x,y; i<m; i++)
cin>>x>>y, E[x].push_back(y),E[y].push_back(x),input.push_back(edge(x,y));
dfs(1,0);
for(auto ed : input)
if(bridge.count(ed))
cout << ed.first << ' ' << ed.second << '\n';

return 0;
}

neoj739

1

neoj737

neoj738

2022 附中校內賽 PD

利用 DSU 倒著加邊回去

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pii pair<int,int>
#define x first
#define y second
#define ios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define eb emplace_back
#define pb push_back
#define popb pop_back
#define int ll

const int N = 200005;

int bose[N];
int n, m, q;
pii e[N];
vector<pii> op;
vector<bool> ans;
vector<int> G[N];
bool no_pt[N];

int find_bose(int ch){
if(bose[ch] == ch) return ch;
return bose[ch] = find_bose(bose[ch]);
}

signed main()
{
// ios;
//刪邊 -> 加邊 答案倒著輸出
cin >> n >> m;
for(int i = 0; i<N; i++) bose[i] = i;
for(int i = 0; i<m; i++) cin >> e[i].x >> e[i].y, G[e[i].x].eb(e[i].y), G[e[i].y].eb(e[i].x);
cin >> q;
memset(no_pt, 0, sizeof(no_pt));
for(int i = 0; i<q; i++){
int cmd, a, b;
cin >> cmd >> a;
if(cmd == 1){
no_pt[a] = 1;
for(int i : G[a])
if(no_pt[i]==1) op.eb(a+N, i+N);// cout << "bye " << a << ' ' << i << '\n';
}
else cin >> b, op.eb(a, b);
}
for(int i = 0; i<m; i++){
if(no_pt[e[i].x]==1 && no_pt[e[i].y]==1) continue;
// cout << e[i].x << " connect " <<e[i].y<<'\n';
bose[find_bose(e[i].x)] = find_bose(e[i].y);
}
while(!op.empty()){
pii cur = op.back(); op.popb();
if(cur.x < N) ans.eb(find_bose(cur.x)==find_bose(cur.y));
else bose[find_bose(cur.x-N)] = find_bose(cur.y-N);
}while(!ans.empty()){
bool a = ans.back(); ans.popb();
cout << (a ? "YES\n" : "NO\n");
}
return 0;
}

2022 師大附中暑期資訊培訓模擬競賽 I PB

2022 師大附中暑期資訊培訓模擬競賽 II PC

2020 花中一模 PE