/*
Time limit: 1000ms
Memory limit: 256mb
---------------------Copy the following code, complete it and submit---------------------
I, <Your Full Name>, am submitting the assignment for
an individual project.
I declare that the assignment here submitted is original except for
source material explicitly acknowledged, the piece of work, or a part
of the piece of work has not been submitted for more than one purpose
(i.e. to satisfy the requirements in two different courses) without
declaration. I also acknowledge that I am aware of University policy
and regulations on honesty in academic work, and of the disciplinary
guidelines and procedures applicable to breaches of such policy and
regulations, as contained in the University website
http://www.cuhk.edu.hk/policy/academichonesty/.
It is also understood that assignments without a properly signed
declaration by the student concerned will not be graded by the
teacher(s).
*/
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <limits.h>
#include <string.h>
#define MAX_COST 999999
#define MAX_NODES 100000
// min heap
struct node {
int id;
int cost;
};
typedef struct node* Node;
struct Heap {
int capacity;
int size;
Node* arr;
};
typedef struct Heap* HeapADT;
Node CreateHeapNode(int id, int cost) {
Node tmp = (Node) malloc(sizeof(struct node));
tmp->id = id;
tmp->cost = cost;
return tmp;
}
HeapADT CreateHeap(int capacity) {
HeapADT heap = (HeapADT) malloc(sizeof(struct Heap));
heap->capacity = capacity;
heap->size = 0;
heap->arr = (Node*) malloc((capacity + 1) * sizeof(Node));
return heap;
}
void InsertHeap(HeapADT heap, Node tmp) {
if (heap->size < heap->capacity) {
heap->size++;
int cur = heap->size;
int father = cur / 2;
while (father >= 1 && heap->arr[father]->cost > tmp->cost) {
heap->arr[cur] = heap->arr[father];
cur = father;
father = cur / 2;
}
heap->arr[cur] = tmp;
}
}
void DeleteHeap(HeapADT heap) {
if (heap->size != 0) {
Node tmp = heap->arr[heap->size];
heap->size--;
int cur = 1;
int child = cur * 2;
while (child <= heap->size) {
if (child + 1 <= heap->size && heap->arr[child+1]->cost < heap->arr[child]->cost) {
child++;
}
if (heap->arr[child]->cost < tmp->cost) {
heap->arr[cur] = heap->arr[child];
cur = child;
child = cur * 2;
} else {
break;
}
}
heap->arr[cur] = tmp;
}
}
Node Top(HeapADT heap) {
if (heap->size > 0) {
return heap->arr[1];
} else {
return NULL;
}
}
int Empty(HeapADT heap) {
if (heap->size > 0) {
return 0;
} else {
return 1;
}
}
struct linkedListNode {
int id;
int weight;
struct linkedListNode* next;
};
typedef struct linkedListNode* ListNode;
ListNode CreateListNode(int id, int weight) {
ListNode node = (ListNode) malloc(sizeof(struct linkedListNode));
node->id = id;
node->weight = weight;
node->next = NULL;
return node;
}
// Graph ADT
struct graph {
int n;
ListNode* G;
};
typedef struct graph* GraphADT;
GraphADT CreateGraph(int n) {
GraphADT myGraph = (GraphADT) malloc(sizeof(struct graph));
myGraph->n = n;
myGraph->G = (ListNode*) malloc(n * sizeof(ListNode));
memset(myGraph->G, 0, n * sizeof(ListNode));
return myGraph;
}
// Be careful: the graph is undirected
// So you need to add edge(u, v) and edge(v, u) at the same time
void AddEdge(GraphADT myGraph, int u, int v, int weight) {
// WRITE YOUR CODE HERE
}
int cost[MAX_NODES+5];
// Tips: Use array cost[] to compute the weight of edge(u, v)
int Compute_Cost(int u, int v)
{
// WRITE YOUR CODE HERE
}
// graph related data structure
int c[MAX_NODES+5];
int color[MAX_NODES+5];
// color 0 means the node is already in the spanning tree
// color 1 means the node is not yet in the spanning tree
long long Minimum_Spanning_Tree_Cost(GraphADT myGraph, int n, int m)
{
HeapADT myHeap = CreateHeap(n + m * 2);
for(int i = 0; i < myGraph->n; ++i) {
c[i] = MAX_COST;
color[i] = 0;
}
// Be careful: you need a long long variable to store the total cost
// WRITE YOUR CODE HERE
}
int main()
{
int n, m, u, v;
scanf("%d %d", &n, &m);
GraphADT myGraph = CreateGraph(n);
for(int i = 0; i < n; ++i)
scanf("%d", &cost[i]);
for(int i = 0; i < m; ++i)
{
scanf("%d %d", &u, &v);
AddEdge(myGraph, u, v, Compute_Cost(u, v));
}
printf("%lld\n", Minimum_Spanning_Tree_Cost(myGraph, n, m));
return 0;
}
---------------------------------------End of Code---------------------------------------
## [Minimum Cost for Transportation Design]
You are a renowned urban transportation designer tasked with designing a cost-effective transportation network for a country.
The country is modeled as an undirected graph consisting of $n$ nodes (cities) with no initial roads (edges).
The government has provided $m$ candidate roads for you, each represented as an undirected edge connecting two distinct cities.
Your objective is to select exactly $n - 1$ roads from these candidates to form a connected undirected graph (a spanning tree) that minimizes the total construction cost.
Each city $i$ has a development coefficient $c_i$ , reflecting its level of infrastructure readiness.
The total cost of the network is calculated as the sum of $c_i × d_i$ for all cities, where $d_i$ denotes the degree of city $i$ in the chosen spanning tree.
Your challenge is to determine the optimal spanning tree configuration that minimizes this total cost.
The provided candidate roads guarantee at least one valid solution exists.
Hint: The problem can be transformed into a minimum spanning tree (MST) problem by strategically assigning weights to edges.
Consider how the development coefficients of connected cities influence the cost, and derive edge weights that allow standard MST algorithms (e.g., Krusky's or Prim's) to yield the optimal solution.
### Input
The first line contains two integers $n, m(1\leq n \leq m\leq 200000)$, representing the number of nodes and candidates roads.
The second line contains $n$ integers, and the $i$-th represents $c_{i-1} (1\leq c_{i-1}\leq 100000)$.
The next $m$ lines each contain two integers $u,v$, representing a candidate road.
### Output
Output one single integer, the minimum cost.
### Example
**Input**
```
5 6
1 4 5 1 5
2 4
0 4
3 4
1 4
0 2
1 2
```
**Output**
```
27
```