首页 > 其他分享 >poj 1201(差分约束)

poj 1201(差分约束)

时间:2023-05-29 22:36:01浏览次数:45  
标签:cnt int 1201 bi 差分 ai poj maxn include


Intervals


Time Limit: 2000MS

 

Memory Limit: 65536K

Total Submissions: 23934

 

Accepted: 9075


Description


You are given n closed, integer intervals [ai, bi] and n integers c1, ..., cn. 
Write a program that: 
reads the number of intervals, their end points and integers c1, ..., cn from the standard input, 
computes the minimal size of a set Z of integers which has at least ci common elements with interval [ai, bi], for each i=1,2,...,n, 
writes the answer to the standard output. 


Input


The first line of the input contains an integer n (1 <= n <= 50000) -- the number of intervals. The following n lines describe the intervals. The (i+1)-th line of the input contains three integers ai, bi and ci separated by single spaces and such that 0 <= ai <= bi <= 50000 and 1 <= ci <= bi - ai+1.


Output


The output contains exactly one integer equal to the minimal size of set Z sharing at least ci elements with interval [ai, bi], for each i=1,2,...,n.


Sample Input


5 3 7 3 8 10 3 6 8 1 1 3 1 10 11 1


Sample Output

6


思路:

首先第一个转化,是找到一个合理的表示。用ti表示每一个数,如果有用就是1,否则是0。吧S(i+1)定义成S(i+1)=sigma(tj)(1<=j<=i)也就是。S[i+1]表示从0到i有多少个数是需要的。

因此,题目中的条件可以表示成S[bi+1]>=S[ai]+Ci//至少要Ci个

这与bellman中的松弛操作时很像的。因此可以看成一些点

有D[v]>=D[u]+w(u,v)

上式对任何u成立,所以v应该是里面最大的,若D[v]<D[u]+w(u,v)则D[v]=D[u]+w(u,v)

于是。可以从ai和bi+1连一条线,它的长度是ci

这里只有这些条件还是不够的,还要加上两个使其满足整数性质的条件

1>=s[i+1]-s[i]>=0

有了这么多条件,使其自然构成了一个差分约束系统。

用spfa算法得到一个最长路,第一个到最后一个节点的最长路即是需要求的值。



AC:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;

const int maxn = 50005;
const int inf = 0x7f7f7f;
struct Edge
{
	int k,c,next;
}edge[maxn*10];
int n,pre[maxn],cnt,s,t,dis[maxn];
bool vis[maxn];

void addedge(int a,int b,int c)
{
	edge[cnt].k = b;
	edge[cnt].c = c;
	edge[cnt].next = pre[a];
	pre[a] = cnt++;
}

void SPFA()
{
	queue<int> que;
	memset(vis,false,sizeof(vis));
	for(int i = s; i <= t+1; i++)
		dis[i] = -inf;
	dis[s] = 0; vis[s] = true;
	que.push(s);
	while(!que.empty())
	{
		int u = que.front();
		que.pop();
		vis[u] = false;
		for(int i = pre[u]; i != -1; i = edge[i].next)
		{
			int k = edge[i].k;
			if(dis[k] < dis[u] + edge[i].c)
			{
				dis[k] = dis[u] + edge[i].c;
				if(vis[k] == false)
				{
					vis[k] = true;
					que.push(k);
				}
			}
		}
	}
	printf("%d\n",dis[t+1]);
}

int main()
{
	while(scanf("%d",&n)!=EOF)
	{
		s = inf,t = -inf;
		memset(pre,-1,sizeof(pre));
		cnt = 0;
		for(int i = 1; i <= n; i++)
		{
			int a,b,c;
			scanf("%d%d%d",&a,&b,&c);
			s = min(a,s); t = max(b,t);
			addedge(a,b+1,c);
		}
		for(int i = s; i <= t; i++)
		{
			addedge(i,i+1,0);
			addedge(i+1,i,-1);
		}
		SPFA();
	}
	return 0;
}





标签:cnt,int,1201,bi,差分,ai,poj,maxn,include
From: https://blog.51cto.com/u_16143128/6374316

相关文章

  • poj 1716(贪心)
    题意:给出数轴上的n个区间,每个区间都是连续的int区间。现在要在数轴上任意取一堆元素,构成一个元素集合V,要求每个区间和元素集合V的交集至少有两个不同的元素求集合V最小的元素个数。解题思路:考虑到区间之间的重叠性,所以每次都要尽可能地去每个区间靠后的值,才能保证前后两个区间公共......
  • poj 2362(剪枝)
    题意:给定一堆不定长度的小棒子,问他们能否构成一个正方形。解题思路:最开始写的时候把题意弄错了,以为只要能够从中取出一部分构成矩形即可。。。。这里注意一下几个剪枝的地方:1)要把所有的棒子都用上且组成正方形,那么sum%4=0;2)如果棒子长度小于4,肯定是不行的3)如果棒子中有长度大于s......
  • poj 1988(并查集)
    题意:进行m次操作,M x y 将包含x的集合移动到y上面,C x, 计算x下面有几个元素。解题思路:这道题很容易想到用并查集,但是这里有点绕;最开始我想到的是建立一个num[x],表示x以下的节点数,但这样会有一个问题,要更新num[x]时,必须要枚举哪些节点的父节点为p,由于节点数太多,所以TLE是难免的......
  • poj 1230(贪心)
    解题思路:这道题目是用贪心的思想,从左向右扫描场地的每一列是否合法。若不合法,贪心的找出从该列起向右延伸最长的m道墙,移除这m道墙使得该列合法。我最开始代码会出现这样的问题:如果两个墙是连在一起的,那么会被当做一个墙来处理。。。AC:#include<iostream>#include<cstdio>#inclu......
  • poj 1634
    题意:一个员工A的直接上司是那些薪水大于A,并且身高>=A的人中薪水最少的一个。主席CEO的薪水最高,且身高也是最高的。有多组数据。每组数据给出m个员工,和q个询问。每个员工有id、薪水、身高。对于每个询问,给出某个id,让你求该员工的直接上司的id和该员工的下属的个数。若该员工......
  • poj 1451(Trie)
    题意:就是让你模拟手机输入单词。具体就是给你一些单词,以及该单词被使用的频数,这个频数也是该单词前缀的使用频数,当然不同的单词有可能有相同的前缀,那么这个相同的前缀的使用频数就是这两个单词使用频数之和,以此类推。然后再给你一些数字串,让你针对该数字串的每一个前缀输出它的最有......
  • poj 1190(剪枝)
    生日蛋糕TimeLimit: 1000MS MemoryLimit: 10000KTotalSubmissions: 16191 Accepted: 5751Description7月17日是Mr.W的生日,ACM-THU为此要制作一个体积为Nπ的M层生日蛋糕,每层都是一个圆柱体。 设从下往上数第i(1<=i<=M)层蛋糕是半径为Ri,高度为Hi的圆......
  • hdu 1534(差分约束)
    题意:安排计划,有4种约束方式,给出你这些时间的n个约束..如果计划是可行的,求出每一件事发生的最早时间..否则输出“impossible”..①.FAFaba要在b完成后完成..②.FASaba要在b开始前完成..③.SASaba要在b开始前开始..④.SAFaba要在b结束前开......
  • poj 3281(最大流)
    解题思路:这是道匹配的问题,最近刚学网络流,所以想用网络流去做。。按照题目要求,我开始建立的是food----cow----drink的图,源点与所有的food的编号连接,所有的drink的编号与汇点连接,这里所有的有向边的容量都为1,。。但很不幸的是WA了。。看了别人的思路,我才知道原来这里保证不了一头牛......
  • poj 1935(搜索+回溯)
    解题思路:先我们考虑从源点出发到所有自己想要经过的点然后在回到源点sum,显然每条边都必须经过源点(这个我们可以一次dfs求出),但题目的意思是可以不用回到源点,那么我们可以再求源点到所有要经过的点的最远距离ans,于是答案便是sum-ans.这道题的思路确实是很巧妙,一开始我还是在想如......