グラフから減らすことができるスコアの最大量を見つけるためのC++プログラム
n個の頂点とm個のエッジを持つ重み付きの無向グラフがあるとします。グラフのスコアは、グラフ内のすべてのエッジの重みの加算として定義されます。エッジの重みは負の値になる可能性があり、それらを削除するとグラフのスコアが増加します。グラフを接続したまま、グラフからエッジを削除して、グラフのスコアを最小にする必要があります。減らすことができるスコアの最大量を見つける必要があります。
グラフは配列'edges'で与えられ、各要素は{weight、{vertex1、vertex2}}の形式です。
したがって、入力がn =5、m =6、edges ={{2、{1、2}}、{2、{1、3}}、{1、{2、3}}、{3 、{2、4}}、{2、{2、5}}、{1、{3、5}}}の場合、出力は4になります。
グラフからエッジ(1、2)と(2、5)を削除すると、スコアの合計の減少は4になり、グラフは接続されたままになります。
これを解決するために、次の手順に従います-
cnum := 0 Define an array par of size: 100. Define an array dim of size: 100. Define a function make(), this will take v, par[v] := v dim[v] := 1 Define a function find(), this will take v, if par[v] is same as v, then: return v return par[v] = find(par[v]) Define a function unify(), this will take a, b, a := find(a) b := find(b) if a is not equal to b, then: (decrease cnum by 1) if dim[a] > dim[b], then: swap values of (a, b) par[a] := b dim[b] := dim[b] + dim[a] cnum := n sort the array edges based on edge weights for initialize i := 1, when i <= n, update (increase i by 1), do: make(i) res := 0 for each edge in edges, do: a := first vertex of edge b := second vertex of edge weight := weight of edge if find(a) is same as find(b), then: if weight >= 0, then: res := res + 1 * weight Ignore following part, skip to the next iteration if cnum is same as 1, then: if weight >= 0, then: res := res + 1 * weight Otherwise unify(a, b) return res
例
理解を深めるために、次の実装を見てみましょう-
#include <bits/stdc++.h> using namespace std; int cnum = 0; int par[100]; int dim[100]; void make(int v){ par[v] = v; dim[v] = 1; } int find(int v){ if(par[v] == v) return v; return par[v] = find(par[v]); } void unify(int a, int b){ a = find(a); b = find(b); if(a != b){ cnum--; if(dim[a] > dim[b]){ swap(a, b); } par[a] = b; dim[b] += dim[a]; } } int solve(int n, int m, vector <pair <int, pair<int,int>>> edges){ cnum = n; sort(edges.begin(), edges.end()); for(int i = 1; i <= n; i++) make(i); int res = 0; for(auto &edge : edges){ int a = edge.second.first; int b = edge.second.second; int weight = edge.first; if(find(a) == find(b)) { if(weight >= 0) res += 1 * weight; continue; } if(cnum == 1){ if(weight >= 0) res += 1 * weight; } else{ unify(a, b); } } return res; } int main() { int n = 5, m = 6; vector <pair<int, pair<int,int>>> edges = {{2, {1, 2}}, {2, {1, 3}}, {1, {2, 3}}, {3, {2, 4}}, {2, {2, 5}}, {1, {3, 5}}}; cout<< solve(n, m, edges); return 0; }
入力
5, 6, {{2, {1, 2}}, {2, {1, 3}}, {1, {2, 3}}, {3, {2, 4}}, {2, {2, 5}}, {1, {3, 5}}}
出力
4
-
グラフ内のスーパー頂点を見つけるためのC++プログラム
n個の頂点を持つグラフが与えられたとします。頂点には1からnの番号が付けられ、配列edgesで指定されたエッジによって接続されます。各頂点には、配列valuesで指定された1からnまでの数値内のx値があります。ここで、グラフからスーパー頂点を見つける必要があります。頂点1からiへの最短経路にi番目の頂点と同じ「x」値を持つ頂点がない場合、頂点iは「スーパー頂点」と呼ばれます。この基準を満たすすべての頂点を印刷します。 したがって、入力がn =5のようである場合、値={1、2、2、1、3}、エッジ={{1、2}、{2、3}、{2、3}、{2、4 }、{4、5}}の場合、出力は1 345に
-
与えられたグラフのブリッジエッジの数を見つけるためのC++プログラム
n個の頂点とm個のエッジを含む重み付けされていない無向グラフが与えられたとします。グラフのブリッジエッジは、グラフを削除するとグラフが切断されるエッジです。与えられたグラフでそのようなグラフの数を見つける必要があります。グラフには、平行なエッジや自己ループは含まれていません。 したがって、入力がn =5、m =6、edges ={{1、2}、{1、3}、{2、3}、{2、4}、{2、5}、{3 、5}}の場合、出力は1になります。 グラフには、{2、4}のブリッジエッジが1つだけ含まれています。 これを解決するには、次の手順に従います- mSize := 100 Define an