题目大意：原题链接
构造一个集合，这个集合内的数字满足所给的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=0; bool vis[maxn]; int d[maxn],head[maxn]; struct Edge { int to,wt; int next; }e[3*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?0:-inf; que.push(u); while(!que.empty()){ u=que.front(); que.pop(); for(int i=head[u];i!=-1;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,0,sizeof(d)); memset(e,0,sizeof(e)); memset(vis,0,sizeof(vis)); memset(head,-1,sizeof(head)); for(int i=1;i<=m;i++){ scanf("%d%d%d",&u,&v,&w); Add(u,v+1,w); s=min(u,s),t=max(t,v+1); } for(int i=s;i<t;i++){ Add(i,i+1,0); Add(i+1,i,-1); } Dijkstra(s); printf("%d ",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=0; bool vis[maxn]; int d[maxn],head[maxn]; struct Edge { int to,wt; int next; }e[3*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?0:-inf; que.push(u); while(!que.empty()){ u=que.front(); que.pop(); vis[u]=0; for(int i=head[u];i!=-1;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]=1; que.push(v); } } } } int main() { while(scanf("%d",&m)!=EOF){ s=inf,t=-inf; memset(d,0,sizeof(d)); memset(e,0,sizeof(e)); memset(vis,0,sizeof(vis)); memset(head,-1,sizeof(head)); for(int i=1;i<=m;i++){ scanf("%d%d%d",&u,&v,&w); Add(u,v+1,w); s=min(u,s),t=max(t,v+1); } for(int i=s;i<t;i++){ Add(i,i+1,0); Add(i+1,i,-1); } Spfa(s); printf("%d ",d[t]); } }