首页 > 其他 > 详细

【POJ 1716】Integer Intervals(差分约束系统)

时间:2018-03-14 12:33:50      阅读:127      评论:0      收藏:0      [点我收藏+]

标签:入门题   put   AD   edge   ota   全部   lib   最小   最短   

【POJ 1716】Integer Intervals(差分约束系统)


Integer Intervals
Time Limit: 1000MS ? Memory Limit: 10000K
Total Submissions: 13425 ? Accepted: 5703

Description

An integer interval [a,b], a < b, is a set of all consecutive integers beginning with a and ending with b.
Write a program that: finds the minimal number of elements in a set containing at least two different integers from each interval.

Input

The first line of the input contains the number of intervals n, 1 <= n <= 10000. Each of the following n lines contains two integers a, b separated by a single space, 0 <= a < b <= 10000. They are the beginning and the end of an interval.

Output

Output the minimal number of elements in a set containing at least two different integers from each interval.

Sample Input

4
3 6
2 4
0 2
4 7

Sample Output

4

Source

实训回来后的一血~~

差分约束系统,走前看了点,没搞透,做完这题略微有点明确了。

这题是差分约束系统入门题,关于差分约束系统。百度各种大牛博客讲的都非常具体。简单说就是通过不等关系建立约束系统图,然后跑最短路(大于关系则跑最长路)

回到此题,题目要求找出一个最小集合S,满足对于n个范围[ai,bi],S中存在两个及两个以上不同的点在范围内

令Zi表示满足条件的情况下。0~i点至少有多少点在集合内

则Zb-Za >= 2

仅仅有这一个条件构造出来的图可能不是全然连通的,所以须要找一些“隐含条件”

不难发现 对于相邻的点 0 <= Zi-Z(i-1) <= 1 保证关系符同样 转化为

Zi-Z(i-1) >= 0

Z(i-1)-Zi >= -1

用这三个关系,就可以构造差分约束系统,然后SPFA或者Bellman跑一趟最长路(满足全部条件)


代码例如以下:

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>

using namespace std;
const int INF = 0x3f3f3f3f;
const int msz = 1e5;
const int mod = 1e9+7;
const double eps = 1e-8;

struct Edge
{
	int v,w,next;
};

Edge eg[233333];
int head[50050];
bool vis[50050];
int dis[50050];
int tp,st,en;

void Add(int u,int v,int w)
{
	eg[tp].v = v;
	eg[tp].w = w;
	eg[tp].next = head[u];
	head[u] = tp++;
}

int SPFA()
{
	memset(vis,0,sizeof(vis));
	memset(dis,-INF,sizeof(dis));
	queue <int> q;
	dis[st] = 0;
	vis[st] = 1;
	int u,v,w;

	q.push(st);

	while(!q.empty())
	{
		u = q.front();
		q.pop();
		vis[u] = 0;
		for(int i = head[u]; i != -1; i = eg[i].next)
		{
			v = eg[i].v;
			w = eg[i].w;
			if(dis[v] < dis[u]+w)
			{
				dis[v] = dis[u]+w;
				if(!vis[v]) 
				{
					q.push(v);
					vis[v] = 1;
				}
			}
		}
	}
	return dis[en];
}

int main(int argc,char **argv)
{
	int n;
	int u,v;

	while(~scanf("%d",&n))
	{
		tp = 0;
		memset(head,-1,sizeof(head));
		
		en = 0,st = INF;

		while(n--)
		{
			scanf("%d%d",&u,&v);
			Add(u,v+1,2);
			//最小点做起点 最大点做终点
			en = max(en,v+1);
			st = min(st,u);
		}

		for(int i = st; i < en; ++i)
		{
			Add(i,i+1,0);
			Add(i+1,i,-1);
		}
		printf("%d\n",SPFA());
	}
	return 0;
}


【POJ 1716】Integer Intervals(差分约束系统)

标签:入门题   put   AD   edge   ota   全部   lib   最小   最短   

原文:https://www.cnblogs.com/llguanli/p/8566286.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号