链接
http://poj.org/problem?id=1201
题意
从
0
∼
50000
0\sim 50000
0∼50000 中选出尽可能少的整数，使每个区间
[
a
i
,
b
i
]
[a_i,b_i]
[ai,bi] 内都有至少
c
i
c_i
ci 个数被选出
思路
设
s
[
k
]
s[k]
s[k] 为
0
∼
k
0\sim k
0∼k 中选出了
s
[
k
]
s[k]
s[k] 个数
由题意得：
s
b
i
−
s
a
i
−
1
≥
c
i
s_{b_i}-s_{a_i-1}\ge c_i
sbi−sai−1≥ci
又因为：
s
k
−
s
k
−
1
≥
0
s_k-s_{k-1}\ge 0
sk−sk−1≥0
s
k
−
1
−
s
k
≥
−
1
s_{k-1}-s_k\ge -1
sk−1−sk≥−1
在
k
−
1
k-1
k−1 与
k
k
k 之间建立权值为
0
0
0 的有向边，
k
k
k 与
k
−
1
k-1
k−1 之间建立权值为
1
1
1 的有向边，
a
i
−
1
a_{i-1}
ai−1 与
b
i
b_{i}
bi 之间建立权值为
c
i
c_i
ci 的有向边
以
−
1
-1
−1 为起点跑最长路，因为
c
i
≤
b
i
−
a
i
+
1
c_i\le b_i-a_i+1
ci≤bi−ai+1 ，所以图中不存在正环，一定有解
代码
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <climits>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <bitset>
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
using namespace std
;
typedef double DB
;
typedef long long LL
;
typedef unsigned long long ULL
;
typedef pair
<int,int> PII
;
typedef vector
<int> VI
;
typedef vector
<PII
> VPII
;
const int N
=5e4+5;
int n
,mx
,dist
[N
];
bool st
[N
];
VPII G
[N
];
void spfa() {
for(int i
=0;i
<=mx
;i
++) dist
[i
]=0xc0c0c0c0;
queue
<int> q
;
q
.push(0);
dist
[0]=0;
st
[0]=true;
while(q
.size()) {
int u
=q
.front();
q
.pop();
st
[u
]=false;
for(int i
=0;i
<SZ(G
[u
]);i
++) {
int v
=G
[u
][i
].FI
,w
=G
[u
][i
].SE
;
if(dist
[v
]<dist
[u
]+w
) {
dist
[v
]=dist
[u
]+w
;
if(!st
[v
]) {
st
[v
]=true;
q
.push(v
);
}
}
}
}
printf("%d\n",dist
[mx
]);
}
int main() {
scanf("%d",&n
);
for(int i
=1;i
<=n
;i
++) {
int u
,v
,w
;
scanf("%d%d%d",&u
,&v
,&w
);
v
++;
mx
=max(mx
,v
);
G
[u
].PB(MP(v
,w
));
}
for(int i
=0;i
<mx
;i
++) G
[i
].PB(MP(i
+1,0));
for(int i
=1;i
<=mx
;i
++) G
[i
].PB(MP(i
-1,-1));
spfa();
return 0;
}
