| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 115338 | model_code | Hotel (CEOI11_hot) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
/* Slow solution for task HOT
* Author: Miroslaw Michalski
* Time complexity : O(n^3)
* 03MAY11
* Min Cost Max Flow
*/
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cmath>
#include <iostream>
#include <sstream>
#include <string>
#include <utility>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <cassert>
using namespace std;
#define VAR(a,b) typeof(b) a=(b)
#define REP(i,n) for(int _n=n, i=0;i<_n;++i)
#define FOR(i,a,b) for(int i=(a),_b=(b);i<=_b;++i)
#define FORD(i,a,b) for(int i=(a),_b=(b);i>=_b;--i)
#define FOREACH(it,c) for(VAR(it,(c).begin());it!=(c).end();++it)
#define ALL(f,w) ({ bool _ok=true; f _ok=_ok && (w); _ok; })
#define EXISTS(f,w) (!ALL(f,!(w)))
typedef long long LL;
const int INF = 1100000000;
typedef vector<int> VI;
#define MP make_pair
#define PB push_back
#define ST first
#define ND second
#define SIZE(x) (int)x.size()
const int N=500100;
struct Edge{
int v,rev,c,koszt;
Edge(int vv,int rrev,int cc,int kkoszt) : v(vv), rev(rrev), c(cc), koszt(kkoszt) {}
Edge(){}
};
vector<Edge> kraw[N];
int parent[N],parent_kraw[N];
int used[N],dist[N],pot[N];
void AddEdge(int a,int b,int c,int koszt){
kraw[a].PB(Edge(b,SIZE(kraw[b])+(a==b),c,koszt));
kraw[b].PB(Edge(a,SIZE(kraw[a])-1,0,-koszt));
}
LL MinCostMaxFlow(int beg,int end,int n){
int res=0;
LL koszt=0, totalResult = 0;
REP(i,n) pot[i]=0; //poczatkowy potencjal, zakladam, ze poczatkowo
//wszystkie wagi sa nieujemne, jesli moba byc ujemne,
//to trzeba obliczyc poczatkowe potencjaly Bellmanem-Fordem
while (1){
REP(i,n) dist[i]=INF,used[i]=0;
dist[beg]=0;
//algorytm Dijkstry, mozna zmienic na wersje z kopcem dla grafu rzadkiego
REP(k,n){
int best=-1;
REP(i,n) if (!used[i] && (best==-1 || dist[i]<dist[best])) best=i;
used[best]=1;
if (dist[best]==INF) break;
FOREACH(it,kraw[best]) if (it->c>0){
int x=it->koszt-pot[it->v]+pot[best];
if (dist[it->v]>dist[best]+x){
dist[it->v]=dist[best]+x;
parent[it->v]=best;
parent_kraw[it->v]=it-kraw[best].begin();
}
}
}
if (dist[end]==INF) break; //brak sciezki powiekszajacej
REP(i,n) dist[i]+=pot[i],pot[i]=dist[i]; //uaktualnienie potencjalu
int cap=INF; //minimalna przepustowosc na sciezce
int x=end;
do{
cap=min(cap,kraw[parent[x]][parent_kraw[x]].c);
x=parent[x];
} while (x!=beg);
res+=cap;
x=end;
do{
koszt+=kraw[parent[x]][parent_kraw[x]].koszt*(LL)cap;
kraw[parent[x]][parent_kraw[x]].c-=cap;
kraw[x][kraw[parent[x]][parent_kraw[x]].rev].c+=cap;
x=parent[x];
} while (x!=beg);
totalResult = max(totalResult, static_cast<long long>(INF) * res - koszt);
}
return totalResult;
}
int main(){
int graphSize, n, m, o, ci, pi;
vector<pair<int, int> > room, need;
scanf("%d%d%d", &n, &m, &o);
graphSize = 3 + n + m + 1;
REP(i, graphSize) {
kraw[i].clear();
}
AddEdge(0, 1, o, 0);
REP(i, n) {
scanf("%d%d", &ci, &pi);
room.push_back(make_pair(ci, pi));
}
REP(i, m) {
scanf("%d%d", &ci, &pi);
need.push_back(make_pair(ci, pi));
}
REP(i, n) {
AddEdge(1, 2 + i, 1, 0);
}
REP(i, m) {
AddEdge(2 + n + i, graphSize - 1, 1, 0);
}
REP(i, n) {
REP(j, m) {
if (room[i].first < need[j].first && room[i].second >= need[j].second) {
AddEdge(2 + i, 2 + n + j, 1, INF - (need[j].first - room[i].first));
}
}
}
LL p = MinCostMaxFlow(0, graphSize - 1, graphSize);
printf("%lld\n", p);
return 0;
}