题目大意：原题链接
构造一个集合，这个集合内的数字满足所给的n个条件，每个条件都是指在区间[a,b]内至少有c个数在集合内。问集合最少包含多少个点。即求至少有多少个元素在区间[a,b]内。
解题思路：
首先假设s[i]表示从0到i中有s[i]个数属于这个序列。
1. 开始我用每个整数(1,2,...)当做图的结点,添加边就是Add(u,v,w),写出来之后发现连题目的样例数据都输出错误,输出结果为8.
2. 后来发现这样是错误的,比如有两个约束条件分别为:1 3 2, 3 6 2;那么按照上面的思路添加这两条边<1,3>=2,<3,6>=2;后又可以得到边<1,6>=4,意思是在线段[1,6]上至少要选4个点,而实际上不是的,应该是至少要选3个点就够了。问题出哪呢？？因为线段[1,3]和[3,6]有一个公共点3.
3. 所以要换一种方式建图,对于一个条件(u,v,w)实际上表示在开区间(u-0.5,v+0.5)上至少选w整数点,但是又不能把3.5,4.5,5.5...这样的小数当做图的结点啊！再换一种,用左闭右开区间[u,v+1),因为取的是整数点,所以意义和闭区间[u,v]一样,这样,对于每个限制条件(u,v,w)就可以添加边<u,v+1>=w;即Add(u,v+1,w).
4.但是这题和上一题PKU3169又有点不同,上一题奶牛节点编号是连续的,而这一题节点编号是不连续的,所以要学会挖掘题目中的隐含条件。首先,对于每个描述,都可以得到一个方程s[v]-s[u]>=w,同时由于每个数至多取一次,那么有0<=s[i]-s[i-1]<=1,写成统一的形式(即不等式的朝向相同)即为:s[v]-s[u]>=w; s[i]-s[i-1]>=0; s[i-1]-s[i]>=-1.这样节点编号就连续了,接下来采用和PKU3169同样的方法建图即可。
注意：此题跑的是最长路 ; queue<int> que;语句可以定义为全局变量或者定义在Dijkstra(int u)内部。说来也奇怪,之前做Vjudge上的一道题时,该语句非得定义在函数Dijkstra(int u)内部,否则一直WA,当时也是气的不行。
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
#define maxn 50010
#define inf 0x3f3f3f3f
using namespace std;
int m,u,v,w,s,t,tot=;
bool vis[maxn];
int d[maxn],head[maxn];
struct Edge
{
int to,wt;
int next;
}e[*maxn]; void Add(int u,int v,int w)
{
e[tot].to=v;
e[tot].wt=w;
e[tot].next=head[u];
head[u]=tot++;
}
queue<int> que;
void Dijkstra(int u)
{
for(int i=s;i<=t;i++)
d[i]=i==u?:-inf;
que.push(u);
while(!que.empty()){
u=que.front();
que.pop();
for(int i=head[u];i!=-;i=e[i].next){
int v=e[i].to;
int w=e[i].wt;
if(d[v]<d[u]+w){//d[u]!=-inf可有可无
d[v]=d[u]+w;
que.push(v);
}
}
}
} int main()
{
while(scanf("%d",&m)!=EOF){
s=inf,t=-inf;
memset(d,,sizeof(d));
memset(e,,sizeof(e));
memset(vis,,sizeof(vis));
memset(head,-,sizeof(head));
for(int i=;i<=m;i++){
scanf("%d%d%d",&u,&v,&w);
Add(u,v+,w);
s=min(u,s),t=max(t,v+);
}
for(int i=s;i<t;i++){
Add(i,i+,);
Add(i+,i,-);
}
Dijkstra(s);
printf("%d\n",d[t]);
}
}
加上vis[maxn]数组标记后好像也并没有加快,不知道是测试数据不够大还是根本就不能节省时间。注意Dijkstra(int u)函数中vis[maxn]的位置非常重要;
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
#define maxn 50010
#define inf 0x3f3f3f3f
using namespace std;
int m,u,v,w,s,t,tot=;
bool vis[maxn];
int d[maxn],head[maxn];
struct Edge
{
int to,wt;
int next;
}e[*maxn]; void Add(int u,int v,int w)
{
e[tot].to=v;
e[tot].wt=w;
e[tot].next=head[u];
head[u]=tot++;
}
queue<int> que;
void Spfa(int u)
{
for(int i=s;i<=t;i++)
d[i]=i==u?:-inf;
que.push(u);
while(!que.empty()){
u=que.front();
que.pop();
vis[u]=;
for(int i=head[u];i!=-;i=e[i].next){
int v=e[i].to;
int w=e[i].wt;
if(d[v]<d[u]+w){//d[u]!=-inf可有可无
d[v]=d[u]+w;
if(vis[v]) continue;
vis[v]=;
que.push(v);
}
}
}
} int main()
{
while(scanf("%d",&m)!=EOF){
s=inf,t=-inf;
memset(d,,sizeof(d));
memset(e,,sizeof(e));
memset(vis,,sizeof(vis));
memset(head,-,sizeof(head));
for(int i=;i<=m;i++){
scanf("%d%d%d",&u,&v,&w);
Add(u,v+,w);
s=min(u,s),t=max(t,v+);
}
for(int i=s;i<t;i++){
Add(i,i+,);
Add(i+,i,-);
}
Spfa(s);
printf("%d\n",d[t]);
}
}