欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Poj 1716& Poj 1201 (Integer) Intervals【贪心|差分约束详解】

程序员文章站 2024-03-23 15:46:10
...

Poj 1716& Poj 1201 (Integer) Intervals【贪心|差分约束详解】
题目链接

一、贪心算法

原文链接:https://blog.csdn.net/linyuxilu/article/details/51954030

先对所有区间按末端点排序

取第i个区间的最后两个元素x和y

若第i+1个区间包含了这两个元素,则跳到下一个区间所取的元素个数+0

若第i+1个区间只包含了这两个元素中的一个(由于有序,所以必定是包含y),则取第i+1个区间的最后一个元素,所取的元素个数+1。为了方便下一区间的比较,更新x和y的值,使他们为当前V集合中最后的两个元素。

若第i+1个区间没有包含这两个元素,则第i+1个区间的最后两个元素,所取的元素个数+2。为了方便下一区间的比较,更新x和y的值,使他们为当前V集合中最后的两个元素。

元素初值初始化为2

x初始化为第一个区间的最后倒数第2个元素

y初始化为第一个区间的最后的元素

#include<stdio.h>
#include<algorithm>
using namespace std;
struct F
{
    int a,b;
} s[10010];
int cmp(F x,F y)
{
    return x.b<y.b;
}
int main()
{
    int n,i,j,x,y;
    scanf("%d",&n);
    for(i=0; i<n; i++)
        scanf("%d%d",&s[i].a,&s[i].b);
    sort(s,s+n,cmp);
    j=2;
    x=s[0].b-1;
    y=s[0].b;
    for(i=1; i<n; i++)
    {
        if(s[i].a<=x&&s[i].b>=y)//如果此区间包含了这两个元素,不用再取
            continue;
        if(s[i].a<=y&&s[i].a>x)//如果只包含一个,肯定是y
        {
            x=y;
            y=s[i].b;//更新x和y
            j+=1;//增加一个元素
        }
        if(s[i].a>y)//如果不包含任意一个元素,就需要增加后两位元素
        {
            x=s[i].b-1;//更新元素的值
            y=s[i].b;//因为数据是从小到大排的额,所以保存后两位
            j+=2;//元素数量加2
        }
    }
    printf("%d\n",j);
    return 0;
}

2、差分约束

原文链接:https://blog.csdn.net/a15110103117/article/details/52513644

对这一道题,每个区间只需要保证2个不同元素即可,我们自然可以从左到右对每个区间贪心的选择最后两个,然后和下一个区间进行比较,可是如果每个区间需要有n个不同元素呢?此时贪心将很难实施,参考poj 1201,更多的使用的是差分约束系统。

我们设a[0]到a[10000],表示从0到i一共有几个整数,比如a[0]为1个(其中有0),a[5]为6个(其中有0,1,2,3,4,5)。

那么利用它们之间的关系可以有这么几个不等式:

1.a[y]-a[x-1]>=2.(y>x,表示[x,y]闭区间的个数)

2.a[i]-a[i+1]>=-1.

3.a[i+1]-a[i]>=0.

差分约束系统中一个比较重要的问题是,如何建图,如果我们希望求最短路径的话,他的松弛条件是

if(d[u]>d[v]+w[v,u])
	d[u]=d[v]+w[v,u]

也就是说在最短路径中,我们执行完松弛之后,对每个点有以下条件成立,如果u,vu,v恰好是最短路径上相邻的两点,那么等号成立。
d[u]d[v]+w[v,u]d[v]d[u]w[v,u]d[u]\leq d[v]+w[v,u]\\ d[v]\geq d[u]-w[v,u]

观察我们上面的不等式,如果将常数项看作两点之间的权重,那么对
a[y]a[x1]2a[y]-a[x-1]\geq 2,从yyx1x-1连接一条权重为2-2的边,以此类推就得到了我们的图,然后求最左的端点到最右端点+1的最短路径即可。相反如果是用最长路做,那么松弛之后就满足
d[u]d[v]+w[v,u]d[v]d[u]w[v,u]d[u]\geq d[v]+w[v,u]\\ d[v]\leq d[u]-w[v,u]

那么对于a[y]a[x1]2a[y]-a[x-1]\geq 2我们将从x1x-1连接一条权重为2的边到yy。这是我个人对建图的理解。

值得注意的一点是:建立的图可能不联通,我们只需要加入一个超级源点,比如说求取最长路时图不联通的话,我们只需要加入一个点S,对其他的每个点建立一条权值为0的边图就联通了,然后从S点开始进行spfa判环。最短路类似,不过原点到其他点的权值为inf。

如果要判断差分约束系统是否存在解,一般都是判断环,选择求最短路或者最长路求解都行,只是不等式标准化时候不同,判环地话,用spfa即可,n个点中如果同一个点入队超过n次,那么即存在环。

/**
*   差分约束:
*       刚接触差分约束的确很纠结。。
*   差分约束系统的题其实是研究题目的约束条件,再根据最短路在松弛边的时候的固有性质来理解的。
*   就如这题,由题目意思有如下约束条件:
*       dis[u]表示u-1之前所取的关键点的数, 对于边(i, i+1)有
*       1、dis[i+1] - dis[i] >= 0
*       2、dis[i+1] - dis[i] <= 2;
*       对于边(u, v)
*       3、dis[v+1] - dis[u] >= 2   // 在[u, v]区间内必须取2个点以上
*
*       清楚了这些约束条件就可以依此建图了。
*       一开始看了好多人的题解。有求最长路的,有求最短路的,有mn为源点的,有mx为源点的
*   其实,求最长也好最短也好。不过是要理解实质,根据构图的不同,和起始点的不同,最短路最长路都可以的。
*       关键是,怎么把约束条件映射的图上,也就是如何建立这个图,如何加边!
*   首先,可以确定,如果是用最长路做:
*       那么在松弛边(u, v)的时候是根据 先判断 d[v] < d[u] + w ,如果成立 d[u] = d[v] + w;  // w 为边权。
*   这样在松弛完毕后就有  d[v] > d[u] + w 再看看约束条件: dis[i+1] - dis[i] >= 0
*   所以可以这样加边:  add_edge(i, i+1, w);  // 函数原型 add_edge(int u, int v, int w)
*       再看看约束条件: dis[v+1] - dis[u] >= 2 要使得松弛后 d[v] > d[u] + w 那么添边方法:add_edge(u, v+1, 2);
*/
 
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <string>
#include <queue>
#include <map>
#include <vector>
#include <algorithm>
#define DEBUG 0
#define INF 0x1fffffff
#define MAXS 10005
 
typedef long long LL;
using namespace std;
int n, inq[MAXS], dis[MAXS];
struct Edge
{
    int v, w;
    Edge(){}
    Edge(int vv, int ww) {v = vv; w = ww;}
};
vector<Edge> ver[MAXS];
 
void dijkstra(int mx, int mn)
{
    for(int i = mn; i <= mx; i ++) {
        inq[i] = 0;
        dis[i] = -INF;
    }
    queue<int> q;
    inq[mn] = 1;
    q.push(mn);
    dis[mn] = 0;
 
    while(!q.empty())
    {
        int cur = q.front(); q.pop();
        inq[cur] = 0;
        for(int i = 0; i < ver[cur].size(); i ++)
        {
            int v = ver[cur][i].v, w = ver[cur][i].w;
            if(dis[v] < dis[cur] + w) {
                dis[v] = dis[cur] + w;
                if(!inq[v]) {
                    inq[v] = 1;
                    q.push(v);
                }
            }
        }
    }
}
 
 
int main()
{
    while(~scanf("%d", &n))
    {
        int u, v, mx = 0, mn = INF;
        for(int i = 0; i <= MAXS; i ++)
            ver[i].clear();
        for(int i = 0; i < n ; i ++) {
            scanf("%d%d", &u, &v);
            if(v + 1 > mx) mx = v + 1;
            if(u < mn) mn = u;
            /** 约束条件 d[v+1] - d[u] >= 2 */
            ver[u].push_back(Edge(v+1, 2));
        }
 
        /** 添加其他约束条件。 */
        for(int i = 0; i <= mx; i ++) {
            ver[i].push_back(Edge(i+1, 0));
            ver[i+1].push_back(Edge(i, -1));
        }
        dijkstra(mx, mn);
        printf("%d\n", dis[mx]);
    }
    return 0;
}
相关标签: ACM图论/网络流