PROBLEM LINK: FEBCON04
Author, Tester, Editorialist : John Zakkam
DIFFICULTY: HARD
PREREQUISITES:
Math ,Graph Theory, flow with demands.
PROBLEM:
There are two streets. First street has N1 houses. Second street has N2
houses. There are no connections between houses inside street1 and also street2. Some houses in street1 are connected to some houses in street2.
The houses are colored either red(R) or blue(B) or is colorless (U). Our task is to color connections in between houses in street one and two. To paint a connection red it takes r rupees and to paint a connection blue it takes b rupees. We have to color the connections in the minimum cost possible and also satisfying the properties for each red house, the number of red connections incident to it should be strictly greater than the number of blue connections incident to it and for each blue vertex, the number of blue connections incident to it should be strictly greater than the number of red connections incident to it. If there is no coloring that meets all the constraints, print one integer −1 Otherwise, print an integer c denoting the total cost of coloring, and a string consisting of m characters. The ith character should be U if the ith connection should be left uncolored, R if the ith connection should be painted red, or B if the ith connection should be painted blue. If there are multiple coloring s with minimum possible cost, print any of them.
EXPLANATION:
For this problem, we should sctually think of a flow solution. First of all, the network will consist of vertices and edges of the original graph. We somehow have to denote “red”, “blue” and “colorless” edges; we will do it as follows: each edge of the original graph corresponds to a bi-directional edge with capacity 1 in the network; if the flow goes from the left part to the right part along the edge, it is red; if the flow goes from right to left, it is a blue edge; and if there is no flow along the edge, it is colorless.
Now, we need to impose some constraints on the vertices. Consider some vertex v from the left part. Each red edge incident to it transfers one unit of flow from it to some other vertex, and each blue edge incident to it does the opposite. So, the difference between the number of blue and red edges incident to v is the amount of excess flow that has to be transfered somewhere else. If v is colorless, there are no constraints on the colors of edges, so this amount of excess flow does not matter — to model it, we can add a directed edge from source to v with infinite capacity, and a directed edge from v to sink with infinite capacity. What if v is red? At least one unit of flow should be transfered to it; so we add a directed edge from the source to v with infinite capacity such that there should be at least one unit of flow along it. And if v is blue, we need to transfer at least one unit of excess flow from it — so we add a directed edge from v to the sink with infinite capacity such that there is at least one unit of flow along it. The colors of the vertices in the right part can be modeled symmetrically.
Or you can model it with the help of the costs: if the flow along the edge should be between l and r, we can add two edges: one with capacity l and cost k (where k is a negative number with sufficiently large absolute value, for example, −109), and another with capacity r−l and cost 0.
Okay, now we know how to find at least one painting. How about finding the cheapest painting that meets all the constraints? One of the simplest ways to do it is to impose costs on the edges of the original graph: we can treat each edge of the original graph as a pair of directed edges, one going from left to right with capacity 1
and cost r, and another going from right to left with capacity 1 and cost b.
SOLUTIONS:
Setter's Solution
#include<bits/stdc++.h>
using namespace std;
const int N = 443;
int n1, n2, m, r, b;
string s1, s2;
int u[N];
int v[N];
struct edge
{
int y, c, f, cost;
edge() {};
edge(int y, int c, int f, int cost) : y(y), c(c), f(f), cost(cost) {};
};
int bal[N][N];
int s, t, oldS, oldT, V;
vector<int> g[N];
vector<edge> e;
void add(int x, int y, int c, int cost)
{
g[x].push_back(e.size());
e.push_back(edge(y, c, 0, cost));
g[y].push_back(e.size());
e.push_back(edge(x, 0, 0, -cost));
}
int rem(int num)
{
return e[num].c - e[num].f;
}
void add_LR(int x, int y, int l, int r, int cost)
{
int c = r - l;
if(l > 0)
{
add(s, y, l, cost);
add(x, t, l, cost);
}
if(c > 0)
{
add(x, y, c, cost);
}
}
int p[N];
int d[N];
int pe[N];
int inq[N];
bool enlarge()
{
for(int i = 0; i < V; i++)
{
d[i] = int(1e9);
p[i] = -1;
pe[i] = -1;
inq[i] = 0;
}
d[s] = 0;
queue<int> q;
q.push(s);
inq[s] = 1;
while(!q.empty())
{
int k = q.front();
q.pop();
inq[k] = 0;
for(auto z : g[k])
{
if(!rem(z)) continue;
if(d[e[z].y] > d[k] + e[z].cost)
{
p[e[z].y] = k;
pe[e[z].y] = z;
d[e[z].y] = d[k] + e[z].cost;
if(!inq[e[z].y])
{
q.push(e[z].y);
inq[e[z].y] = 1;
}
}
}
}
if(p[t] == -1)
return false;
int cur = t;
while(cur != s)
{
e[pe[cur]].f++;
e[pe[cur] ^ 1].f--;
cur = p[cur];
}
return true;
}
void add_edge(int x, int y)
{
add(x, y + n1, 1, r);
add(y + n1, x, 1, b);
}
void impose_left(int x)
{
if(s1[x] == 'R')
{
add_LR(oldS, x, 1, m, 0);
}
else if(s1[x] == 'B')
{
add_LR(x, oldT, 1, m, 0);
}
else
{
add(oldS, x, m, 0);
add(x, oldT, m, 0);
}
}
void impose_right(int x)
{
if(s2[x] == 'R')
{
add_LR(x + n1, oldT, 1, m, 0);
}
else if(s2[x] == 'B')
{
add_LR(oldS, x + n1, 1, m, 0);
}
else
{
add(oldS, x + n1, m, 0);
add(x + n1, oldT, m, 0);
}
}
void construct_bal()
{
for(int i = 0; i < n1; i++)
{
for(auto z : g[i])
{
if(e[z].y >= n1 && e[z].y < n1 + n2)
bal[i][e[z].y - n1] += e[z].f;
}
}
}
void find_ans()
{
int res = 0;
string w = "";
for(auto x : g[s])
if(rem(x))
{
cout << -1 << endl;
return;
}
for(int i = 0; i < m; i++)
{
if(bal[u[i]][v[i]] > 0)
{
bal[u[i]][v[i]]--;
res += r;
w += "R";
}
else if(bal[u[i]][v[i]] < 0)
{
bal[u[i]][v[i]]++;
res += b;
w += "B";
}
else w += "U";
}
cout << res << endl << w << endl;
}
int main()
{
cin >> n1 >> n2 >> m >> r >> b;
cin >> s1;
cin >> s2;
for(int i = 0; i < m; i++)
{
cin >> u[i] >> v[i];
u[i]--;
v[i]--;
}
oldS = n1 + n2;
oldT = oldS + 1;
s = oldT + 1;
t = s + 1;
V = t + 1;
for(int i = 0; i < n1; i++)
impose_left(i);
for(int i = 0; i < n2; i++)
impose_right(i);
for(int i = 0; i < m; i++)
add_edge(u[i], v[i]);
add(oldT, oldS, 100000, 0);
while(enlarge());
construct_bal();
find_ans();
}
Editorialist's Solution
#include<bits/stdc++.h>
using namespace std;
const int N = 443;
int n1, n2, m, r, b;
string s1, s2;
int u[N];
int v[N];
struct edge
{
int y, c, f, cost;
edge() {};
edge(int y, int c, int f, int cost) : y(y), c(c), f(f), cost(cost) {};
};
int bal[N][N];
int s, t, oldS, oldT, V;
vector<int> g[N];
vector<edge> e;
void add(int x, int y, int c, int cost)
{
g[x].push_back(e.size());
e.push_back(edge(y, c, 0, cost));
g[y].push_back(e.size());
e.push_back(edge(x, 0, 0, -cost));
}
int rem(int num)
{
return e[num].c - e[num].f;
}
void add_LR(int x, int y, int l, int r, int cost)
{
int c = r - l;
if(l > 0)
{
add(s, y, l, cost);
add(x, t, l, cost);
}
if(c > 0)
{
add(x, y, c, cost);
}
}
int p[N];
int d[N];
int pe[N];
int inq[N];
bool enlarge()
{
for(int i = 0; i < V; i++)
{
d[i] = int(1e9);
p[i] = -1;
pe[i] = -1;
inq[i] = 0;
}
d[s] = 0;
queue<int> q;
q.push(s);
inq[s] = 1;
while(!q.empty())
{
int k = q.front();
q.pop();
inq[k] = 0;
for(auto z : g[k])
{
if(!rem(z)) continue;
if(d[e[z].y] > d[k] + e[z].cost)
{
p[e[z].y] = k;
pe[e[z].y] = z;
d[e[z].y] = d[k] + e[z].cost;
if(!inq[e[z].y])
{
q.push(e[z].y);
inq[e[z].y] = 1;
}
}
}
}
if(p[t] == -1)
return false;
int cur = t;
while(cur != s)
{
e[pe[cur]].f++;
e[pe[cur] ^ 1].f--;
cur = p[cur];
}
return true;
}
void add_edge(int x, int y)
{
add(x, y + n1, 1, r);
add(y + n1, x, 1, b);
}
void impose_left(int x)
{
if(s1[x] == 'R')
{
add_LR(oldS, x, 1, m, 0);
}
else if(s1[x] == 'B')
{
add_LR(x, oldT, 1, m, 0);
}
else
{
add(oldS, x, m, 0);
add(x, oldT, m, 0);
}
}
void impose_right(int x)
{
if(s2[x] == 'R')
{
add_LR(x + n1, oldT, 1, m, 0);
}
else if(s2[x] == 'B')
{
add_LR(oldS, x + n1, 1, m, 0);
}
else
{
add(oldS, x + n1, m, 0);
add(x + n1, oldT, m, 0);
}
}
void construct_bal()
{
for(int i = 0; i < n1; i++)
{
for(auto z : g[i])
{
if(e[z].y >= n1 && e[z].y < n1 + n2)
bal[i][e[z].y - n1] += e[z].f;
}
}
}
void find_ans()
{
int res = 0;
string w = "";
for(auto x : g[s])
if(rem(x))
{
cout << -1 << endl;
return;
}
for(int i = 0; i < m; i++)
{
if(bal[u[i]][v[i]] > 0)
{
bal[u[i]][v[i]]--;
res += r;
w += "R";
}
else if(bal[u[i]][v[i]] < 0)
{
bal[u[i]][v[i]]++;
res += b;
w += "B";
}
else w += "U";
}
cout << res << endl << w << endl;
}
int main()
{
cin >> n1 >> n2 >> m >> r >> b;
cin >> s1;
cin >> s2;
for(int i = 0; i < m; i++)
{
cin >> u[i] >> v[i];
u[i]--;
v[i]--;
}
oldS = n1 + n2;
oldT = oldS + 1;
s = oldT + 1;
t = s + 1;
V = t + 1;
for(int i = 0; i < n1; i++)
impose_left(i);
for(int i = 0; i < n2; i++)
impose_right(i);
for(int i = 0; i < m; i++)
add_edge(u[i], v[i]);
add(oldT, oldS, 100000, 0);
while(enlarge());
construct_bal();
find_ans();
}