环问题

算法 / 图论
字数统计: 1.5k   |   阅读时长≈ 8 分钟

无向有权最小环

最短路Floyd里面讲了,也可以用dij枚举边(因为无向图双向边,也要屏蔽反边)

https://www.luogu.com.cn/problem/P6175

这题有重边,邻接矩阵没问题

Floyd

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 endl '\n'
using namespace std;
typedef long long ll;
int f[105][105];
int mp[105][105];

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int n,m;
	cin>>n>>m;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= n; j++){
			mp[i][j] = 100005;
			if(i != j) f[i][j] = 100005;
		}
	}
	for(int i = 1; i <= m; i++){
		int u,v,w;
		cin>>u>>v>>w;
		mp[u][v] = min(mp[u][v], w);
		mp[v][u] = min(mp[v][u], w);
		f[u][v] = min(f[u][v], w);
		f[v][u] = min(f[v][u], w);
	}
	int ans = 100005;
	for(int k = 1; k <= n; k++){
		for(int i = 1; i <= n; i++){
			for(int j = 1; j <= n; j++){
				if(i != j && j != k && i != k) ans = min(ans, f[i][j] + mp[i][k] + mp[k][j]);
				f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
			}
		}
	}
	if(ans == 100005) cout<<"No solution."<<endl;
	else cout<<ans<<endl;
	return 0;
}

dij

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
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
const int N = 1e5;
vector<pair<int,int>>e [N];
bool vis[N];
int dis[N];
int ans = 1000005;
int n,m;
void init(){
	for(int i = 1; i <= n; i++){
		vis[i] = 0;
		dis[i] = 1000005;
	}
}
void dij(int a, int b){
	init();
	priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>>q;
	dis[a] = 0;
	q.push({0,a});
	while(!q.empty()){
		int u = q.top().second;
		q.pop();
		vis[u] = 1;
		for(auto i : e[u]){
			int v = i.first;
			int w = i.second;
			if(vis[v]) continue;
			if(u == a && v == b) continue;
			if(dis[v] > dis[u] + w){
				dis[v] = dis[u] + w;
				q.push({dis[v], v});
			}
		}
	}
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin>>n>>m;
	for(int i = 0; i < m; i++){
		int u, v, d;
		cin>>u>>v>>d;
		if(u == v) continue;
		e[u].push_back({v,d});
		e[v].push_back({u,d});
	}
	for(int i = 1; i <= n; i++){
		for(int j = 0; j < e[i].size(); j++){
			dij(i, e[i][j].first);
			ans = min(ans, dis[e[i][j].first] + e[i][j].second);
		}
	}
	if(ans != 1000005) cout<<ans<<endl;
	else cout<<"No solution."<<endl;
	return 0;
}

有向有权最小环

dij枚举边或者枚举顶点

无权图

无向

用dij枚举边或点(不用优先队列优化,直接普通bfs)

https://leetcode.cn/problems/shortest-cycle-in-a-graph/

枚举边

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
class Solution {
public:
    int findShortestCycle(int n, vector<vector<int>>& edges) {
        int ans = INT_MAX;
        vector<int> e[n];
        for(auto i : edges){
            e[i[0]].push_back(i[1]);
            e[i[1]].push_back(i[0]);
        }
        for(int i = 0; i < n; i++){
            for(int j : e[i]){
                vector<int> dis(n, n + 1);
                dis[i] = 0;
                queue<int>q;
                q.push(i);
                while(!q.empty()){
                    int u = q.front();
                    q.pop();
                    for(int v : e[u]){
                        if(u == i && v == j) continue;
                        if(dis[v] == n + 1){
                            dis[v] = dis[u] + 1;
                            q.push(v);
                        }
                    }
                }
                ans = min(ans, 1 + dis[j]);
            }
        }
        if(ans > n) ans = -1;
        return ans;
    }
};

枚举点

有向

https://leetcode.cn/problems/longest-cycle-in-a-graph/description/

tarjan或者拓扑排序+dfs

有向可以用tarjan得到强连通

也可以把边权看成1,跑dij

tarjan

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
int dfn[100010], low[100010],vis[100010];
int st[100010];
vector<int> e[100100];
class Solution {
public:
    int n, cnt;
    int ind = 0;
    int ans = -1;
    void tarjan(int u){
        st[++ind] = u;
        dfn[u] = low[u] = cnt++;
        for(int v : e[u]){
            if(!dfn[v]){
                tarjan(v);
                low[u] = min(low[u], low[v]);
            }else if(!vis[v]){
                low[u] = min(low[u], dfn[v]);
            }
        }
        if(low[u] == dfn[u]){
            int sum = 0;
            int p;
            do{
                p = st[ind--];
                vis[p] = 1;
                sum++;
            }while(p != u);
            ans = max(sum, ans);
        }
    }
    int longestCycle(vector<int>& edges) {
        n = edges.size();
        for(int i = 0; i < n; i++){
            dfn[i] = 0;
            vis[i] = 0;
            low[i] = 0;
            st[i] = 0;
            e[i].clear();
        }
        for(int i = 0; i < n; i++){
            if(edges[i] == -1) continue;
            e[i].push_back(edges[i]);
        }
        for(int i = 0; i < n; i++){
            if(!dfn[i]) tarjan(i);
        }
        if(ans == 1) ans = -1;
        return ans;
    }
};

拓扑+dfs

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
int in[100010],vis[100010];
vector<int> e[100010];
class Solution {
public:
    int n, ans = -1;
    int dfs(int u){
        int sum = 1;
        vis[u] = 1;
        for(int v : e[u]){
            if(!vis[v]) sum = 1 + dfs(v);
        }
        return sum;
    }
    int longestCycle(vector<int>& edges) {
        n = edges.size();
        for(int i = 0; i < n; i++){
            in[i] = 0;
            vis[i] = 0;
            e[i].clear();
        }
        for(int i = 0; i < n; i++){
            if(edges[i] == -1) continue;
            e[i].emplace_back(edges[i]);
            in[edges[i]]++;
        }
        queue<int>q;
        for(int i = 0; i < n; i++){
            if(in[i] == 0) q.push(i);
        }
        while(!q.empty()){
            int u = q.front();
            q.pop();
            for(int v : e[u]){
                in[v]--;
                if(in[v] == 0) q.push(v);
            }
        }
        for(int i = 0; i < n; i++){
            if(in[i] && !vis[i]){
                ans = max(ans, dfs(i));
            }
        }
        if(ans == 1) ans = -1;
        return ans;
    }
};

三元环计数

https://www.luogu.com.cn/problem/P1989

先把无向图转换为有向图(度数大的边指向度数小的边, 相同则编号小的边指向编号大的边,这个规则其实无所谓大小,只要你统一规定就好了)

然后遍历每个节点,然后遍历这个节点的所有邻居,把它所有邻居都指向它.

再遍历它所有邻居,同时遍历邻居的邻居,如果邻居的邻居是它自己,就证明了有环

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
#include <bits/stdc++.h>
using namespace std;

constexpr int MAXN = 1e5 + 5;
int deg[MAXN], vis[MAXN];
vector<int> G[MAXN];

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n, m;
    cin >> n >> m;
    vector<pair<int, int>> e(m);
    for (auto &[v, u] : e)
        cin >> v >> u, ++deg[v], ++deg[u];
    for (auto [v, u] : e)
    {
        if (deg[v] < deg[u] || deg[v] == deg[u] &&v > u){
            swap(v, u);
        }
        G[v].push_back(u);
    }
    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        for (auto u : G[i]){
            vis[u] = i;
        }
        for (auto u : G[i])
            for (auto w : G[u])
                ans += (vis[w] == i);
    }
    cout << ans << endl;

    return 0;
}
  • Copyrights © 2023-2024 Kano
  • 访问人数: | 浏览次数:

请我喝杯咖啡吧~

支付宝
微信