POJ 1201 Intervals【差分约束】

题意：

有n个如下形式的条件： $a_i,b_i,c_i$ ,表示在区间[ $a_i$ , $b_i$ ]内至少要选择 $c_i$ 个整数点.问你满足以上所有条件，最少需要选多少个点?

思路：第一道差分约束题，有关差分约束知识详见https://blog.csdn.net/whereisherofrom/article/details/78922648（个人感觉这个博主写的挺好的）

令 $s_x$ 表示从区间[0,x]中选择的整数点个数，则有=c_i\rightarrow s_{b_i+1}-s_{a_i}>=c_i" class="mathcode" src="https://private.codecogs.com/gif.latex?s_%7Bb_i%7D-s_%7Ba_i-1%7D%3E%3Dc_i%5Crightarrow%20s_%7Bb_i+1%7D-s_%7Ba_i%7D%3E%3Dc_i">（因为=0" class="mathcode" src="https://private.codecogs.com/gif.latex?a_i%3E%3D0">，会出现数组下标为-1的情况），如果只靠这个式子是无法得出答案的，题中还有隐藏的约束 $0<=s_{i+1}-s_i<=1$ 即是=0" class="mathcode" src="https://private.codecogs.com/gif.latex?s_%7Bi+1%7D-s_i%3E%3D0">和=-1" class="mathcode" src="https://private.codecogs.com/gif.latex?s_i-s_%7Bi+1%7D%3E%3D-1">，题中要求最小值，所以用spfa跑一遍最长路即可。

代码：

#include<iostream>

#include<cstdio>

#include<queue>

using namespace std;

const int maxn = 50005;

const int INF = 0x3f3f3f3f;

int tot;

struct node

{

    int to;

    int next;

    int w;

};

node edges[maxn * 3];

int head[maxn];

int d[maxn];

bool vis[maxn];

void add_edges(int u, int v, int w)

{

    edges[++tot].to = v;

    edges[tot].w = w;

    edges[tot].next = head[u];

    head[u] = tot;

}

int l = 50005;

int r = -1;

void spfa()

{

    for(int i = l; i <= r; i++)

        vis[i] = false, d[i] = -INF;

    d[l] = 0;

    queue<int>q;

    q.push(l);

    while(!q.empty())

    {

        int x = q.front();

        q.pop();

        vis[x] = false;

        for(int i = head[x]; i; i = edges[i].next)

        {

            node v = edges[i];

            if(d[v.to] < d[x] + v.w)

            {

                d[v.to] = d[x] + v.w;

                if(!vis[v.to])

                {

                    vis[v.to] = true;

                    q.push(v.to);

                }

            }

        }

    }

}

int main()

{

    int n;

    scanf("%d", &n);

    for(int i = 1; i <= n; i++)

    {

        int a, b, c;

        scanf("%d%d%d", &a, &b, &c);

        add_edges(a, b + 1, c);

        r = max(r, b + 1);	  //求区间右端点

        l = min(l, a);        //求区间左端点

    }

    for(int i = l; i < r; i++)

    {

        add_edges(i + 1, i, -1);

        add_edges(i, i + 1, 0);

    }

    spfa();

    cout << d[r] << endl;

}

巴特西

POJ 1201 Intervals【差分约束】

最新文章

热门文章