PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: mexomerf
Tester: tabr
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
Finding connected components, Eulerian circuits (to prove correctness)
PROBLEM:
You are given a simple weighted graph, each of whose vertices is colored either black or white.
In one move, you can choose an edge such that its endpoints have opposite colors, and reduce its weight by 1. After this move, the colors of its endpoints will swap.
Find the minimum number of operations required to reach a state where all edge weights are equal, and every vertex has the same color it started with.
EXPLANATION:
Let’s try to solve a slightly easier problem: fix a weight W, and we’ll try to compute the cost of getting every edge down to W (or decide that it’s impossible).
For simplicity, we’ll assume the graph is connected - operations in different connected components are independent, so every weight can be made W if and only if every weight within each component can be made W separately.
First off, since weights can only decrease, if any edge has weight \lt W initially it’s clearly impossible.
So, we only need to look at values of W that are \leq m, where m is the smallest weight of any input edge.
Now, since W is fixed, we know exactly how many times each edge needs to be operated on (it’s x-W for an edge with weight x).
For vertex u, let c_u denote the number of times it’ll be involved in an operation - this is exactly the sum of the number of moves required for each edge incident to u.
Since the color of a vertex changes each time it’s involved in an operation, it’s easy to see that if every vertex is to return to its original color, every c_u must be even.
On the other hand, this condition isn’t quite sufficient: for example, if every vertex has the same color (and there are at least two vertices), it’s impossible make even a single move.
As it happens, this is the only edge case!
That is, if every c_u is even, and either the connected component is a singleton or contains vertices of both colors, it’s always possible to perform the requisite number of moves.
Proof
First, let’s make a couple of reductions.
For each edge (u, v) that needs to be operated on x times, we instead replace it with x edges between u and v, each of which needs to be operated on exactly once.
We now have a multigraph, albeit unweighted.
Lemma: In this new graph, consider a trail u_1 \to u_2 \to u_3 \to \ldots \to u_k such that u_1 and u_k have different colors.
There exists a way to operate on each of these edges exactly once.
Proof
We prove the result using induction on k.
If k = 2, the result is trivially true - there is only one edge with its endpoints having opposite colors, we can perform the operation on it directly.
When k \gt 2, we consider two cases:
- If u_1 and u_2 have different colors, operate on the edge joining them.
Now, u_2 and u_k have different colors, and the u_2 \to u_k trail can be inductively solved. - If u_1 and u_2 have the same color, u_2 and u_k will have different colors.
First solve for the u_2 \to u_k trail inductively, which causes the color of u_2 to flip (if u_2 appears somewhere in the middle of the trail, it’ll have two operations performed using it which won’t change its color; apart from that the operation with u_3 will change its color once, resulting in a flipped color overall).
Now u_1 and u_2 have different colors, so operate on the edge joining them to finish.
Next, observe that c_u is exactly the degree of u in this multigraph.
It’s well-known that when each degree of a connected multigraph is even, it contains an Eulerian circuit (and vice versa). Find any such Eulerian circuit.
Since the graph contains both white and black vertices, there will definitely exist an edge connecting a black vertex to a white vertex - let (u, v) be such an edge.
Re-orient the Eulerian circuit to be u \to v\to v_1 \to v_2 \to \ldots \to v_k \to u.
First operate on the edge (u, v), which is possible by virtue of our choice.
The remaining part of the circuit is v\to v_1 \to v_2 \to \ldots \to v_k \to u. Observe that this is a trail whose first and last vertices have different colors, so the lemma above tells us that every edge in it can be operated on exactly once, as desired!
This completes the proof of possibility.
We now know how to solve for a single target weight W.
To finish, observe that we don’t need to check too many candidates of W: in fact, it’s enough to check only m, m-1, and m-2 (recall that m is the minimum input edge weight).
This is because, if a solution exists for some W \lt m-2, then W+2 will be valid as well:
- All edge requirements will decrease by 2. However, since W \lt m-2, these requirements will still remain positive, so connected components won’t change.
In particular, this means the criterion about connected components’ colors remains the same (i.e they are either singletons or have both colors). - All edge requirements decrease by 2, so each c_u will decrease by an even number; in particular they’ll all remain even.
So, check for each of W, W-1, W-2 whether it’s possible or not.
If all three fail the checks, the answer is -1; otherwise it’s the minimum cost among whichever ones do have a solution.
TIME COMPLEXITY:
\mathcal{O}(N+M) per testcase.
CODE:
Author's code (C++)
// library link: https://github.com/manan-grover/My-CP-Library/blob/main/library.cpp
#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;
#define asc(i,a,n) for(I i=a;i<n;i++)
#define dsc(i,a,n) for(I i=n-1;i>=a;i--)
#define forw(it,x) for(A it=(x).begin();it!=(x).end();it++)
#define bacw(it,x) for(A it=(x).rbegin();it!=(x).rend();it++)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define lb(x) lower_bound(x)
#define ub(x) upper_bound(x)
#define fbo(x) find_by_order(x)
#define ook(x) order_of_key(x)
#define all(x) (x).begin(),(x).end()
#define sz(x) (I)((x).size())
#define clr(x) (x).clear()
#define U unsigned
#define I long long int
#define S string
#define C char
#define D long double
#define A auto
#define B bool
#define CM(x) complex<x>
#define V(x) vector<x>
#define P(x,y) pair<x,y>
#define OS(x) set<x>
#define US(x) unordered_set<x>
#define OMS(x) multiset<x>
#define UMS(x) unordered_multiset<x>
#define OM(x,y) map<x,y>
#define UM(x,y) unordered_map<x,y>
#define OMM(x,y) multimap<x,y>
#define UMM(x,y) unordered_multimap<x,y>
#define BS(x) bitset<x>
#define L(x) list<x>
#define Q(x) queue<x>
#define PBS(x) tree<x,null_type,less<I>,rb_tree_tag,tree_order_statistics_node_update>
#define PBM(x,y) tree<x,y,less<I>,rb_tree_tag,tree_order_statistics_node_update>
#define pi (D)acos(-1)
#define md 1000000007
#define rnd randGen(rng)
long long readInt(long long l, long long r, char endd) {
long long x = 0;
int cnt = 0;
int fi = -1;
bool is_neg = false;
while (true) {
char g = getchar();
if (g == '-') {
assert(fi == -1);
is_neg = true;
continue;
}
if ('0' <= g && g <= '9') {
x *= 10;
x += g - '0';
if (cnt == 0) {
fi = g - '0';
}
cnt++;
assert(fi != 0 || cnt == 1);
assert(fi != 0 || is_neg == false);
assert(!(cnt > 19 || (cnt == 19 && fi > 1)));
}
else if (g == endd) {
assert(cnt > 0);
if (is_neg) {
x = -x;
}
assert(l <= x && x <= r);
return x;
}
else {
assert(false);
}
}
}
string readString(int l, int r, char endd) {
string ret = "";
int cnt = 0;
while (true) {
char g = getchar();
assert(g != -1);
if (g == endd) {
break;
}
cnt++;
ret += g;
}
assert(l <= cnt && cnt <= r);
return ret;
}
void dfs(I x,I vis[],UM(I,I) tr[],I fin,I a[],B &euler,B &same,B &white,B &black){
if(vis[x]){
return;
}
if(a[x]){
black=true;
}else{
white=true;
}
vis[x]=1;
I sum=0;
forw(it,tr[x]){
sum+=(*it).se-fin;
if((*it).se!=fin){
same=false;
}else{
continue; // added
}
dfs((*it).fi,vis,tr,fin,a,euler,same,white,black);
}
if(sum%2){
euler=false;
}
}
int main(){
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
uniform_int_distribution<I> randGen;
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
I t;
cin>>t;
while(t--){
I n,m;
cin>>n>>m;
I a[n];
asc(i,0,n){
cin>>a[i];
}
UM(I,I) tr[n];
I mn=LLONG_MAX;
I tot=0;
asc(i,0,m){
I u,v,w;
cin>>u>>v>>w;
if(m==500000&&i>m-10){
cerr<<u<<" "<<v<<" "<<w<<endl;
}
tot+=w;
mn=min(w,mn);
u--;
v--;
tr[u][v]=w;
tr[v][u]=w;
}
tot-=m*mn;
I vis[n]={};
I ans=tot;
asc(i,0,n){
B euler=true;
B same=true;
B white=false;
B black=false;
dfs(i,vis,tr,mn,a,euler,same,white,black);
if(!same && !(euler & white & black)){
ans=-1;
}
vis[i]=0;
}
if(ans==-1){
mn--;
ans=tot+m;
asc(i,0,n){
B euler=true;
B same=true;
B white=false;
B black=false;
dfs(i,vis,tr,mn,a,euler,same,white,black);
if(!same && !(euler & white & black)){
ans=-1;
}
vis[i]=0;
}
}
if(ans==-1){ // added (copied from line 172 - 186)
mn--;
ans=tot+m*2; // changed m -> m*2
asc(i,0,n){
B euler=true;
B same=true;
B white=false;
B black=false;
dfs(i,vis,tr,mn,a,euler,same,white,black);
if(!same && !(euler & white & black)){
ans=-1;
}
vis[i]=0;
}
}
cout<<ans<<"\n";
}
return 0;
}
Tester's code (C++)
#include <bits/stdc++.h>
using namespace std;
struct dsu {
vector<int> p;
vector<int> sz;
int n;
dsu(int _n) : n(_n) {
p = vector<int>(n);
iota(p.begin(), p.end(), 0);
sz = vector<int>(n, 1);
}
inline int get(int x) {
if (p[x] == x) {
return x;
} else {
return p[x] = get(p[x]);
}
}
inline bool unite(int x, int y) {
x = get(x);
y = get(y);
if (x == y) {
return false;
}
p[x] = y;
sz[y] += sz[x];
return true;
}
inline bool same(int x, int y) {
return (get(x) == get(y));
}
inline int size(int x) {
return sz[get(x)];
}
inline bool root(int x) {
return (x == get(x));
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int tt;
cin >> tt;
while (tt--) {
int n, m;
cin >> n >> m;
vector<int> color(n);
for (int i = 0; i < n; i++) {
cin >> color[i];
}
vector<int> x(m), y(m), w(m);
for (int i = 0; i < m; i++) {
cin >> x[i] >> y[i] >> w[i];
x[i]--;
y[i]--;
}
long long ans = -1;
int mn = *min_element(w.begin(), w.end());
// we only need to check mn, mn - 1, and mn - 2
for (int z = mn; z >= mn - 2; z--) {
int ok = 1;
// each connected component must be an eulearian curcuit
vector<long long> sum(n);
for (int i = 0; i < m; i++) {
sum[x[i]] += w[i] - z;
sum[y[i]] += w[i] - z;
}
for (int i = 0; i < n; i++) {
if (sum[i] % 2 == 1) {
ok = 0;
}
}
// make connected components
// ignore the edge with w[i] == z since no operations are needed
dsu d(n);
for (int i = 0; i < m; i++) {
if (w[i] > z) {
d.unite(x[i], y[i]);
}
}
vector<vector<int>> g(n);
for (int i = 0; i < n; i++) {
g[d.get(i)].emplace_back(i);
}
for (int i = 0; i < n; i++) {
int black = 0, white = 0, need_ops = 0;
for (int v : g[i]) {
if (color[v]) {
black = 1;
} else {
white = 1;
}
if (sum[v] > 0) {
need_ops = 1;
}
}
if (need_ops) {
if (!(black && white)) {
ok = 0;
}
}
}
if (ok) {
ans = 0;
for (int i = 0; i < m; i++) {
ans += w[i] - z;
}
break;
}
}
cout << ans << '\n';
}
return 0;
}