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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
|
// 2467. Most Profitable Path in a Tree
#include "leetcode.h"
/*
* there is an undirected tree with 'n' nodes labeled from 0 to 'n - 1', rooted
* at node 0. you are given a 2d integer array 'edges' of length 'n - 1' where
* 'edges[i] = [a_i, b_i]' indicates that there is an edge between nodes 'a_i'
* and 'b_i' in the tree. at every node 'i', there is a gate. you are also given
* an array of even integers 'amount', where 'amount[i]' represents the price
* needed to open the gate at node 'i', if 'amount[i]' is negative, or the case
* reward obtained on oening the gate at node 'i' otherwise. return the maximum
* net income alice can have if she travels towards the optimal leaf node.
*/
#define HIGH 100100
#define PASS 100010
struct node {
int val;
struct node *next;
};
struct head {
struct node *head;
};
struct node *push_node(int val) {
struct node *new = (struct node *)malloc(sizeof(struct node));
new->val = val;
new->next = NULL;
return new;
}
void connect_edges(struct head *graph, int v1, int v2) {
struct node *tmp = push_node(v2);
tmp->next = graph[v1].head;
graph[v1].head = tmp;
tmp = push_node(v1);
tmp->next = graph[v2].head;
graph[v2].head = tmp;
}
struct head *create_graph(int **edges, int edgesSize) {
struct head *graph =
(struct head *)calloc(edgesSize + 1, sizeof(struct head));
for (int i = 0; i < edgesSize; i++)
connect_edges(graph, edges[i][0], edges[i][1]);
return graph;
}
bool bob_traverse(struct head *graph, int *vis, int curr) {
if (!curr)
return true;
struct node *new = graph[curr].head;
while (new) {
if (vis[new->val] == HIGH) {
vis[new->val] = vis[curr] + 1;
if (bob_traverse(graph, vis, new->val))
return true;
vis[new->val] = PASS;
}
new = new->next;
}
return false;
}
void alice_traverse(struct head *graph, int *alice_vis, int *bob_vis,
int *amount, int curr, int sum, int *max) {
if (bob_vis[curr] > alice_vis[curr])
sum += amount[curr];
else if (bob_vis[curr] == alice_vis[curr])
sum += amount[curr] / 2;
struct node *new = graph[curr].head;
bool leaf = true;
while (new) {
if (alice_vis[new->val] == HIGH) {
leaf = false;
alice_vis[new->val] = alice_vis[curr] + 1;
alice_traverse(graph, alice_vis, bob_vis, amount, new->val, sum, max);
}
new = new->next;
}
if (leaf)
*max = *max > sum ? *max : sum;
}
int mostProfitablePath(int **edges, int edgesSize, int *edgesColSize, int bob,
int *amount, int amountSize) {
int *bob_vis = (int *)malloc((edgesSize + 1) * sizeof(int));
int *alice_vis = (int *)malloc((edgesSize + 1) * sizeof(int));
int max = INT_MIN;
for (int i = 0; i <= edgesSize; i++)
bob_vis[i] = alice_vis[i] = HIGH;
struct head *graph = create_graph(edges, edgesSize);
bob_vis[bob] = alice_vis[0] = 0;
bob_traverse(graph, bob_vis, bob);
alice_traverse(graph, alice_vis, bob_vis, amount, 0, 0, &max);
return max;
}
int main() {
int e1i[4][2] = {{0, 1}, {1, 2}, {1, 3}, {3, 4}}, a1[] = {-2, 4, 2, -4, 6};
int e2i[1][2] = {{0, 1}}, a2[] = {-7280, 2350};
struct two_d_arr e1, e2;
two_d_arr_init(&e1, ARRAY_SIZE(e1i), ARRAY_SIZE(e1i[0]), e1i);
two_d_arr_init(&e2, ARRAY_SIZE(e2i), ARRAY_SIZE(e2i[0]), e2i);
printf("%d\n", mostProfitablePath(e1.arr, e1.row_size, e1.col_size, 3, a1,
ARRAY_SIZE(a1))); // expect: 6
printf("%d\n", mostProfitablePath(e2.arr, e2.row_size, e2.col_size, 1, a2,
ARRAY_SIZE(a2))); // expect: -7280
two_d_arr_free(&e1);
two_d_arr_free(&e2);
}
|