差分约束 poj 1201 （最大路径，区间约束）

关于差分约束，有个很好的博客

http://www.cppblog.com/menjitianya/archive/2015/11/19/212292.html

https://blog.csdn.net/consciousman/article/details/53812818

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

Sample Output

Source

Southwestern Europe 2002

给定n（n <= 50000）个整点闭区间和这个区间中至少有多少整点需要被选中，每个区间的范围为[ai, bi]，并且至少有ci个点需要被选中，其中0 <= ai <= bi <= 50000，问[0, 50000]至少需要有多少点被选中。例如3 6 2 表示[3, 6]这个区间至少需要选择2个点，可以是3,4也可以是4,6（总情况有 C(4, 2)种）。

首先根据题目给的关系，有d[ bi ] - d[ ai - 1 ] >= ci （因为实际上区间中有bi-ai-+1个点，ai也算)，d[i]表示[0,i]中最少有多少个满足的点，然后又有一个条件：就是i选不选，那么就有另一个关系0 <= d[i] - d[i-1] <= 1 ，在这套关系里，因为包含0，所以整个区间的源点是d[-1]=0,那么为了方便处理，可以把所有的数据都+1，然后根据不等关系建图，用spfa处理一遍，因为题目所需的是最少，即求最长路径。

//#include <bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;

#define maxn 100005
#define INF 9999999
typedef pair<int,int> pii;
vector<pii> e[maxn];
int vis[maxn],cnt[maxn],d[maxn],n,mmax,mmin;

void add_edge(int x,int y,int z)
{
    e[x].push_back(make_pair(y,z));
    //e[y].push_back(make_pair(x,z));
}

void init(int n)
{
    for(int i=0; i<=n; i++) e[i].clear();
    for(int i=0; i<=n; i++) d[i]=-INF;
}

void spfa(int s)
{
    queue<int>q;
    memset(vis,0,sizeof(vis));
    fill(d,d+mmax,-INF);                 //最长路径记得改一下d[i]的初始化
    q.push(s);
    d[s]=0;
    vis[s]=1;
    while(!q.empty())
    {
        int now=q.front();
        vis[now]=0;
        q.pop();
        for(int i=0; i<e[now].size(); i++)
        {
            int v=e[now][i].first;
            if(d[v]<d[now]+e[now][i].second)
            {
                d[v]=d[now]+e[now][i].second;
                if(!vis[v])
                {
                    q.push(v);
                    vis[v]=1;
                }
            }
        }
    }
}

int main()
{
    while(~scanf("%d",&n))
    {
       memset(e,0,sizeof(e));
        mmin=INF;
        mmax=-INF;
        for(int i=0; i<n; i++)
        {
            int x,y,z;
            scanf("%d %d %d",&x,&y,&z);
            mmax=max(y+1,mmax);               //找出区间最小点和最大点，作为起点和终点
            mmin=min(x,mmin);
            add_edge(x,y+1,z);
        for(int i=mmin; i<mmax; i++)
        {
            add_edge(i,i+1,0);
            add_edge(i+1,i,-1);
        }
        spfa(mmin);
        printf("%d
",d[mmax]);

    }
}

View Code