In this HackerEarth Mancunian, The Confectioner problem solution Mancunian wants to open his very own bakery in the city. Being an apprentice of the famous SAF who was known for his exquisite cake recipes, the residents of the city have similar high expectations from him.
There are M types of ingredients from which cakes are made, each of which has a cost. Each cake needs some number of these ingredients, not necessarily all of them. Initially, Mancunian has no ingredient present at his shop. He needs to buy the ones he needs. Once he buys some ingredient, he has access to an unlimited supply of it and does not need to ever buy it again.
At the grand opening of his bakery, Mancunian received orders from N customers, along with the price the customer is willing to pay for their ordered cake. Mancunian must decide to bake some of these cakes (not necessarily all) so that he can maximise his earnings. His earnings will be the money he earns from the sale of the cakes he bakes minus the cost of the ingredients he bought. Note that he may choose not to bake any cake.
Given a set of M ingredients available and a set of N cake orders, help Mancunian find the maximum amount he can earn.
HackerEarth Mancunian, The Confectioner problem solution.
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define MOD (1000000007LL)
#define LEFT(n) (2*(n))
#define RIGHT(n) (2*(n)+1)
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
ll pwr(ll base, ll p, ll mod = MOD){
ll ans = 1;while(p){if(p&1)ans=(ans*base)%mod;base=(base*base)%mod;p/=2;}return ans;
}
struct edge{
int a, b;
ll cap, flow;
edge(){}
edge(int a, int b, ll cap, ll flow){
this->a = a;
this->b = b;
this->cap = cap;
this->flow = flow;
}
};
int s, t, dist[5000], ptr[5000];
vector<edge> edgeList;
vector<int> adj[5000];
void add_edge(int a, int b, ll cap){
adj[a].pb(edgeList.size());
edgeList.pb(edge(a, b, cap, 0));
adj[b].pb(edgeList.size());
edgeList.pb(edge(b, a, 0, 0));
// cout<<"added edge "<<a<<" "<<b<<" "<<cap<<endl;
}
bool bfs(){
memset(dist, -1, sizeof(dist));
queue<int> qq;
dist[s] = 0;
qq.push(s);
while(!qq.empty()){
int v = qq.front();
qq.pop();
for(int i=0;i<(int)adj[v].size();i++){
int id = adj[v][i];
int to = v ^ edgeList[id].a ^ edgeList[id].b;
if(dist[to] == -1 && edgeList[id].flow < edgeList[id].cap){
dist[to] = dist[v]+1;
qq.push(to);
}
}
}
return (dist[t] != -1);
}
ll dfs(int v, ll flow){
if(!flow) return 0;
if(v == t) return flow;
for(;ptr[v]<(int)adj[v].size();ptr[v]++){
int id = adj[v][ptr[v]];
int to = v ^ edgeList[id].a ^ edgeList[id].b;
if(dist[to] != dist[v]+1) continue;
ll pushed = dfs(to, min(flow, edgeList[id].cap-edgeList[id].flow));
if(pushed > 0){
edgeList[id].flow += pushed;
edgeList[1^id].flow -= pushed;
return pushed;
}
}
return 0;
}
ll dinitz(){
ll ans = 0;
while(1){
if(!bfs()) break;
memset(ptr, 0, sizeof(ptr));
while(ll pushed = dfs(s, MOD))
ans += pushed;
}
return ans;
}
int n, m, cakes[205], ingred[205], arr[205][205];
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cin>>n>>m;
assert(n >= 1 && n <= 200);
assert(m >= 1 && m <= 200);
for(int i=1;i<=n;i++){
cin>>cakes[i];
assert(cakes[i] >= 1 && cakes[i] <= 1000*1000*1000);
}
for(int i=1;i<=m;i++){
cin>>ingred[i];
assert(ingred[i] >= 1 && ingred[i] <= 1000*1000*1000);
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
cin>>arr[i][j];
assert(arr[i][j] == 0 || arr[i][j] == 1);
}
s = 0; t = 1+n+m;
ll ans = 0;
for(int i=1;i<=n;i++){
ans += cakes[i];
add_edge(s, i, cakes[i]);
for(int j=1;j<=m;j++)
if(arr[i][j] == 1)
add_edge(i, n+j, MOD);
}
for(int i=1;i<=m;i++){
add_edge(n+i, t, ingred[i]);
}
ans -= dinitz();
cout<<ans;
return 0;
}
Second solution
#include <bits/stdc++.h>
using namespace std;
#define MAXN 1000005
#define INF 1e9
struct Edge
{int v,flow,C,rev;};
class Graph{
int V;
int *level ;
vector< Edge > *adj;
public :
Graph(int V)
{
adj = new vector<Edge>[V];
this->V = V;
level = new int[V];
}
void addEdge(int u, int v, int C)
{
Edge a = {v, 0, C, (int)adj[v].size()};
Edge b = {u, 0, 0, (int)adj[u].size()};
adj[u].push_back(a);
adj[v].push_back(b);
}
bool BFS(int s, int t);
int sendFlow(int s, int flow, int t, int ptr[]);
int DinicMaxflow(int s, int t);
};
bool Graph::BFS(int s, int t){
for (int i = 0 ; i < V ; i++)
level[i] = -1;
level[s] = 0;
list< int > q;
q.push_back(s);
vector<Edge>::iterator i ;
while (!q.empty())
{
int u = q.front();
q.pop_front();
for (i = adj[u].begin(); i != adj[u].end(); i++)
{
Edge &e = *i;
if (level[e.v] < 0 && e.flow < e.C)
{
level[e.v] = level[u] + 1;
q.push_back(e.v);
}
}
}
return level[t] < 0 ? false : true ;
}
int Graph::sendFlow(int u, int flow, int t, int start[]){
if (u == t)
return flow;
for ( ; start[u] < adj[u].size(); start[u]++)
{
Edge &e = adj[u][start[u]];
if (level[e.v] == level[u]+1 && e.flow < e.C)
{
int curr_flow = min(flow, e.C - e.flow);
int temp_flow = sendFlow(e.v, curr_flow, t, start);
if (temp_flow > 0)
{
e.flow += temp_flow;
adj[e.v][e.rev].flow -= temp_flow;
return temp_flow;
}
}
}
return 0;
}
int Graph::DinicMaxflow(int s, int t){
if (s == t)
return -1;
int total = 0;
while (BFS(s, t) == true)
{
int *start = new int[V+1];
while (int flow = sendFlow(s, INT_MAX, t, start))
total += flow;
}
return total;
}
int main()
{
int i,j,cakes,ingredients,price,ans=0;
scanf("%d %d",&cakes,&ingredients);
Graph g(cakes+ingredients+2);
for(i=1;i<=cakes;i++){
scanf("%d",&price);
ans += price;
g.addEdge(0,i,price);
}
for(i=1;i<=ingredients;i++){
scanf("%d",&price);
g.addEdge(cakes+i,ingredients+cakes+1,price);
}
for(i=1;i<=cakes;i++)
for(j=cakes+1;j<=cakes+ingredients;j++){
scanf("%d",&price);
if(!price) continue;
g.addEdge(i,j,INF);
}
cout<<ans-g.DinicMaxflow(0,cakes+ingredients+1)<<endl;
return 0;
}
0 Comments