Algoogle

Algorithm for Programming Contest

AOJ 1246 Concert Hall Scheduling

Category: AOJ Tag: min-cost-flow

Concert Hall Scheduling

問題概要


ホールを予約したい人の開始日と終了日と料金のリストが与えられる.
ホールが2つあるとき使わせる人をうまく選んだ時の料金の総和の最大を求めよ.

解法


0日->1日->…->365日と容量2, コスト0の辺を張り,
希望の開始日と終了日に容量1, コストを符号反転した料金の辺を張る.
あとは流量2の最小費用流を求めてその符号を反転したものを返せば良い.

コード


(1246.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <bits/stdc++.h>
using namespace std;
#define repi(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define rep(i,a) repi(i,0,a)
#define all(u) begin(u),end(u)
#define pb push_back
const int inf = 1e9;
struct edge { int to, cap, cost, rev;};
const int V = 366;
typedef pair<int,int> pii;
vector<edge> G[V];
int h[V], dist[V];
int prevv[V], preve[V];
int N;

void add_edge(int from, int to, int cap, int cost){
    G[from].push_back((edge){to, cap, -cost, int(G[to].size())});
    G[to].push_back((edge){from, 0, cost, int(G[from].size() - 1)});
}

int min_cost_flow(int s, int t, int f){
    int res = 0;
    fill(h, h + V, 0);
    while(f > 0){
        priority_queue<pii, vector<pii>, greater<pii> > que;
        fill(dist, dist + V, inf);
        dist[s] = 0;
        que.push(pii(0, s));
        while(!que.empty()){
            pii p = que.top(); que.pop();
            int v = p.second;
            if(dist[v] < p.first) continue;
            rep(i,G[v].size()){
                edge &e = G[v][i];
                if(e.cap > 0 && dist[e.to] > dist[v] + e.cost + h[v] - h[e.to]){
                    dist[e.to] = dist[v] + e.cost + h[v] - h[e.to];
                    prevv[e.to] = v;
                    preve[e.to] = i;
                    que.push(pii(dist[e.to], e.to));
                }
            }
        }
        if(dist[t] == inf) return -1;
        rep(v,V) h[v] += dist[v];
        int d = f;
        for(int v = t; v != s; v = prevv[v])
            d = min(d, G[prevv[v]][preve[v]].cap);
        f -= d;
        res += d * h[t];
        for(int v = t; v != s; v = prevv[v]){
            edge &e = G[prevv[v]][preve[v]];
            e.cap -= d;
            G[v][e.rev].cap += d;
        }
    }
    return res;
}

bool input(){
    cin >> N;
    if(!N) return 0;
    rep(i,V) G[i].clear();
    rep(i,V-1) add_edge(i,i+1,2,0);
    rep(i,N){
        int s, t, c;
        cin >> s >> t >> c;
        add_edge(s-1,t,1,c);
    }
    return 1;
}
signed main(){
    while(input()) cout << -min_cost_flow(0,365,2) << endl;
    return 0;
}

Comments