24:I[344796,["/_next/static/chunks/083cs_iw_ie0y.js","/_next/static/chunks/00mfjk9z2ewie.js","/_next/static/chunks/0kte1p5-f-6qg.js","/_next/static/chunks/1m-ucx9f24e0y.js","/_next/static/chunks/0uf80u9-0x190.js","/_next/static/chunks/14j8vn9k5ltv3.js","/_next/static/chunks/3v_5xqrzlodgn.js","/_next/static/chunks/0pa5jqbmn9_7a.js","/_next/static/chunks/1ar-qc6-a6pvz.js"],"default"] 2a:I[27201,["/_next/static/chunks/083cs_iw_ie0y.js","/_next/static/chunks/00mfjk9z2ewie.js","/_next/static/chunks/0kte1p5-f-6qg.js","/_next/static/chunks/1m-ucx9f24e0y.js","/_next/static/chunks/0uf80u9-0x190.js","/_next/static/chunks/14j8vn9k5ltv3.js","/_next/static/chunks/3v_5xqrzlodgn.js","/_next/static/chunks/0pa5jqbmn9_7a.js"],"IconMark"] 25:T13e9,

Salesforce Channel Optimization

In a Salesforce-powered organization, different departments are represented as connected undirected nodes in a network with a total of org_nodes nodes numbered from 1 to org_nodes.

Each node corresponds to a department, and the communication channels between these departments are represented as edges that connect org_from[i] to org_to[i] with associated cost org_weight[i].

The organization needs to optimize its system by removing unnecessary communication channels between departments while maintaining full connectivity, i.e. each department must be able to reach every other department either directly or through a sequence of channels.

After the optimization, exactly org_nodes - 1 channels may remain, and they must keep all departments connected — that is, the retained channels form a spanning tree of the organization.

Your task is to determine the maximum possible sum of communication channel costs that can be removed.

Note: All the communication channels (edges) are bi-directional, and the associated costs can be negative as well. The network may contain multiple channels between the same pair of departments, and channels that start and end at the same department (self-loops). A self-loop is never part of a spanning tree, so it is always removed.

Input Format

The first line contains two space-separated integers org_nodes and org_edges — the number of departments and the number of communication channels.

Each of the next org_edges lines contains three space-separated integers org_from[i], org_to[i] and org_weight[i] — the two endpoints of the i-th channel and its cost.

Output Format

Print a single integer — the maximum possible sum of the costs of the removed communication channels.

Constraints

2 ≤ org_nodes ≤ 2 * 10^5
org_nodes - 1 ≤ org_edges ≤ 2 * 10^5
1 ≤ org_from[i], org_to[i] ≤ org_nodes
-10^9 ≤ org_weight[i] ≤ 10^9
The network may contain multiple channels between the same pair of departments and/or self-loops.
It is guaranteed that the network is connected: every department is reachable from every other department. (inferred; the source only bounds org_edges from below, which alone does not guarantee connectivity)
The answer fits in a signed 64-bit integer: its absolute value is at most 2 10^14, so use long long in C++ and long in Java — a 32-bit int overflows. (inferred from the input bounds)*

Examples

Example 1

Input:

Output:

Explanation: The total cost of all five channels is 1 + 1 + 1 + 2 + 2 = 7. Retaining the three channels 1-2, 1-3 and 1-4 (total cost 3) keeps every department connected, so the channels between departments 2 and 3 and between departments 2 and 4 are removed for a total of 2 + 2 = 4.

Example 2

Input:

Output:

Explanation: The total cost of all three channels is -2 + 4 + (-1) = 1. Retaining the channels 1-2 (cost -2) and 3-1 (cost -1) keeps all three departments connected at a total retained cost of -3, so the removed cost is 1 - (-3) = 4. Only the channel of cost 4 is removed.

Example 3

Input:

Output:

Explanation: One channel must remain to connect the two departments, and only the channel 1-2 of cost 10 can serve that purpose. Both self-loops are removed, so the removed cost is -5 + 15 = 10.

Notes

Departments are numbered from 1 (1-based indexing).
The costs of self-loops and of duplicate parallel channels still count toward the total cost of the network, and every one of them that is not part of the retained spanning tree contributes to the answer.
Exactly org_nodes - 1 channels remain, so when org_edges = org_nodes - 1 the network is already a tree and the answer is 0.
The answer can be 0, and it can be negative — for example when every channel cost is negative, the removed channels sum to a negative value.
There is always at least one valid answer because the network is guaranteed to be connected.

26:T48b,#include #include #include #include #include using namespace std; struct Edge { int w, u, v; }; static vector parent; static int findRoot(int x) { while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; } return x; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; if (!(cin >> n >> m)) return 0; vector edges; edges.reserve(m); long long total = 0; for (int i = 0; i < m; i++) { int u, v, w; cin >> u >> v >> w; total += w; if (u != v) edges.push_back({w, u, v}); } sort(edges.begin(), edges.end(), [](const Edge &a, const Edge &b) { return a.w < b.w; }); parent.resize(n + 1); iota(parent.begin(), parent.end(), 0); long long kept = 0; int used = 0; for (const Edge &e : edges) { int ru = findRoot(e.u), rv = findRoot(e.v); if (ru != rv) { parent[ru] = rv; kept += e.w; if (++used == n - 1) break; } } cout << (total - kept) << "\n"; return 0; } 27:T6b2,import java.io.DataInputStream; import java.io.IOException; public class Main { static long getMaxRemovedChannelCost(int orgNodes, int[] orgFrom, int[] orgTo, int[] orgWeight) { // Write your code here return 0; } public static void main(String[] args) throws IOException { FastReader in = new FastReader(); int orgNodes = in.nextInt(); int orgEdges = in.nextInt(); int[] orgFrom = new int[orgEdges]; int[] orgTo = new int[orgEdges]; int[] orgWeight = new int[orgEdges]; for (int i = 0; i < orgEdges; i++) { orgFrom[i] = in.nextInt(); orgTo[i] = in.nextInt(); orgWeight[i] = in.nextInt(); } System.out.println(getMaxRemovedChannelCost(orgNodes, orgFrom, orgTo, orgWeight)); } static class FastReader { private final DataInputStream din = new DataInputStream(System.in); private final byte[] buffer = new byte[1 << 16]; private int pointer = 0, bytesRead = 0; int nextInt() throws IOException { int ret = 0; int b = read(); while (b <= ' ') b = read(); boolean neg = b == '-'; if (neg) b = read(); while (b >= '0' && b <= '9') { ret = ret * 10 + (b - '0'); b = read(); } return neg ? -ret : ret; } private int read() throws IOException { if (pointer == bytesRead) { bytesRead = din.read(buffer, 0, buffer.length); pointer = 0; if (bytesRead == -1) return -1; } return buffer[pointer++]; } } } 28:Tce9,# Salesforce Channel Optimization In a Salesforce-powered organization, different departments are represented as nodes in an undirected network. There are `org_nodes` departments numbered from `1` to `org_nodes`. Each communication channel connects two departments. The `i`-th channel connects `org_from[i]` to `org_to[i]` and has communication cost `org_weight[i]`. All channels are bidirectional, and costs may be negative. The organization wants to remove some channels while keeping the network fully connected. Exactly `org_nodes - 1` channels may remain, and the remaining channels must still allow every department to reach every other department. In graph terms, the remaining channels must form a spanning tree. Determine the maximum possible sum of costs of the channels that are removed. ## Input Format The first line contains two space-separated integers `org_nodes` and `org_edges`. Each of the next `org_edges` lines contains three space-separated integers: - `org_from[i]` — one endpoint of the `i`-th channel - `org_to[i]` — the other endpoint of the `i`-th channel - `org_cost[i]` — the cost of the `i`-th channel For custom testing, the function input is equivalent to: ``` getMaxRemovedChannelCost(org_nodes, org_edges, org_from, org_to, org_cost) ``` ## Output Format Return or print a single integer — the maximum possible sum of the costs of the removed communication channels. ## Constraints - `2 <= org_nodes <= 2 * 10^5` - `org_nodes - 1 <= org_edges <= 2 * 10^5` - `1 <= org_from[i], org_to[i] <= org_nodes` - `-10^9 <= org_cost[i] <= 10^9` - The graph may contain multiple edges between the same pair of departments and self-loops. - The answer fits in a signed 64-bit integer, so use `long long` in C++ or `long` in Java. - The network is assumed to be connected; otherwise no spanning tree can be formed. ## Examples ### Example 1 Input: ```text 4 5 1 2 1 1 3 1 1 4 1 3 2 2 4 2 2 ``` Output: ```text 4 ``` Explanation: The total cost of all channels is `1 + 1 + 1 + 2 + 2 = 7`. One way to keep the departments connected is to keep the channels `1-2`, `1-3`, and `1-4`, which have total cost `3`. The two removed channels between `2-3` and `2-4` have total cost `2 + 2 = 4`. ### Example 2 Input: ```text 3 3 1 2 -2 1 3 4 3 1 -1 ``` Output: ```text 4 ``` Explanation: The total cost of all channels is `-2 + 4 + (-1) = 1`. Keeping the channels `1-2` for cost `-2` and `3-1` for cost `-1` forms the minimum-cost spanning tree with total cost `-3`. The removed cost is `1 - (-3) = 4`. ### Example 3 Input: ```text 2 3 1 2 10 1 1 -5 2 2 15 ``` Output: ```text 10 ``` Explanation: One channel must remain to connect the two departments. Only channel `1-2` can do that. The self-loop costs are `-5` and `15`, and both are removed, so the removed total is `-5 + 15 = 10`. ## Notes - Departments are 1-indexed. - Self-loops are never part of a spanning tree and therefore always contribute to the removed cost. - Parallel edges are independent: each copy contributes its own cost to the total, and at most one copy of any edge can be used in the retained spanning tree. - If `org_edges == org_nodes - 1`, the graph is already a tree and the answer is `0`. - The answer may be `0`, and it may be negative if all channel costs are negative.29:Ta34,# Salesforce Channel Optimization ## Intuition Let `total` be the sum of the costs of all channels. If the total cost of the channels we keep is `kept`, then the total cost of the removed channels is: ```text removed = total - kept ``` Since `total` is fixed, maximizing the removed cost is equivalent to **minimizing the cost of the retained channels**. The retained channels must be exactly `org_nodes - 1` channels and must keep the graph connected, so they must form a spanning tree. Therefore, the optimal retained set is exactly a **minimum spanning tree**. The answer is: ```text total - MST_cost ``` ## Approach 1. Read the graph and compute `total` as the sum of all edge costs. 2. Disregard self-loops for the MST step because a self-loop cannot join two different components and can never be part of the retained spanning tree. 3. Sort the remaining channels by cost in ascending order. 4. Run Kruskal's algorithm using a disjoint-set union / union-find data structure: - For each edge in sorted order, if its two endpoints are currently in different connected components, use that edge in the MST and add its cost to `mst_cost`. - Stop once `org_nodes - 1` edges have been selected. 5. The maximum removed cost is `total - mst_cost`. ## Why This Works Any valid solution retains `org_nodes - 1` edges and keeps the graph connected, so it is a spanning tree. Conversely, every spanning tree is a valid set of retained channels. Kruskal's algorithm produces a minimum spanning tree by repeatedly taking the cheapest edge that does not create a cycle. Negative edge costs do not affect the algorithm: it only compares costs, and the most negative edges will be considered first when sorted in ascending order. Self-loops always form a cycle immediately, so union-find never accepts them. They can still be included in the final answer because their costs are already included in the total sum. ## Complexity Let `n = org_nodes` and `m = org_edges`. - Sorting the edges takes `O(m log m)`. - Union-find operations are nearly `O(m alpha(n))`. - Overall time: `O(m log m)`. - Overall space: `O(n + m)`. ## Common Pitfalls - Use 64-bit integer types for `total`, `mst_cost`, and the final answer. - Include self-loop costs in the total even though self-loops are never retained. - Do not combine parallel edges into a single edge, because each parallel copy contributes its own cost and at most one can be used in the tree. - Build a minimum spanning tree, not a maximum spanning tree. - The answer is not necessarily non-negative; it can be negative when all edge costs are negative.1d:[["$","script",null,{"type":"application/ld+json","dangerouslySetInnerHTML":{"__html":"{\"@context\":\"https://schema.org\",\"@type\":\"LearningResource\",\"learningResourceType\":\"Coding Question\",\"name\":\"Salesforce Channel Optimization\",\"description\":\"Salesforce Channel Optimization In a Salesforce-powered organization, different departments are represented as connected undirected nodes in a network with a total of org_nodes nodes numbered from 1 to org_nodes . Each node corresponds to a department, and the communication channels between these departments are represented as edges that connect org_from[i] to org_to[i] with associated cost org_weight[i] . The organization needs to optimize its system by removing unnecessary communication channe\",\"educationalLevel\":\"medium\",\"about\":{\"@type\":\"Organization\",\"name\":\"Cisco_23july\"},\"provider\":{\"@type\":\"Organization\",\"name\":\"OAHelper\",\"url\":\"https://oahelper.in\"},\"isPartOf\":{\"@type\":\"WebSite\",\"name\":\"OAHelper\",\"url\":\"https://oahelper.in\"},\"url\":\"https://oahelper.in/problems/NTE1Nnww/salesforce-channel-optimization\"}"}}],["$","script",null,{"type":"application/ld+json","dangerouslySetInnerHTML":{"__html":"{\"@context\":\"https://schema.org\",\"@type\":\"BreadcrumbList\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https://oahelper.in/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Problems\",\"item\":\"https://oahelper.in/problems\"},{\"@type\":\"ListItem\",\"position\":3,\"name\":\"Salesforce Channel Optimization\",\"item\":\"https://oahelper.in/problems/NTE1Nnww/salesforce-channel-optimization\"}]}"}}],["$","section",null,{"className":"sr-only","aria-hidden":"true","children":[["$","p",null,{"children":["Company: ","Cisco_23july"]}],["$","p",null,{"children":["Difficulty: ","medium"]}],false,["$","div",null,{"children":[["$","h2",null,{"children":"Problem Statement"}],["$","p",null,{"children":"Salesforce Channel Optimization In a Salesforce-powered organization, different departments are represented as connected undirected nodes in a network with a total of org_nodes nodes numbered from 1 to org_nodes . Each node corresponds to a department, and the communication channels between these departments are represented as edges that connect org_from[i] to org_to[i] with associated cost org_weight[i] . The organization needs to optimize its system by removing unnecessary communication channels between departments while maintaining full connectivity, i.e. each department must be able to reach every other department either directly or through a sequence of channels. After the optimization, exactly org_nodes - 1 channels may remain, and they must keep all departments connected — that is, the retained channels form a spanning tree of the organization. Your task is to determine the maximum possible sum of communication channel costs that can be removed. Note: All the communication chann"}]]}],false,["$","nav",null,{"aria-label":"Related company pages","children":[["$","$Lb",null,{"href":"/company-questions/cisco23july","children":["More ","Cisco_23july"," OA questions"]}],["$","$Lb",null,{"href":"/interview-experiences","children":"Interview experiences"}]]}]]}],["$","$L24",null,{"id":"NTE1Nnww","initialQuestion":{"id":"NTE1Nnww","title":"Salesforce Channel Optimization","google_doc_link":null,"problem_statement":"$25","solution_cpp":"$26","solution_python":"import sys\n\n\ndef main():\n data = sys.stdin.buffer.read().split()\n if not data:\n return\n pos = 0\n n = int(data[pos]); pos += 1\n m = int(data[pos]); pos += 1\n edges = []\n total = 0\n for _ in range(m):\n u = int(data[pos]); v = int(data[pos + 1]); w = int(data[pos + 2])\n pos += 3\n total += w\n if u != v:\n edges.append((w, u, v))\n edges.sort()\n parent = list(range(n + 1))\n\n def find(x):\n root = x\n while parent[root] != root:\n root = parent[root]\n while parent[x] != root:\n parent[x], x = root, parent[x]\n return root\n\n kept = 0\n used = 0\n for w, u, v in edges:\n ru = find(u)\n rv = find(v)\n if ru != rv:\n parent[ru] = rv\n kept += w\n used += 1\n if used == n - 1:\n break\n print(total - kept)\n\n\nif __name__ == \"__main__\":\n main()\n","solution_java":null,"pregiven_code_cpp":"#include \n\nusing namespace std;\n\nlong long getMaxRemovedChannelCost(int org_nodes, vector org_from,\n vector org_to, vector org_weight) {\n // Write your code here\n return 0;\n}\n\nint main() {\n ios::sync_with_stdio(false);\n cin.tie(nullptr);\n\n int org_nodes, org_edges;\n if (!(cin >> org_nodes >> org_edges)) return 0;\n\n vector org_from(org_edges), org_to(org_edges), org_weight(org_edges);\n for (int i = 0; i < org_edges; i++) {\n cin >> org_from[i] >> org_to[i] >> org_weight[i];\n }\n\n cout << getMaxRemovedChannelCost(org_nodes, org_from, org_to, org_weight) << \"\\n\";\n return 0;\n}\n","pregiven_code_python":"import sys\n\n\ndef getMaxRemovedChannelCost(org_nodes, org_from, org_to, org_weight):\n # Write your code here\n return 0\n\n\ndef main():\n data = sys.stdin.buffer.read().split()\n if not data:\n return\n org_nodes = int(data[0])\n org_edges = int(data[1])\n org_from = []\n org_to = []\n org_weight = []\n pos = 2\n for _ in range(org_edges):\n org_from.append(int(data[pos]))\n org_to.append(int(data[pos + 1]))\n org_weight.append(int(data[pos + 2]))\n pos += 3\n print(getMaxRemovedChannelCost(org_nodes, org_from, org_to, org_weight))\n\n\nif __name__ == \"__main__\":\n main()\n","pregiven_code_java":"$27","difficulty":"medium","question_type":"coding","premium_required":0,"created_at":"2026-07-23T11:42:58.45126+00:00","updated_at":"2026-08-10T00:02:42.794567+00:00","solution_code":null,"solution":null,"pregiven_code":"#include \n\nusing namespace std;\n\nlong long getMaxRemovedChannelCost(int org_nodes, vector org_from,\n vector org_to, vector org_weight) {\n // Write your code here\n return 0;\n}\n\nint main() {\n ios::sync_with_stdio(false);\n cin.tie(nullptr);\n\n int org_nodes, org_edges;\n if (!(cin >> org_nodes >> org_edges)) return 0;\n\n vector org_from(org_edges), org_to(org_edges), org_weight(org_edges);\n for (int i = 0; i < org_edges; i++) {\n cin >> org_from[i] >> org_to[i] >> org_weight[i];\n }\n\n cout << getMaxRemovedChannelCost(org_nodes, org_from, org_to, org_weight) << \"\\n\";\n return 0;\n}\n","input_test_case":"[\"4 5\\n1 2 1\\n1 3 1\\n1 4 1\\n3 2 2\\n4 2 2\\n\", \"3 3\\n1 2 -2\\n1 3 4\\n3 1 -1\\n\"]","output_test_case":"[\"4\\n\", \"4\\n\"]","lc_tags":"[\"Sorting\", \"Greedy\", \"Tree\", \"Graph Theory\", \"Union-Find\", \"Minimum Spanning Tree\"]","visual_animation":null,"difficulty_score":45,"md_problem_statement":"$28","unique_company_name":"cisco","sql_solution":null,"bash_solution":null,"js_solution":null,"editorial":"$29","hidden_test_cases_blob_count":80,"youtube_tutorial":null,"prompt_solution":null,"campus_type":null,"college_name":null,"role":null,"hidden_test_cases_ref":null,"is_mock_oa":false,"publication_status":"published","has_image":true,"company_name":"Cisco_23july","is_first_in_company":true,"company_ref":"MTYxNXww","total_test_cases":15,"hidden_test_cases_count":13},"isQotdToday":false,"qotdReward":5}]] 1f:null 23:[["$","title","0",{"children":"Salesforce Channel Optimization - Cisco_23july OA Question | OAHelper"}],["$","meta","1",{"name":"description","content":"Salesforce Channel Optimization (Cisco_23july OA) - medium: Salesforce Channel Optimization In a Salesforce-powered organization, different departments are represented as connected undirected nodes in a network with a to…"}],["$","meta","2",{"name":"author","content":"OAHelper Team"}],["$","meta","3",{"name":"keywords","content":"Cisco_23july OA question, Cisco_23july online assessment, Salesforce Channel Optimization, medium, online assessment, coding question, OA practice, interview preparation"}],["$","meta","4",{"name":"robots","content":"index, follow"}],["$","meta","5",{"name":"googlebot","content":"index, follow, max-video-preview:-1, max-image-preview:large, max-snippet:-1"}],["$","link","6",{"rel":"canonical","href":"https://oahelper.in/problems/NTE1Nnww/salesforce-channel-optimization"}],["$","meta","7",{"name":"google-site-verification","content":"MCxApq58khiH0y4KRigRUpoTS3ckefkhoCSHRIRLiXo"}],["$","meta","8",{"property":"og:title","content":"Salesforce Channel Optimization - Cisco_23july OA Question | OAHelper"}],["$","meta","9",{"property":"og:description","content":"Salesforce Channel Optimization (Cisco_23july OA) - medium: Salesforce Channel Optimization In a Salesforce-powered organization, different departments are represented as connected undirected nodes in a network with a to…"}],["$","meta","10",{"property":"og:url","content":"https://oahelper.in/problems/NTE1Nnww/salesforce-channel-optimization"}],["$","meta","11",{"property":"og:site_name","content":"OAHelper"}],["$","meta","12",{"property":"og:image","content":"https://oahelper.in/campus-ceo-favicon.png?v=11"}],["$","meta","13",{"property":"og:image:width","content":"256"}],["$","meta","14",{"property":"og:image:height","content":"256"}],["$","meta","15",{"property":"og:image:alt","content":"Salesforce Channel Optimization - Cisco_23july OA Question"}],["$","meta","16",{"property":"og:type","content":"website"}],["$","meta","17",{"name":"twitter:card","content":"summary_large_image"}],["$","meta","18",{"name":"twitter:title","content":"Salesforce Channel Optimization - Cisco_23july OA Question | OAHelper"}],["$","meta","19",{"name":"twitter:description","content":"Salesforce Channel Optimization (Cisco_23july OA) - medium: Salesforce Channel Optimization In a Salesforce-powered organization, different departments are represented as connected undirected nodes in a network with a to…"}],["$","meta","20",{"name":"twitter:image","content":"https://oahelper.in/campus-ceo-favicon.png?v=11"}],["$","link","21",{"rel":"shortcut icon","href":"/campus-ceo-favicon.png?v=11"}],["$","link","22",{"rel":"icon","href":"/campus-ceo-favicon-128.png?v=11","sizes":"128x128","type":"image/png"}],["$","link","23",{"rel":"icon","href":"/campus-ceo-favicon.png?v=11","sizes":"256x256","type":"image/png"}],["$","link","24",{"rel":"icon","href":"/campus-ceo-favicon-512.png?v=11","sizes":"512x512","type":"image/png"}],["$","link","25",{"rel":"apple-touch-icon","href":"/campus-ceo-favicon-512.png?v=11","sizes":"180x180","type":"image/png"}],["$","$L2a","26",{}]]