Widening Channels
Autumn tournament
Submission name: channels.cpp
Problem summary
Lakes are linked by undirected channels of known widths. The whole network is connected for a boat of width 1. Find the minimum number of channels that must be widened so a boat of width k can travel between every pair of lakes.
Input
n m; m triples i j width; then k.
Output
The minimum number of channels to widen.
Constraints
2 ≤ n ≤ 1000; 2 ≤ m ≤ 100,000; channel widths and k: 1…200.
Worked example
An independently prepared example for this explanation.
Input
4 3 1 2 5 2 3 1 3 4 5 4
Output
1
Solution analysis
- Keep only channels whose width is already at least k.
- Count connected components with iterative DFS. Call that number c.
- Each widened channel can merge at most two current components, so at least c−1 are required.
- The original connected network becomes a connected graph of components. Choose a spanning tree of that graph: widening its c−1 channels suffices.
Why it works
The lower bound comes from reducing c components to 1, one merge at a time. Original connectivity guarantees a component-spanning tree, attaining that bound.
Watch out. The goal is to minimize how many channels change, not the total increase in their widths.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: The lower bound comes from reducing c components to 1, one merge at a time. Original
// connectivity guarantees a component-spanning tree, attaining that bound.
#include<iostream>
#include<vector>
#include<tuple>
#include<stack>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,m;
cin>>n>>m;
vector<tuple<int,int,int>>edges(m);
for(auto&[a,b,w]:edges){
cin>>a>>b>>w;
}
int k;
cin>>k;
vector<vector<int>>g(n+1);
for(auto[a,b,w]:edges){
if(w>=k){
g[a].push_back(b);
g[b].push_back(a);
}
}
vector<bool>seen(n+1);
int components=0;
for(int s=1;s<=n;++s){
if(!seen[s]){
++components;
stack<int>st;
st.push(s);
seen[s]=true;
while(!st.empty()){
int v=st.top();
st.pop();
for(int u:g[v]){
if(!seen[u]){
seen[u]=true;
st.push(u);
}
}
}
}
}
cout<<components-1<<'\n';
}