GPHLBL - Editorial

Author: Manish Tanwar
Tester: Rahul Dugar
Editorialist: Ritesh Gupta

Medium-Hard

PREREQUISITES:

Strongly Connected Component, Lower Bound Max-Flow

PROBLEM:

You are given a graph G with N nodes and M edges. You want to label each edge with either 1 or 2. Each of the labels has different costs, c_1 and c_2 respectively. You want to assign the labels in a way that cost is as minimum as possible and with that you have to satisfy Q constraints.

For each valid i, the i-th constraint is that the number of edges in a set S_i with the label x_i should be between l_i and r_i (inclusive); S_i is determined by a given vertex w_i and the type of this constraint t_i as follows:

• t_i = 1: S_i = Out(N(w_i))
• t_i = 2: S_i = In(N(w_i))
• t_i = 3: S_i = Out(\{w_i\})
• t_i = 4: S_i = In(\{w_i\})

Where,

• For each u, v \in V, R(u, v) is true if v can be reached from u or false otherwise. Specifically, if u = v, it is always true.
• For each v \in V, a set of vertices N(v) = \{u \in V \mid R(u, v) \wedge R(v, u)\}.
• For each subset U \subseteq V, two sets of edges Out(U) = \{(u,v) \in E \mid u \in U\} and In(U) = \{(v,u) \in E \mid u \in U\}.

QUICK EXPLANATION:

• We can say that N(v) is nothing but one of the SCC components of the given graph. It could be easily found using the standard SCC algorithm.
• So, now we know that all four queries are affecting the edges related to some set of vertices.
• We can consider c_1 < c_2 always. If it is not then we can swap them and process the queries accordingly.
• We should also uniform the Q constraints. Means, we need to change all the constraints into either terms of c_1 or in c_2. In our case, let’s change them in c_1.
• Now, we can solve the problem for c_1 with a lower bound maxflow where we model it as a c_1 type label. With this, we create a four layer model where:
• Source to the first layer represents the scc’s outgoing demands
• First to second layer represents the node’s outgoing demands
• Second to third layer represents the edges
• Third to fourth layer represents node’s incoming demands
• Fourth to sink represents scc’s incoming demands.

EXPLANATION:

Observation 1: N(v) represents the one of the strongly connected components which contains v. As from the definition of SCC, we know that the vertices which are reachable from one another can be part of the same component. So, here if we narrow down the given definition of R and N, we can say that N(v) is the SCC of the given graph G which contains the node v.

Observation 2: Without loss of generality, we can assume that c_1 < c_2 and if it is not then we swap them and update the given Q constraints as well. We can also convert all the Q constraints for a single label i.e. 1. This will simplify the problem and now we need to look only for the constraints for one label, for our purpose we convert all of them into label 1.

How to convert ?: Let’s say outDegree(v) is equal to the number of edges going out from v and inDegree(v) is equal to the number of edges coming into v. Now, we can say that:

• inEdgesOfLabel1(v) + inEdgesOfLabel2(v) = inDegree(v)
• So, any incoming constraint of vertex v with label 2 of given range [l_i, r_i] can be converted into label 1 with range equal to [inDegree(v) - r_i, inDegree(v) - l_i]
• outEdgesOfLabel1(v) + outEdgesOfLabel2(v) = outDegree(v)
• So, any outgoing constraint of vertex v with label 2 of given range [l_i, r_i] can be converted into label 1 with range equal to [outDegree(v) - r_i, outDegree(v) - l_i]

The same works for SCC components also. From here on, we assume that all constraints are of label 1. If there is no constraints for any vertex v or SCC’s then we can assume that incoming constraints is equal to range [0, inDegree(v)] and outgoing constraints is equal to range [0, outDegree(v)]

What if there are multiple constraints for a single vertex / SCC ? : If there are L constraints are there for any single vertex v then we can create a new constraints in which range is given by [maximum of left limit of all L constraints, minimum of right limit of all L constraints]

Is a valid assignment possible ?: If there is a vertex or SCC for which the constraint i is such that it’s r_i is less than l_i then the answer is not possible or no valid assignment is possible to satisfy the constraints.

Let’s try to solve the problem, so we want to minimize the cost which directly implies that we need to maximize the number of edges of the label 1, as we had already fixed it in observation 2. And that’s pretty useful because this actually redirected the solution towards max-flow which will basically be related to flows.

We would use flow with dependencies/lowerbound maxflow. We need not to know the insites to solve the problem but let’s see what it actually means. Normally in max flows, we have some capacity for every edge and we just want to find the maximal flow that we can push from the sink to the source such that we will always be pushing at most the capacity flow through every edge.

However, when we talk about flow with dependencies, we also have an additional constraint for every edge that’s like the lower bounds for every edge. So in other words instead of having just a capacity, we also have the lower bound for this. Basically, for some set of edges, there exists an interval (left, right) which will basically define the flow in terms of minimum and maximum capacity.

Now, we want to model our problem so that we can apply the flow with dependencies/lower bound maxflow over it to get the answer. But this is not an easy part. So, here is the trick - we will construct the graph such that we’ll have a source, we’ll also have a sync and the intermediate things will be there.

We will have four layers in between where the first layer will have strongly connected components and it has incoming edges from source to them which have the bounded by outgoing demand constraints. Then we have a second layer which consists of vertices and have incoming from strongly connected components which represents the outgoing demand for vertex and we can say that every vertex should be connected with only one SCC.

Then we have actual edges which are actually taking the flow for us, you can assume that it has two states only 0 or 1 where 0 means label with 1 and other is with label 2. We again have vertices with outgoing demand in SCC and then SCC to sink.

So, here we are basically modifying the given graph in such a way so that given constraints can be incorporated to the new graph itself and by applying lower bound max-flow to the new graph, we get the maximum number edges, we can label with the minimum value label. As we have four types of constraints, outgoing and incoming demand for vertex and outgoing and incoming demand for SCC.

We know that any vertex is part of exactly one SCC of the given graph, so we can say that the incoming demand of any vertex is directly coming of it’s SCC. This way all SCC’s are getting their demand from source and vertex is getting their incoming demands from their respective SCC’s. Now, any SCC is outsourcing their incoming to the vertex and we know it’s outgoing capacity. So, we need to put the outgoing demand constraints of any SCC on the incoming edge they are getting from source. Same way, we are putting outgoing demand constraints over the incoming edge received by any vertex from their SCC.

This way the first half is constructed and the same way we can do for the second half to consider the incoming demands. Now, how to connect these two graphs, it is pretty easy to say that the connection should be based on the actual edges of the graph as it is vertex to vertex mapping and we can not pass more than one quantity (here, we are talking about edges) from any two vertexes. So, it is either 0 or 1 which resembles it is not labeled with the minimum value label or labeled with the minimum value label respectively.

Once we are building this then we need to just apply the lower bound max-flow over it assuming that we are maximizing the edges of the 1 type label according to observation 2. If there is no possibility for c_1 then the answer is not possible otherwise if max-flow gives as x then x number of edges are labeled with 1 and (m-x) number of edges are labeled with 2. So, the minimum cost would be c_1 * x + c_2 * (m-x)

SOLUTIONS:

Setter's Solution
#include <bits/stdc++.h>
using namespace std;
template<class T> ostream& operator<<(ostream &os, vector<T> V){os << "[ "; for(auto v : V) os << v << " "; return os << "]";}
template<class L, class R> ostream& operator<<(ostream &os, pair<L,R> P){return os << "(" << P.first << "," << P.second << ")";}
#ifndef ONLINE_JUDGE
#define TRACE
#endif

#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){ cout << name << " : " << arg1 << endl; }
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){const char* comma = strchr(names + 1, ',');cout.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);}
#else
#define trace(...) 1
#endif
#define mp make_pair
#define pb push_back
#define endl '\n'
#define F first
#define S second
#define I insert
typedef long double ld;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<int> vi;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef vector<pll> vpll;
typedef vector<pii> vpii;

// code credits - http://e-maxx.ru/algo/dinic
struct edge {
int x, y;
ll cap, flow;
};

struct DinicFlow {
const ll inf = (1e16);
vector <edge> e;
vector <int> cur, d;
vector < vector <int> > adj;
int n, source, sink;

DinicFlow() {}

DinicFlow(int v) {
n = v;
cur = vector <int> (n + 1);
d = vector <int> (n + 1);
adj = vector < vector <int> > (n + 1);
}

void addEdge(int from, int to, ll cap) {
edge e1 = {from, to, cap, 0};
edge e2 = {to, from, 0, 0};
}

int bfs() {
queue <int> q;
for(int i = 0; i <= n; ++i) d[i] = -1;
q.push(source); d[source] = 0;
while(!q.empty() and d[sink] < 0) {
int x = q.front(); q.pop();
for(int i = 0; i < (int)adj[x].size(); ++i) {
int id = adj[x][i], y = e[id].y;
if(d[y] < 0 and e[id].flow < e[id].cap) {
q.push(y); d[y] = d[x] + 1;
}
}
}
return d[sink] >= 0;
}

ll dfs(int x, ll flow) {
if(!flow) return 0;
if(x == sink) return flow;
int id = adj[x][cur[x]], y = e[id].y;
if(d[y] != d[x] + 1) continue;
ll pushed = dfs(y, min(flow, e[id].cap - e[id].flow));
if(pushed) {
e[id].flow += pushed;
e[id ^ 1].flow -= pushed;
return pushed;
}
}
return 0;
}

ll maxFlow(int src, int snk) {
this->source = src; this->sink = snk;
ll flow = 0;
while(bfs()) {
for(int i = 0; i <= n; ++i) cur[i] = 0;
while(int pushed = dfs(source, inf)) {
flow += pushed;
}
}
return flow;
}
};

const int N = 1e5+1;
bool visit[N];

int n,m,q,a,b,c1,c2;
int scc[N], scc_cnt, scc_ecnt[N][2];

void dfs(int f){
visit[f]=1;
for(auto z : adj[f]) if(!visit[z]) dfs(z);
dfs_time.pb(f);
}

void dfs2(int f){
visit[f] = 1; scc[f] = scc_cnt;
for(auto z : rev_adj[f]) if(!visit[z]) dfs2(z);
}

void compute_scc(){
dfs_time.clear();
for(int i=1;i<=n;i++)
if(!visit[i]) dfs(i);
reverse(dfs_time.begin(), dfs_time.end());
fill(visit+1, visit+n+1, 0);
for(int v : dfs_time){
if(visit[v]) continue;
scc_cnt++;
dfs2(v);
}
for(int i=1;i<=n;i++){
}
}

inline void constraint(pii& p, int l, int r){
p.F = max(p.F, l); p.S = min(p.S, r);
}

pii v_cons[N][2], scc_cons[N][2];
ll inf = 1e14;

int getMaxFlow(){
int total = 2*n + 2*scc_cnt;
int src = ++total, sink = ++total, src1 = ++total, sink1 = ++total;
DinicFlow g(total);
ll sat_flow = 0;
int wrong_flag = 0;

vll demands(total);

auto add_edge = [&](pii c, int u, int v){
if(c.F > c.S) wrong_flag = 1;
demands[u] += c.F;
demands[v] -= c.F;
};

for(int i=1;i<=n;i++) {
// middle layer (l3), flow: [0,1]
}
for(int i=1;i<=scc_cnt;i++){
}

for(int i=1;i<=total-2;i++){
if(demands[i] < 0) g.addEdge(src1, i, -demands[i]);
else if(demands[i] > 0) g.addEdge(i, sink1, demands[i]), sat_flow += demands[i];
}

if(wrong_flag) return -1;
ll mflow = g.maxFlow(src1, sink1);
if(mflow != sat_flow) return -1;

return g.maxFlow(src, sink);
}

ll solve(){
cin>>n>>m>>q;
fill(visit, visit+n+1, 0);
for(int i=1;i<=n;i++) for(int j : {0,1})
v_cons[i][j] = {0, m}, scc_cons[i][j] = {0,m}, scc_ecnt[i][j] = 0;
scc_cnt = 0;

compute_scc();

cin>>c1>>c2;
int flip = (c1 > c2);
if(c1 > c2) swap(c1,c2);

for(int i=0;i<q;i++){
int type, v, label, l, r;
cin>>type>>v>>label>>l>>r;
int le = l, re = r;
label--;
label ^= flip;
if(type <= 2){
type--;
if(label){
int tot = scc_ecnt[scc[v]][type];
re = tot - l; le = tot - r;
}
constraint(scc_cons[scc[v]][type], le, re);
}
else{
type -= 3;
if(label){
re = tot - l; le = tot - r;
}
constraint(v_cons[v][type], le, re);
}
}

int flow = getMaxFlow();
if(flow == -1) return -1;
ll ans = (ll)c1*flow + (ll)c2*(m-flow);
return ans;
}

int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int t; cin>>t;
while(t--) cout<<solve()<<'\n';
}

Tester's Solution
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#ifndef rd
#define trace(...)
#define endl '\n'
#endif
#define pb push_back
#define fi first
#define se second
#define int long long
typedef long long ll;
typedef long double f80;
#define double long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define sz(x) ((long long)x.size())
#define fr(a,b,c) for(int a=b; a<=c; a++)
#define rep(a,b,c) for(int a=b; a<c; a++)
#define trav(a,x) for(auto &a:x)
#define all(con) con.begin(),con.end()
const ll infl=0x3f3f3f3f3f3f3f3fLL;
const int infi=0x3f3f3f3f;
//const int mod=998244353;
const int mod=1000000007;
typedef vector<int> vi;
typedef vector<ll> vl;

typedef tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update> oset;
auto clk=clock();
mt19937_64 rang(chrono::high_resolution_clock::now().time_since_epoch().count());
int rng(int lim) {
uniform_int_distribution<int> uid(0,lim-1);
return uid(rang);
}
int powm(int a, int b) {
int res=1;
while(b) {
if(b&1)
res=(res*a)%mod;
a=(a*a)%mod;
b>>=1;
}
return res;
}

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) {
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;
}
long long readIntSp(long long l, long long r) {
}
long long readIntLn(long long l, long long r) {
}
string readStringLn(int l, int r) {
}
string readStringSp(int l, int r) {
}

int sum_n=0,sum_m=0,sum_q=0;
#define rsz(x, n) x.resize(n)
#define clr(x) x.clear()
class SCC {
public:
int n,cnt; // cnt -> number of scc's formed
vector<vector<int>> g,rg,sg,comp; // sg -> dag with all nodes compressed.
vector<int> scc,order;
vector<bool> vis;
void reset() {
clr(g),clr(rg),clr(sg),clr(comp),clr(scc),clr(order),clr(vis);
}
void init(int _n) {
reset();
n=_n,cnt=0;
_n+=2;
rsz(g, _n),rsz(rg,_n),rsz(sg,_n),rsz(comp,_n);
scc.resize(_n,0);
vis.resize(_n,0);
}
void add(int u, int v) {
g[u].push_back(v);
rg[v].push_back(u);
}
void compute() {
fr(i, 1, n)
if(!vis[i])
dfs1(i);
fill(all(vis),0);
for(int i=n-1; i>=0; i--)
if(!vis[order[i]])
dfs2(order[i],++cnt);
}
void dfs1(int u) {
vis[u]=1;
for(int v : g[u])
if(!vis[v])
dfs1(v);
order.pb(u);
}
void dfs2(int u, int c) {
vis[u]=1;
scc[u]=c;
comp[c].pb(u);
for(int v : rg[u]) {
if(!vis[v])
dfs2(v,c);
if(vis[v]&&c!=scc[v])
sg[scc[v]].pb(c);
}
}
};

struct Edge {
int from,to,cap,flow,index;
Edge(int from, int to, int cap, int flow, int index) :
from(from), to(to), cap(cap), flow(flow), index(index) {
}
};
struct PushRelabel {
int N;
vector<vector<Edge> > G;
vector<ll> excess;
vector<int> dist,active,count;
queue<int> Q;
PushRelabel(int N) :
N(N), G(N), excess(N), dist(N), active(N), count(2*N) {
}
void AddEdge(int from, int to, int cap) {
G[from].push_back(Edge(from,to,cap,0,G[to].size()));
if(from==to)
G[from].back().index++;
G[to].push_back(Edge(to,from,0,0,G[from].size()-1)); // for bidirectional set cap.
}
void Enqueue(int v) {
if(!active[v]&&excess[v]>0) {
active[v]=true;
Q.push(v);
}
}
void Push(Edge &e) {
int amt=min(excess[e.from],ll(e.cap-e.flow));
if(dist[e.from]<=dist[e.to]||amt==0)
return;
e.flow+=amt;
G[e.to][e.index].flow-=amt;
excess[e.to]+=amt;
excess[e.from]-=amt;
Enqueue(e.to);
}
void Gap(int k) {
fr(v, 0, N - 1) {
if(dist[v]<k)
continue;
count[dist[v]]--;
dist[v]=max(dist[v],N+1);
count[dist[v]]++;
Enqueue(v);
}
}
void Relabel(int v) {
count[dist[v]]--;
dist[v]=2*N;
fr(i, 0, G[v].size() - 1)
if(G[v][i].cap-G[v][i].flow>0)
dist[v]=min(dist[v],dist[G[v][i].to]+1);
count[dist[v]]++;
Enqueue(v);
}
void Discharge(int v) {
for(int i=0; excess[v]>0&&i<G[v].size(); i++)
Push(G[v][i]);
if(excess[v]>0) {
if(count[dist[v]]==1) {
Gap(dist[v]);
}
else
Relabel(v);
}
}
ll GetMaxFlow(int s, int t) {
count[0]=N-1;
count[N]=1;
dist[s]=N;
active[s]=active[t]=1;
fr(i, 0, (int)G[s].size() - 1) {
excess[s]+=G[s][i].cap;
Push(G[s][i]);
}
while(!Q.empty()) {
int v=Q.front();
Q.pop();
active[v]=0;
Discharge(v);
}
ll totflow=0;
fr(i, 0, (int)G[s].size() - 1)
totflow+=G[s][i].flow;
}
};
const int INF=infi;
struct MaxFlowLowerBound {
PushRelabel PR;
int N,s,t,s1,t1;
ll total_demands;
MaxFlowLowerBound(int N, int s, int t) :
N(N), PR(N+2), s(s), t(t), s1(N), t1(N+1), total_demands(0) {
}
void AddEdge(int from, int to, ll lo, ll hi) {
total_demands+=lo;
}
ll GetMaxFlow() {
if(PR.GetMaxFlow(s1,t1)<total_demands)
return -1;
PushRelabel PR1(N);
ll initial=0;
for(int i=0; i<N; i++) {
for(auto e : PR.G[i]) {
if(e.flow<0||e.cap==0)
continue;
if(e.to>=N)
continue;
if(i==t&&e.to==s) {
initial=e.flow;
continue;
}
}
}
return initial+PR1.GetMaxFlow(s,t);
}
};

const int N=100005;
int in[N],ut[N],oin[N],out[N];
pii il[N],ul[N];
pii oil[N],oul[N];
void solve() {
//	int n,m,q;
//	cin>>n>>m>>q;
fr(i,1,n) {
oil[i]={0,m};
oul[i]={0,m};
il[i]={0,m};
ul[i]={0,m};
in[i]=ut[i]=oin[i]=out[i]=0;
}
sum_n+=n;
sum_m+=m;
sum_q+=q;
assert(sum_n<=200000&&sum_m<=200000&&sum_q<=2000000);
SCC G;
G.init(n);
vector<pii> edg;
fr(i,1,m) {
//		int u,v;
//		cin>>u>>v;
assert(u!=v);
edg.pb({u,v});
}
G.compute();
for(auto e:edg) {
out[e.fi]++;
oin[e.se]++;
ut[G.scc[e.fi]]++;
in[G.scc[e.se]]++;
}
fr(i,1,n) {
oil[i].se=oin[i];
oul[i].se=out[i];
il[i].se=in[i];
ul[i].se=ut[i];
}
trace(ul[1]);
//	int c1,c2;
//	cin>>c1>>c2;
bool swapped=0;
if(c1>c2) {
swapped=1;
swap(c1,c2);
}
int src=2*n+2*G.cnt+1,sink=2*n+2*G.cnt+2;
MaxFlowLowerBound F(2*n+2*G.cnt+5,src,sink);
bool no=0;
fr(i,1,q) {
//		int t,w,x,l,r;
//		cin>>t>>w>>x>>l>>r;
if(G.scc[w]==1&&t<=2) {
trace(t,w,x,l,r,ul[1]);
}
if(t<=2)
w=G.scc[w];
if(swapped)
x^=3;
if(x==2) {
int total;
if(t==1) {
total=ut[w];
} else if(t==2) {
total=in[w];
} else if(t==3) {
total=out[w];
} else {
total=oin[w];
}
int nl=total-r,nr=total-l;
l=nl;
r=nr;
}
if(t==1) {
ul[w].fi=max(ul[w].fi,l);
ul[w].se=min(ul[w].se,r);
} else if(t==2) {
il[w].fi=max(il[w].fi,l);
il[w].se=min(il[w].se,r);
} else if(t==3) {
oul[w].fi=max(oul[w].fi,l);
oul[w].se=min(oul[w].se,r);
} else {
oil[w].fi=max(oil[w].fi,l);
oil[w].se=min(oil[w].se,r);
}
if(w==1&&t==1)
trace(ul[1],l,r);
}
fr(i,1,G.cnt)
if(ul[i].fi>ul[i].se||il[i].fi>il[i].se) {
no=1;
}
fr(i,1,n)
if(oul[i].fi>oul[i].se||oil[i].fi>oil[i].se)
no=1;
if(no) {
cout<<-1<<endl;
return;
}
fr(i,1,G.cnt) {
trace(src,2*n+i,ul[i]);
trace(2*n+G.cnt+i,sink,il[i]);
}
fr(i,1,n) {
trace(2*n+G.scc[i],i,oul[i]);
trace(n+i,2*n+G.cnt+G.scc[i],oil[i]);
}
for(auto i:edg)
int ans=F.GetMaxFlow();
if(~ans)
ans=m*c2+(c1-c2)*ans;
cout<<ans<<endl;
}

signed main() {
//	freopen("in.txt","r",stdin);
//	freopen("output3.txt","wb",stdout);
ios_base::sync_with_stdio(0),cin.tie(0);
srand(chrono::high_resolution_clock::now().time_since_epoch().count());
cout<<fixed<<setprecision(8);