FAIRCOST - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: yeamin_kaiser
Tester: raysh07
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

Finding bridges, binary search

PROBLEM:

You’re given a connected undirected weighted graph.
The cost of an edge equals its weight, multiplied by the number of pairs of vertices it disconnects when removed.

The cost of an edge is distributed among its endpoints, as non-negative integers.
The cost of a vertex equals the sum of values it receives from its incident edges.

Find the minimum possible value of the maximum cost of a vertex, under some valid distribution.

EXPLANATION:

First, let’s find the cost of each edge.
We already know the weight of each edge, so we really only need to know the number of pairs of vertices disconnected by the removal of each edge.

For this, note that edges whose removal doesn’t disconnect the graph will end up with a cost of 0 anyway, so we only really care about edges whose removal disconnects the graph, i.e, bridges.
Further, each bridge separates the graph into exactly two connected components; so the number of pairs of disconnected vertices is just the product of their sizes.

Finding the bridges in a graph (and consequently, the sizes of the disconnected components) is a classical problem that can be solved in linear time, and a tutorial can be found here for example.

Now that we know the costs of each edge, let’s move on to the second part: minimizing the maximum value.
This screams binary search, which is exactly what we’ll do!

All we need to do, is to be able to quickly check whether for a fixed x, all the constraints can be satisfied.
That is, can we distribute costs from each edge to its endpoints, such that in the end all the vertices have costs of \leq x?

Notice that we only care about bridges - and in particular, the bridges of a graph form a forest so we only need to be able to check condition for trees, instead of arbitrary graphs!

Checking the condition for a tree can be done greedily: pick a leaf u and its parent p_u of the tree, then give as much as possible to u and all the remaining to its parent.
Repeat this process till you either exhaust all edges, then check if every node has value \leq x.

This can be done in \mathcal{O}(N) time, for a solution in \mathcal{O}(N\log{10^{18}}) time overall.

TIME COMPLEXITY

\mathcal{O}(N\log{10^{18}}) per testcase.

CODE:

Author's code (C++) 
#include <bits/stdc++.h>
using namespace std;

#define ll long long


const int N = 1e5 + 10;
vector<pair<int, int>> g[N];
vector<pair<int, int>> tr[N];
vector<pair<int, int>> ed;
int vis[N], low[N], now = 0, cnum=0;
int isbridge[2 * N];
int comp[N], csz[N];
ll cost[2 * N];
int deg[N], sz[N];

void dfs(int u, int p) {
    low[u] = vis[u] = ++now;
    for (auto [v, id] : g[u]) {
        if (v != p) {
            if (vis[v])
                low[u] = min(low[u], vis[v]);
            else {
                dfs(v, u);
                low[u] = min(low[u], low[v]);
                if (low[v] > vis[u]) isbridge[id] = 1;
            }
        }
    }
}

void dfs2(int s) {
    vis[s] = 1;
    comp[s] = cnum;
    csz[cnum]++;
    for (auto [v, id] : g[s]) {
        if (!isbridge[id]) {
            if (!vis[v]) dfs2(v);
        }
    }
}

void process_bridge(int n, int m) {
    for (int i = 0; i <= n; i++) vis[i] = 0;
    dfs(1, 0);
    for (int i = 0; i <= n; i++) vis[i] = 0;
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {
            cnum++;
            dfs2(i);
        }
    }
    for (int i = 0; i < m; i++) {
        int u=ed[i].first;
        int v=ed[i].second;
        if(comp[u]==comp[v]) continue;
        deg[u]++;
        deg[v]++;
        tr[comp[u]].push_back({comp[v],i});
        tr[comp[v]].push_back({comp[u],i});
    }
}

void calc(int i, int p, ll tot){
    sz[i]=csz[i];
    for(auto [v,id]: tr[i]){
        if(v==p) continue;
        calc(v,i,tot);
        ll val=sz[v]*(tot-sz[v]);
        val*=cost[id];
        cost[id]=val;
        sz[i]+=sz[v];
    }

}

int check(ll x, int n){
    queue<int> q;
    vector<ll> cap(n+1,x);
    vector<int> used(n+1,0);
    vector<int> dc(n+1);
    for(int i=1;i<=n;i++){
        dc[i]=deg[i];
        if(deg[i]==1) q.push(i);
    }

    while(q.size()){
        int curr=q.front();
        q.pop();
        used[curr]=1;
        if(dc[curr]!=1) continue;
        for(auto [v,id]:g[curr]){
            if(used[v]||!isbridge[id]) continue;
            
            ll val=cost[id];
            ll tk=min(val,cap[curr]);
            val-=tk;
            if(cap[v]<val) return 0;
            cap[v]-=val;
            dc[v]--;
            if(dc[v]==1) q.push(v);
            
        }
    }
    return 1;
}


signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin>>u>>v>>w;
        g[u].push_back({v, i});
        g[v].push_back({u, i});
        cost[i] = w;
        ed.push_back({u, v});
    }
    process_bridge(n, m);

    calc(1,0,n);
    ll l=0,r=1e17;
    ll ans=-1;
    while(l<=r){
        ll ss=(l+r)/2;
        if(check(ss,n)){
            ans=ss;
            r=ss-1;
        }
        else l=ss+1;
    }
    cout<<ans<<"\n";

}
Tester's code (C++) 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18
#define f first
#define s second

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

const int N = 1e5 + 69;
int n, m;
vector <pair<int, int>> adj[N];
int par[N], sz[N], d[N], ok[N], c[N], e[N];
int lift[N][19];
bool vis[N];

void dfs(int u){
    vis[u] = true;
    sz[u] = 1;
    for (auto [v, w] : adj[u]){
        if (!vis[v]){
            d[v] = d[u] + 1;
            dfs(v);
            sz[u] += sz[v];
            lift[v][0] = u;
            par[v] = u;
        }
    }
}

void dfs2(int u){
    vis[u] = true;
    
    for (auto [v, w] : adj[u]){
        if (!vis[v]){
            dfs2(v);
            ok[u] += ok[v];
        }
    }
}

void dfs3(int u){
    vis[u] = true;
    for (auto [v, w] : adj[u]){
        if (!vis[v]){
            dfs3(v);
            int give = e[v];
            if (give > w) w = 0;
            else w -= give;
            
            e[u] -= w;
        }
    }
}

bool check(int x){
    for (int i = 1; i <= n; i++) e[i] = x, vis[i] = false;
    
    dfs3(1);
    
    for (int i = 1; i <= n; i++) if (e[i] < 0) return false;
    return true;
}

void Solve() 
{
    cin >> n >> m;
    
    for (int i = 1; i <= m; i++){
        int u, v, w;
        cin >> u >> v >> w;
        
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    
    dfs(1);
    
    for (int j = 1; j <= 18; j++){
        for (int i = 1; i <= n; i++){
            lift[i][j] = lift[lift[i][j - 1]][j - 1];
        }
    }
    
    auto lca = [&](int a, int b){
        if (d[a] < d[b]) swap(a, b);
        
        int del = d[a] - d[b];
        for (int i = 0; i < 19; i++) if (del >> i & 1){
            a = lift[a][i];
        }
        
        if (a == b) return a;
        
        for (int i = 18; i >= 0; i--) if (lift[a][i] != lift[b][i]){
            a = lift[a][i];
            b = lift[b][i];
        }
        
        return lift[a][0];
    };
    
    auto addedge = [&](int a, int b){
        ok[a]++;
        ok[b]++;
        ok[lca(a, b)] -= 2;
    };
    
    for (int i = 1; i <= n; i++){
        for (auto [x, w] : adj[i]){
            if (par[x] != i && par[i] != x){
                addedge(i, x);
            }
        }
    }
    
    for (int i = 1; i <= n; i++) vis[i] = false;
    
    dfs2(1);
    
    int sum = 0;
    
    for (int i = 1; i <= n; i++){
        
        for (auto &[x, w] : adj[i]){
            if (x == par[i] && ok[i] == 0) w = sz[i] * (n - sz[i]) * w;
            else if (i == par[x] && ok[x] == 0) w = sz[x] * (n - sz[x]) * w;
            else w = 0;
        }
    }
    
    int l = 0, r = 1e18;
    while (r != l){
        int mid = (l + r) / 2;
        
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    
    cout << l << "\n";
}

int32_t main() 
{
    auto begin = std::chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
 //   cin >> t;
    for(int i = 1; i <= t; i++) 
    {
        //cout << "Case #" << i << ": ";
        Solve();
    }
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
    return 0;
}
1 Like
2

How can we show that the answer is at most 10^{18}? A loose upper bound is that the cost of one edge is K(N/2)^2 \approx 10^{15}, and there up to 10^5 edges, so this gives an upper bound of about 10^{20}. Of course, this is pretty coarse; I’d like to know what’s the tightest upper bound you’ve found for these constraints.

3

in particular, the bridges of a graph form a forest so we only need to be able to check condition for trees, instead of arbitrary graphs!

please explain??

4

If M is the maximum cost of a single edge, the answer is bounded by M.
This is because you can root each tree arbitrarily, then give the entire edge’s cost to the lower vertex - this way, the root receives nothing and every other vertex receives the cost of exactly one edge.

This bounds the answer to about \frac14 \cdot 10^{15} (which is fairly tight, since a bamboo with all weights 10^5 nearly attains this bound)

5

A bridge is an edge that further disconnects a graph when removed.
In particular, if (u, v) is a bridge, then removing it must disconnect vertices u and v; otherwise no other pair will be disconnected (do you see why?)

This means that a bridge of a graph can never lie on a cycle, since removing one edge from a cycle doesn’t disconnect any of its vertices.
None of the bridges lie on cycles → the graph formed by taking all bridges doesn’t contain any cycles, which is what a forest is.

6

I understand how to find bridges using DFS tree technique but unable to find the sizes of connected components it creates. Can you explain this, or share your code

7

Once you understand what’s going on with the DFS tree, it follows almost immediately (highly recommend reading the linked blog).

If the edge between u and v is a bridge, where u is the parent of v in the DFS tree, then the components created are exactly the subtree of v, and everything else.
So all you need to do is compute subtree sizes while doing the dfs - you can note that the setter’s and tester’s code linked above both do this.

1 Like
8

oh thankyou!!