In this HackerEarth Scheduling War problem solution, Prateek and Chintu are working on different projects both with equal priority. They both need to run some batches of processes. A batch has processes which need some systems to run them irrespective of the number of process running on each dependent system. If a batch runs then the dependent systems are occupied by its processes. No system can run processes from different projects and thus a system can process only chintu's processes or prateek's processes. Their manager being a stylo creep has allowed prateek to run his batches. Chintu felt offended and complained the CTO directly due to which the manager came up with a condition that if chintu can increase the number of processes running in total by replacing some or all of prateeks processes then only he can run his batches. Chintu wants to maximize the total processes running in order to show the manager his skills. Help him complete his task.
HackerEarth Scheduling War problem solution.
#include<bits/stdc++.h>
using namespace std;
struct edge
{
int u, v, w;
};
struct Maxflow
{
int s, d;
vector<edge> edges;
vector<vector<int>> adj;
vector<int> lvl, ptr;
Maxflow(int sz, int s, int d) : s(s), d(d)
{
adj.resize(sz);
lvl.resize(sz);
ptr.resize(sz);
}
void add_edge(int a, int b, int c)
{
int sz = edges.size();
edges.push_back({a, b, c});
edges.push_back({b, a, 0});
adj[a].push_back(sz);
adj[b].push_back(sz + 1);
}
bool bfs()
{
fill(lvl.begin(), lvl.end(), -1);
queue<int> q;
q.push(s);
lvl[s] = 0;
while(!q.empty())
{
int cur = q.front();
q.pop();
for(int i: adj[cur])
{
edge e = edges[i];
int nxt = e.v;
if(lvl[nxt] == -1 && e.w > 0)
{
lvl[nxt] = lvl[cur] + 1;
q.push(nxt);
}
}
}
return lvl[d] != -1;
}
int flow(int cur, int f = 1000000000)
{
if(cur == d)
return f;
for( ; ptr[cur] < adj[cur].size(); ptr[cur]++)
{
int i = adj[cur][ptr[cur]];
edge e = edges[i];
int nxt = e.v;
if(lvl[nxt] != lvl[cur] + 1 || e.w < 1)
continue;
int tmp = flow(nxt, min(f, e.w));
if(tmp)
{
edges[i].w -= tmp;
edges[i ^ 1].w += tmp;
return tmp;
}
}
return 0;
}
int maxflow()
{
int res = 0;
while (bfs())
{
fill(ptr.begin(), ptr.end(), 0);
label:
{
int tmp = flow(s);
if (tmp)
{
res += tmp;
goto label;
}
}
}
return res;
}
};
int main()
{
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int t, n, m, k, w;
vector<int> arr(110);
cin >> n;
for(int i = 0; i < n; i++)
cin >> arr[i];
cin >> m;
int sz = n + m;
int s = sz;
int d = s + 1, tot = 0;
Maxflow mf(sz + 4, s, d);
for(int i = 0; i < m; i++)
{
cin >> t;
while(t--)
{
cin >> k;
mf.add_edge(n + i, k - 1, 1000000000);
}
cin >> w;
mf.add_edge(s, n + i, w);
tot += w;
}
for(int i = 0; i < n; i++)
mf.add_edge(i, d, arr[i]);
cout << tot - mf.maxflow();
return 0;
}Second solution in java.
import java.io.*;
import java.util.*;
class TestClass {
public static void main(String args[] ) throws Exception {
/*
* Read input from stdin and provide input before running
https://www.hackerearth.com/practice/algorithms/graphs/maximum-flow/practice-problems/algorithm/scheduling-war/
*/
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
String[] str = br.readLine().split(" ");
int[] pr = new int[n];
for(int i=0; i<n; i++)
{
pr[i] = Integer.parseInt(str[i]);
}
int bp = Integer.parseInt(br.readLine());
HashSet<Integer> set = new HashSet<Integer>();
int max = 0;
int sum2 = 0;
for(int i=0; i<bp; i++)
{
str = br.readLine().split(" ");
int s = Integer.parseInt(str[0]);
int p = Integer.parseInt(str[str.length-1]);
int total = 0;
for(int j=1; j<=s; j++)
{
total += pr[Integer.parseInt(str[j])-1];
set.add(Integer.parseInt(str[j])-1);
}
if(total<p)
{
max += p-total;
}
sum2 += p;
}
Iterator it = set.iterator();
int sum3 = 0;
while(it.hasNext())
{
sum3 += pr[(Integer)it.next()];
}
if(sum2 > sum3)
{
System.out.println(sum2-sum3);
}
else if(max > 0)
{
System.out.println(max);
}
else
{
System.out.println(0);
}
}
}
0 Comments