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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
| #include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
using ll = long long;
using pli = pair<ll, int>;
namespace MCMF
{
const int N = 5e5 + 5, M = 1e6 + 5, inf = 1e9;
const ll linf = 1e18;
int cnt, head[N];
struct edge
{
int next, to, w;
ll f;
}e[M<<1];
inline void addedge(int u, int v, int w, ll f)
{
e[++cnt] = {head[u], v, w, f};
head[u] = cnt;
}
int n, s, t;
int flow;
int p[N], a[N];
ll d[N], h[N], cost;
void init(int _n, int _s, int _t)
{
n = _n, s = _s, t = _t;
cnt = 1, flow = cost = 0;
memset(head, 0, (n+1)<<2);
}
void add(int u, int v, int cap, ll cost)
{
addedge(u, v, cap, cost), addedge(v, u, 0, -cost);
}
void getH()
{
for(int i=0; i<=n; i++) h[i] = linf;
h[s] = 0;
for(int i=s; i<t; i++)
for(int j=head[i]; j; j=e[j].next)
{
int v = e[j].to;
if(e[j].w && h[v]>h[i]+e[j].f) h[v] = h[i] + e[j].f;
}
}
bool Dijkstra()
{
for(int i=0; i<=n; i++) d[i] = linf;
d[s] = 0, a[s] = inf;
priority_queue<pli, vector<pli>, greater<pli>> pq;
pq.push({0, s});
while(!pq.empty())
{
auto cur = pq.top(); pq.pop();
int u = cur.se;
if(cur.fi>d[u]) continue;
for(int i=head[u]; i; i=e[i].next)
{
int v = e[i].to;
ll w = e[i].f + h[u] - h[v];
if(e[i].w&&d[v]>d[u]+w)
{
p[v] = i;
a[v] = min(a[u], e[i].w);
pq.push({d[v]=d[u]+w, v});
}
}
}
for(int i=0; i<=n; i++)
if(d[i]<linf) h[i] += d[i];
else h[i] = 0;
return d[t]!=linf;
}
void go()
{
getH();
while(Dijkstra())
{
flow += a[t], cost += a[t]*h[t];
int u = t;
while(u!=s)
{
e[p[u]].w -= a[t], e[p[u]^1].w += a[t];
u = e[p[u]^1].to;
}
}
}
}
int main()
{
int n; scanf("%d", &n);
MCMF::init(500002, 0, 500001);
for(int i=1; i<=n; i++)
{
int s, e; ll w; scanf("%d%d%lld", &s, &e, &w);
MCMF::add(s, e+1, 1, -w);
}
for(int i=0; i<MCMF::t; i++) MCMF::add(i, i+1, 2, 0);
MCMF::go();
printf("%lld\n", -MCMF::cost);
return 0;
}
|