fork download
copy 
  1. #include <cmath>
  2. #include <cstdio>
  3. #include <vector>
  4. #include <iostream>
  5. #include <algorithm>
  6. using namespace std;
  7.  
  8. struct Edge {
  9.     int src, dest, weight;
  10. };
  11.  
  12. class Graph {
  13.     int V;
  14.     vector<Edge> edges;
  15.  
  16. public:
  17.     Graph(int V) : V(V) {}
  18.  
  19.     void addEdge(int src, int dest, int weight) {
  20.         edges.push_back({src, dest, weight});
  21.     }
  22.  
  23.     int maxDegree() {
  24.         vector<int> degree(V + 1, 0);
  25.         for (const auto& edge : edges) {
  26.             degree[edge.src]++;
  27.             degree[edge.dest]++;
  28.         }
  29.         return *max_element(degree.begin(), degree.end());
  30.     }
  31.  
  32.     int minDegree() {
  33.         vector<int> degree(V + 1, 0);
  34.         for (const auto& edge : edges) {
  35.             degree[edge.src]++;
  36.             degree[edge.dest]++;
  37.         }
  38.         return *min_element(degree.begin(), degree.end());
  39.     }
  40.  
  41.     int maxWeightedDegree() {
  42.         vector<int> degree(V + 1, 0);
  43.         for (const auto& edge : edges) {
  44.             degree[edge.src] += edge.weight;
  45.             degree[edge.dest] += edge.weight;
  46.         }
  47.         return *max_element(degree.begin(), degree.end());
  48.     }
  49.  
  50.     int minWeightedDegree() {
  51.         vector<int> degree(V + 1, 0);
  52.         for (const auto& edge : edges) {
  53.             degree[edge.src] += edge.weight;
  54.             degree[edge.dest] += edge.weight;
  55.         }
  56.         return *min_element(degree.begin(), degree.end());
  57.     }
  58.  
  59.     int totalEdgeWeight() {
  60.         int total = 0;
  61.         for (const auto& edge : edges) {
  62.             total += edge.weight;
  63.         }
  64.         return total / 2; // Each edge should be counted only once
  65.     }
  66. };
  67.  
  68. int main() {
  69.     int n, m;
  70.     cin >> n >> m;
  71.  
  72.     Graph graph(n);
  73.  
  74.     for (int i = 0; i < m; ++i) {
  75.         int src, dest, weight;
  76.         cin >> src >> dest >> weight;
  77.         graph.addEdge(src, dest, weight);
  78.     }
  79.  
  80.     cout << graph.maxDegree() << endl;
  81.     cout << graph.minDegree() << endl;
  82.     cout << graph.maxWeightedDegree() << endl;
  83.     cout << graph.minWeightedDegree() << endl;
  84.     cout << graph.totalEdgeWeight() << endl;
  85.  
  86.     return 0;
  87. }
  88.  
  89.  
Success #stdin #stdout 0s 5296KB
comments (?)
stdin
copy 
1
2
10
42
11
stdout
copy 
0
0
0
0
52
https://ideone.com/cK1v6z
language:
C++ (gcc 8.3)
created:
10 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!