2014
11-29

# Good 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 hours 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.

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.

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.

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 7273
22 139 7851
194 198 9190
119 274 878
122 173 8640

30
25500
38595

#include <string.h>
#include <stdio.h>
#include <iostream>
#include <algorithm>
using namespace std;
#define maxn 409
int S,T;
struct edge
{
int v,flow,cost;
edge *next,*opp;
#define NEW() &A[++ANS]
int ANS;
inline void addedge(int u,int v,int flow,int cost)
{
edge *ptr=NEW();
ptr->v=v;
ptr->flow=flow;
ptr->cost=cost;
ptr->opp=&A[ANS^1];
}
#define Inf 1000000000
int q[1000009],d[maxn];
bool vis[maxn];
edge *pre[maxn];
bool spfa()
{
memset(vis,0,sizeof(vis));
for(int i=S;i<=T;i++)
d[i]=Inf;
q[0]=S;
d[S]=0;
{
vis[u]=false;
{
v=ptr->v;
if(ptr->flow&&d[v]>d[u]+ptr->cost)
{
d[v]=d[u]+ptr->cost;
pre[v]=ptr;
if(!vis[v])
{
vis[v]=true;
q[tail++]=v;
}
}
}
}
return d[T]!=Inf;
}
int solve()
{
int mincost=0;
while(spfa())
{
edge *ptr;
int low=Inf;
for(int i=T;i!=S;)
{
ptr=pre[i];
low=min(low,ptr->flow);
i=ptr->opp->v;
}
for(int i=T;i!=S;)
{
ptr=pre[i];
ptr->flow-=low;
ptr->opp->flow+=low;
i=ptr->opp->v;
}
if(d[T]>=0)
break;
mincost+=low*d[T];
}
return mincost;
}
int main()
{
int Q;
scanf("%d",&Q);
while(Q--)
{
int s,t,v,n;
S=0;
scanf("%d",&n);

ANS=-1;
for(int i=0;i<406;i++)
{
}
for(int k=1;k<=n;k++)
{
scanf("%d%d%d",&s,&t,&v);
s++;
t++;
T=max(T,t+1);
}
for(int i=S;i<T;i++)
{
}