PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: raysh07
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Medium
PREREQUISITES:
Bitmask DP, DSU/DFS/BFS to check connectivity of a graph
PROBLEM:
Alice has a weighted connected undirected graph. Each edge has a weight of either 0 or 1, denoted A_i.
Bob knows the graph, but not the weights.
The graph is called solvable if Bob can determine the edge weights using at most 2M of the following operations:
- Choose a binary vector B of length M.
Then, receive the weight of the MST of the graph with edge weights set to W_i = A_i\cdot B_i.
Alice can flip edge weights between 0 and 1.
Find the minimum number of changes that need to be made to obtain a solvable graph.
EXPLANATION:
First, we must understand when a graph is solvable, so let’s try to develop a solution to that.
Let f(B) denote the weight of the MST obtained bu querying using the array B.
Bob starts out with absolutely no information, so a reasonable starting point is to query using B = [1, 1, 1, \ldots, 1], which just returns the MST of the initial graph.
Let T = f([1, 1, \ldots, 1]).
Consider what happens if we flip exactly one element of this array to 0, i.e. query using the array [1, 1, \ldots, 1, 0, 1, 1, \ldots, 1].
If this 0 is at index i,
- If A_i = 0, then the weight of this edge in the final graph is going to be 0 independent of B_i.
Weights haven’t changed, so the MST in this case is going to be the same as the original graph - namely T. - If A_i = 1, this edge now has weight 0, while all the other edges haven’t changed.
So,- If edge i was part of some MST of the base graph, it will remain part of the MST of the new graph, but the MST weight will reduce by 1, so it’ll be T-1.
- if edge i wasn’t part of any MST of the base graph, after reduction it may or may not be part of an MST.
If it isn’t, the cost will be T since we’ll be using the other (unchanged) edges anyway; while if it is, the cost will become T-1.
Either way, the new MST cost will be either T or T-1.
Further, if the cost when querying some i like this is T-1, we know for sure it’s an edge with a weight of 1.
This way, we’ve used M+1 queries to find (some of) the edges with weight 1.
Now let’s look at only the edges unknown to us, i.e. the ones which resulted in a query value of T - specifically, consider the subgraph induced by these edges.
If this induced subgraph contains a cycle anywhere, it’s impossible to determine the edges uniquely from MST weights: for example, it’s impossible to distinguish a cycle with all the weights being 0 from a cycle with one edge having weight 1 and everything else being 0, since in both cases the vertices of the cycle can be spanned for cost 0 without needing to use any information about the last edge.
What if it doesn’t contain any cycles?
Then, observe that all these edges must have weight 0.
Why?
So, the induced subgraph of edges with weight 0 must be a forest.
We have a nice separation here: after the MST queries that set each individual edge to 0, the ones which had a change are exactly the ones with weight 1.
In particular, it can be seen that each weight 1 edge must connect two different components of this forest: if it didn’t, then changing its weight to 0 would result in the MST weight not changing, which is a contradiction.
We’ve hence obtained a characterization for solvable graphs:
- The subgraph induced by edges with weight 0 must be a forest.
- Each weight 1 edge must connect two different components of this forest.
We must now compute the minimum number of edge weight changes that will let us accomplish this.
Note that from the above characterization we also see why it’s always possible to obtain a solvable graph: a simple construction is to just set every edge weight to 1.
Let’s transform the problem a bit first to make it easier to deal with: set every edge whose weight is 0, to 1 (and add 1 to the answer for each such change).
After this, we only need to decide which edges to flip back to 0, with the cost of flipping an edge being -1 if it was originally a 0 (since we already spent one operation on flipping it, we could’ve just not done that), and 1 if it was originally a 1 (we just need to flip it).
When deciding which edges to flip back to 0, a couple of conditions must be taken care of:
- The edges flipped to 0 must form a forest.
- There should not be an unflipped edge whose endpoints both lie in the same connected component of flipped edges.
The second condition really just says that the subgraph induced by the flipped edges must be a forest.
We can now use dynamic programming to compute the minimum cost of doing this, using the fact that N is pretty small.
For a subset S of vertices, let dp[S] denote the minimum cost of flipping edges in S, such that the induced subgraph of flipped edges in S is a forest.
Transitions for this are relatively straightforward: we want a forest, so let’s fix a subset S' \subseteq S to be one component of this forest.
Then, update dp[S] with cost[S'] + dp[S \setminus S'], where cost[S'] is the cost of flipping all the edges in S' to make it a tree.
One thing to be careful about here is that S' may not be a tree after flipping all its edges - so cost[S'] only makes sense for those subsets whose induced subgraphs are connected and acyclic; make sure to check this beforehand.
If the subgraph induced by S' isn’t a tree, you can set cost[S'] = \infty for simplicity.
The cost[S] values can be precomputed in \mathcal{O}(2^N \cdot N^2) time by just going through every mask and looking through all the edges in each one.
Once the costs are known, the dp[S] values are found in \mathcal{O}(3^N) time since we’re just doing submask enumeration with constant time transitions.
The answer is given by dp[\{1, 2, \ldots, N\}], plus the initial cost of changing all edge weights to 1.
For N \leq 13, this is more than fast enough.
TIME COMPLEXITY:
\mathcal{O}(2^N \cdot N^2 + 3^N) per testcase.
CODE:
Editorialist's code (C++)
// #include <bits/allocator.h>
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include "bits/stdc++.h"
using namespace std;
using ll = long long int;
mt19937_64 RNG(chrono::high_resolution_clock::now().time_since_epoch().count());
struct DSU {
private:
std::vector<int> parent_or_size;
public:
DSU(int n = 1): parent_or_size(n, -1) {}
int get_root(int u) {
if (parent_or_size[u] < 0) return u;
return parent_or_size[u] = get_root(parent_or_size[u]);
}
int size(int u) { return -parent_or_size[get_root(u)]; }
bool same_set(int u, int v) {return get_root(u) == get_root(v); }
bool merge(int u, int v) {
u = get_root(u), v = get_root(v);
if (u == v) return false;
if (parent_or_size[u] > parent_or_size[v]) std::swap(u, v);
parent_or_size[u] += parent_or_size[v];
parent_or_size[v] = u;
return true;
}
std::vector<std::vector<int>> group_up() {
int n = parent_or_size.size();
std::vector<std::vector<int>> groups(n);
for (int i = 0; i < n; ++i) {
groups[get_root(i)].push_back(i);
}
groups.erase(std::remove_if(groups.begin(), groups.end(), [&](auto &s) { return s.empty(); }), groups.end());
return groups;
}
};
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
int t; cin >> t;
while (t--) {
int n, m; cin >> n >> m;
vector adj(n, vector(n, 0));
int ans = 0;
for (int i = 0; i < m; ++i) {
int u, v, w; cin >> u >> v >> w;
--u, --v;
adj[u][v] = adj[v][u] = w+1;
ans += w == 0;
}
vector cost(1 << n, 0);
for (int mask = 0; mask < 1 << n; ++mask) {
DSU D(n);
bool tree = true;
for (int i = 0; i < n; ++i) if (mask >> i & 1) {
for (int j = i+1; j < n; ++j) if (mask >> j & 1) {
if (adj[i][j]) {
tree &= D.merge(i, j);
cost[mask] -= adj[i][j] == 1;
}
}
}
if (!tree) cost[mask] = 1e6;
}
vector dp(1 << n, 0);
for (int mask = 1; mask < 1 << n; ++mask) {
dp[mask] = 1e6;
for (int sub = mask; sub > 0; sub = (sub - 1) & mask) {
dp[mask] = min(dp[mask], cost[sub] + dp[mask ^ sub]);
}
}
cout << ans + dp.back() << '\n';
}
}
Author's code (C++)
#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define INF (int)1e9
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
struct ufds{
vector <int> root, sz;
int n;
void init(int nn){
n = nn;
root.resize(n + 1);
sz.resize(n + 1, 1);
for (int i = 1; i <= n; i++) root[i] = i;
}
int find(int x){
if (root[x] == x) return x;
return root[x] = find(root[x]);
}
bool unite(int x, int y){
x = find(x); y = find(y);
if (x == y) return false;
if (sz[y] > sz[x]) swap(x, y);
sz[x] += sz[y];
root[y] = x;
return true;
}
};
int type;
int check(int N, int M, vector <int> U, vector <int> V, vector <int> W){
int n = N;
int m = M;
ufds uf;
uf.init(n + 1);
bool good = true;
for (int i = 0; i < m; i++){
if (W[i] == 0){
good &= uf.unite(U[i], V[i]);
}
}
for (int i = 0; i < m; i++){
if (W[i] == 1){
good &= uf.find(U[i]) != uf.find(V[i]);
}
}
return 1 - good;
}
int find_min_changes(int N, int M, vector <int> U, vector <int> V, vector <int> W){
// for each mask, compute the minimum it takes to be good
// mask is good iff all the edges within it are a tree
int n = N;
int m = M;
vector<vector<int>> adj(n, vector<int>(n, -1));
int base = 0;
for (int i = 0; i < m; i++){
adj[U[i] - 1][V[i] - 1] = W[i];
adj[V[i] - 1][U[i] - 1] = W[i];
base += 1 - W[i]; // assuming all W[i] = 1
}
vector <int> cost(1 << n, INF);
for (int i = 1; i < (1 << n); i++){
vector <int> v;
for (int j = 0; j < n; j++){
if (i >> j & 1){
v.push_back(j);
}
}
ufds uf;
uf.init(n);
int edges = 0;
int cs = 0;
bool good = true;
for (int j = 0; j < v.size(); j++){
int x = v[j];
for (int k = j + 1; k < v.size(); k++){
int y = v[k];
if (adj[x][y] != -1){
good &= uf.unite(x, y);
++edges;
if (adj[x][y] == 0){
cs += -1;
} else {
cs += 1;
}
if (!good){
break;
}
}
}
if (!good){
break;
}
}
good &= (edges + 1) == (int)v.size();
if (good){
cost[i] = cs;
}
}
vector <int> dp(1 << n, INF);
dp[0] = 0;
for (int i = 1; i < (1 << n); i++){
int p = 0;
while (!(i >> p & 1)){
++p;
}
int mask = i ^ (1 << p);
for (int s = mask; ; s = (s - 1) & mask){
dp[i] = min(dp[i], dp[s] + cost[i ^ s]);
if (s == 0){
break;
}
}
}
int ans = base + dp[(1 << n) - 1];
return ans;
}
void Solve()
{
int n, m; cin >> n >> m;
vector <int> u(m), v(m), w(m);
for (int i = 0; i < m; i++){
cin >> u[i] >> v[i] >> w[i];
}
cout << find_min_changes(n, m, u, v, w) << "\n";
}
int32_t main()
{
auto begin = std::chrono::high_resolution_clock::now();
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
// freopen("in", "r", stdin);
// freopen("out", "w", stdout);
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;
}
Tester's code (C++)
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl
#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)
template<typename T>
void amin(T &a, T b) {
a = min(a,b);
}
template<typename T>
void amax(T &a, T b) {
a = max(a,b);
}
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
/*
*/
const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;
struct DSU {
vector<int> par, rankk, siz;
DSU() {
}
DSU(int n) {
init(n);
}
void init(int n) {
par = vector<int>(n + 1);
rankk = vector<int>(n + 1);
siz = vector<int>(n + 1);
rep(i, n + 1) create(i);
}
void create(int u) {
par[u] = u;
rankk[u] = 0;
siz[u] = 1;
}
int find(int u) {
if (u == par[u]) return u;
else return par[u] = find(par[u]);
}
bool same(int u, int v) {
return find(u) == find(v);
}
void merge(int u, int v) {
u = find(u), v = find(v);
if (u == v) return;
if (rankk[u] == rankk[v]) rankk[u]++;
if (rankk[u] < rankk[v]) swap(u, v);
par[v] = u;
siz[u] += siz[v];
}
};
void solve(int test_case){
ll n,m; cin >> n >> m;
vector<array<ll,3>> edges;
rep(i,m){
ll u,v,w; cin >> u >> v >> w;
u--, v--;
edges.pb({u,v,w});
}
// find cost of each subset being connected
vector<ll> cost(1<<n,inf2);
rep1(mask,(1<<n)-1){
DSU dsu(n); // only containing 0 edges within the cc
ll curr_cost = 0;
ll sb = setbits(mask);
ll edge_cnt = 0;
for(auto [u,v,w] : edges){
ll in_cc = 0;
if(mask&(1<<u)) in_cc++;
if(mask&(1<<v)) in_cc++;
if(in_cc == 2){
edge_cnt++;
if(dsu.same(u,v)){
curr_cost = inf2;
}
else{
dsu.merge(u,v);
curr_cost += w;
}
}
else if(in_cc == 1){
curr_cost += !w;
}
}
if(edge_cnt != sb-1){
curr_cost = inf2;
}
cost[mask] = curr_cost;
}
vector<ll> dp(1<<n,inf2);
dp[0] = 0;
rep1(mask,(1<<n)-1){
for(int s = mask; s; s = (s-1)&mask){
amin(dp[mask],cost[s]+dp[mask^s]);
}
}
ll ans = dp[(1<<n)-1]>>1;
cout << ans << endl;
}
int main()
{
fastio;
int t = 1;
cin >> t;
rep1(i, t) {
solve(i);
}
return 0;
}