In this HackerEarth Holi and Cultural Festival problem solution A cultural festival is going to be organized in Hacker Society on the day of Holi .The head of the society needs some Poets ,Dancers and some Musicians to perform in this event. He decides to interview N number of people who live in the society. Each one has ratings in all the three fields. He wants to choose right guys for the right job so that the festival can be celebrated in the best possible way.Thus he selects P Poets,D Dancers and M Musicians. Help him in organizing the event.
The strength of Cultural Festival is the sum of ratings of the people in the corresponding field. You have to maximize the sum of their ratings.
HackerEarth Holi and Cultural Festival problem solution.
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
struct edge
{
ll to,rev,cost,fl,cap;
};
vector<edge>v[3010];
ll n,prog[3010],webd[3010],dist[3010],curflow[3010],fans,cans,w,p,m,market[3010];
bool mark[3010];
pair<ll,ll>par[3010];
void add_edge(ll fr,ll to,ll cap,ll cost)
{
v[fr].push_back({to,(int)v[to].size(),cost,0,cap});
v[to].push_back({fr,(int)v[fr].size()-1,-cost,0,0});
}
ll spfa(ll src,ll dest)
{
ll i,j,k;
queue<ll>q;
for(i=1;i<=3007;i++)
{
mark[i]=curflow[i]=0;
dist[i]=1e10;
}
curflow[src]=1e10;
dist[src]=0;
mark[src]=1;
q.push(src);
while(!q.empty())
{
j=q.front();
q.pop();
mark[j]=0;
for(i=0;i<v[j].size();i++)
{
ll to=v[j][i].to;
ll idx=v[j][i].rev;
ll cst=v[j][i].cost;
ll cap=v[j][i].cap;
if(cap<=0||dist[to]<=cst+dist[j])
continue;
curflow[to]=min(curflow[j],cap);
dist[to]=cst+dist[j];
par[to]={j,i};
if(!mark[to])
{
q.push(to);
mark[to]=1;
}
}
}
return curflow[dest];
}
ll augment(ll src,ll dest,ll flow)
{
for(ll i=dest;i!=src;i=par[i].first)
{
edge &temp=v[par[i].first][par[i].second];
edge &rev=v[i][temp.rev];
temp.cap-=flow;
temp.fl+=flow;
rev.cap+=flow;
rev.fl-=flow;
}
return 1LL*dist[dest]*flow;
}
void min_cost_max_flow(ll src,ll dest)
{
ll temp;
while(temp=spfa(src,dest))
{
cans+=augment(src,dest,temp);
fans+=temp;
}
}
int main()
{
freopen("in00.txt","r",stdin);
freopen("out00.txt","w",stdout);
ll i,j,k,src,sink,wb,pg,mr;
cin>>n>>w>>p>>m;
src=n+1;
sink=n+2;
wb=n+3;
pg=n+4;
mr=n+5;
for(i=1;i<=n;i++)
{
cin>>webd[i];
add_edge(i,wb,1,-webd[i]);
}
for(i=1;i<=n;i++)
{
cin>>prog[i];
add_edge(i,pg,1,-prog[i]);
}
for(i=1;i<=n;i++)
{
cin>>market[i];
add_edge(i,mr,1,-market[i]);
}
for(i=1;i<=n;i++)
{
add_edge(src,i,1,0);
}
add_edge(wb,sink,w,0);
add_edge(pg,sink,p,0);
add_edge(mr,sink,m,0);
min_cost_max_flow(src,sink);
cout<<abs(cans)<<"\n";
return 0;
}Second solution
#include <bits/stdc++.h>
using namespace std;
#define fst first
#define snd second
#define all(c) ((c).begin()), ((c).end())
#define TEST(s) if (!(s)) { cout << __LINE__ << " " << #s << endl; exit(-1); }
const long long INF = 99999999;
// min cost max flow code source -> spaghetti source
struct graph {
typedef int flow_type;
typedef int cost_type;
struct edge {
int src, dst;
flow_type capacity, flow;
cost_type cost;
size_t rev;
};
vector<edge> edges;
void add_edge(int src, int dst, flow_type cap, cost_type cost) {
adj[src].push_back({src, dst, cap, 0, cost, adj[dst].size()});
adj[dst].push_back({dst, src, 0, 0, -cost, adj[src].size()-1});
}
int n;
vector<vector<edge>> adj;
graph(int n) : n(n), adj(n) { }
pair<flow_type, cost_type> min_cost_max_flow(int s, int t) {
flow_type flow = 0;
cost_type cost = 0;
for (int u = 0; u < n; ++u) // initialize
for (auto &e: adj[u]) e.flow = 0;
vector<cost_type> p(n, 0);
auto rcost = [&](edge e) { return e.cost + p[e.src] - p[e.dst]; };
for (int iter = 0; ; ++iter) {
vector<int> prev(n, -1); prev[s] = 0;
vector<cost_type> dist(n, INF); dist[s] = 0;
if (iter == 0) { // use Bellman-Ford to remove negative cost edges
vector<int> count(n); count[s] = 1;
queue<int> que;
for (que.push(s); !que.empty(); ) {
int u = que.front(); que.pop();
count[u] = -count[u];
for (auto &e: adj[u]) {
if (e.capacity > e.flow && dist[e.dst] > dist[e.src] + rcost(e)) {
dist[e.dst] = dist[e.src] + rcost(e);
prev[e.dst] = e.rev;
if (count[e.dst] <= 0) {
count[e.dst] = -count[e.dst] + 1;
que.push(e.dst);
}
}
}
}
} else { // use Dijkstra
typedef pair<cost_type, int> node;
priority_queue<node, vector<node>, greater<node>> que;
que.push({0, s});
while (!que.empty()) {
node a = que.top(); que.pop();
if (a.snd == t) break;
if (dist[a.snd] > a.fst) continue;
for (auto e: adj[a.snd]) {
if (e.capacity > e.flow && dist[e.dst] > a.fst + rcost(e)) {
dist[e.dst] = dist[e.src] + rcost(e);
prev[e.dst] = e.rev;
que.push({dist[e.dst], e.dst});
}
}
}
}
if (prev[t] == -1) break;
for (int u = 0; u < n; ++u)
if (dist[u] < dist[t]) p[u] += dist[u] - dist[t];
function<flow_type(int,flow_type)> augment = [&](int u, flow_type cur) {
if (u == s) return cur;
edge &r = adj[u][prev[u]], &e = adj[r.dst][r.rev];
flow_type f = augment(e.src, min(e.capacity - e.flow, cur));
e.flow += f; r.flow -= f;
return f;
};
flow_type f = augment(t, INF);
flow += f;
cost += f * (p[t] - p[s]);
}
return {flow, cost};
}
};
const int N = 2005;
int a[N], b[N], c[N], d[N];
int main(){
int n, p, m, d;
cin >> n >> p >> d >> m;
int ans = N * (p + m + d);
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= n; i++) cin >> b[i];
for(int i = 1; i <= n; i++) cin >> c[i];
graph g(n + 10);
int src = 0, dst = n + 9;
g.add_edge(src, 1, p, 0);
g.add_edge(src, 2, d, 0);
g.add_edge(src, 3, m, 0);
for(int i = 1; i <= n; i++){
g.add_edge(1, i + 3, 1, N - a[i]);
g.add_edge(i + 3, dst, 1, 0);
}
for(int i = 1; i <= n; i++){
g.add_edge(2, i + 3, 1, N - b[i]);
}
for(int i = 1; i <= n; i++){
g.add_edge(3, i + 3, 1, N - c[i]);
}
pair<int, int> P = g.min_cost_max_flow(src, dst);
assert(P.fst == p + m + d);
printf("%d\n", ans - P.snd);
}
0 Comments