2726 Plan
FJ has two same house for rant. Now he has n (1 ≤ n ≤ 1000) piece of order, the orders are
given in the form:
s t v
means that someone want to rant a house from the day s to t paying v yuan totally (including
the day s and t, 0 ≤ s ≤ t ≤ 400, 0 ≤ v ≤ 100,0000).
A hours can be only rant to one person, and FJ should either accept an order totally or reject it.
Input
The first line of input file is a single integer T - The number of test cases. For each test case,
the first line is a single integer n then there n lines, each line gives an order
Output
For each data set, print a single line containing an integer, the maximum total income for the
data set
Sample Input
3
4
1 2 10
2 3 10
3 3 10
1 3 10
6
1 20 1000
3 25 10000
5 15 5000
22 300 5500
10 295 9000
7 7 6000
8
32 251 2261
123 281 1339
211 235 5641
162 217 72736
22 139 7851
194 198 9190
119 274 878
122 173 8640
Sample Output
30
25500
38595
唐牛春季網絡流專場的一道題，今天做了一下。
發現最小費用流就能搞定，定義完數組發現如果以order為點肯定超時了，所以re看了一下題，發現t的范圍很小，都是整數，所以果斷改圖，把每秒作為點就OK了。
建圖方法：相鄰兩個點（t，t + 1）連線，流量是2，費用是0，對于每一個order，s + 1和t + 2連線（t + 2多加1是因為防止有起始點與它相同，出現流錯誤）流量為1，費用為-c，在這個圖上做一邊最小費用流就行了。
SPFA很犀利，不過極限數據還是跑不進0.00s.....
代碼：
#include <cstdio>
#include <cstring>
#define min(a, b) (a > b ? b : a)
using namespace std;
const int maxn = 405;
const int maxm = 3300;
const int inf = 1 << 30;
int n;
struct Edge
{
int v, next, c, w;
} edge[maxm];
int head[maxn], cnt;
void add_edge(int u, int v, int w, int c)
{
edge[cnt].v = v;
edge[cnt].w = w;
edge[cnt].c = c;
edge[cnt].next = head[u];
head[u] = cnt++;
edge[cnt].v = u;
edge[cnt].w = 0;
edge[cnt].c = -c;
edge[cnt].next = head[v];
head[v] = cnt++;
}
int dis[maxn], pre[maxn];
int alpha[maxn];
int que[maxn], qhead, qrear;
int spfa(int s, int e)
{
for (int i = 0; i < maxn; ++i)
dis[i] = inf;
memset(alpha, 0, sizeof(alpha));
dis[s] = 0;
que[qhead = 0] = s;
qrear = 1;
alpha[s] = 1;
while (qhead != qrear)
{
int k = que[qhead++];
qhead %= maxn;
alpha[k] = 0;
for (int q = head[k]; ~q; q = edge[q].next)
if (edge[q].w)
if (dis[k] + edge[q].c < dis[edge[q].v])
{
dis[edge[q].v] = dis[k] + edge[q].c;
pre[edge[q].v] = q;
if (!alpha[edge[q].v])
{
alpha[edge[q].v] = true;
if (edge[q].c < 0)
{
qhead = (qhead - 1 + maxn) % maxn;
que[qhead] = edge[q].v;
}
else
{
que[qrear++] = edge[q].v;
qrear %= maxn;
}
}
}
}
if (dis[e] == inf) return -1;
int k = inf;
for (int i = e; i != s; i = edge[pre[i] ^ 1].v)
k = min(k, edge[pre[i]].w);
return k;
}
int mcmf(int s, int t)
{
int ans = 0, k;
while (~(k = spfa(s, t)))
{
for (int i = t; i != s; i = edge[pre[i] ^ 1].v)
{
edge[pre[i]].w -= k;
edge[pre[i] ^ 1].w += k;
}
ans += dis[t] * k;
}
return ans;
}
void init()
{
cnt = 0;
memset(head, -1, sizeof(head));
}
int main()
{
int T;
scanf("%d", &T);
while (T--)
{
init();
scanf("%d", &n);
for (int i = 0; i < n; ++i)
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add_edge(a + 1, b + 2, 1, -c);
}
for (int i = 0; i <= 401; ++i)
add_edge(i, i + 1, 2, 0);
int ans = mcmf(0, 402);
printf("%d\n", -ans);
}
}