问题描述:

给定n个闭合的整数区间$[ai,bi]$和n个整数$c1,…,cn$。你需要求出集合$Z$最小的元素数量,使集合$Z$对于每一个区间$[ai,bi]$中都有$c$个整数。

输入:

第一行$n (n<=50000)$,表示有n个区间
接下来n行,每行包含$ai, bi, ci$三个整数,其中$0 <= ai <= bi <= 50000$

输出:

输出集合$Z$可能的最小元素数量。

思路:

首先这题有一种贪心的做法,以前用过这种做法,所以我们重点在差分约束上。

这是一道比较基础的差分约束。同样建边是重点,对于每个区间,$bi$之前元素个数$-ai$之前元素个数要$>=ci$,所以我们在$ai,bi$间连一条长度为$ci$的单向边。同样,由于每个点上最多只能放零或一个元素,所以要从每个点$i$向前一个点$i-1$连一条长度为-1的边,从$i$向$i+1$连一条长度为0的边。

建完图以后,由于是求最小值,按照套路用SPFA跑一遍最长路。由于题目保证了有解,所以不需要加特判,输出dis[maxn]就好。

代码:

#include <cstdio>
#include <algorithm>
#include <queue>
#include <cstring>
#define MAXN 50005
using namespace std;

int n, cnt, maxn, head[MAXN*4], dis[MAXN];
bool vis[MAXN];

struct Edge {int to, next, dis;} edge[MAXN*4];

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

void spfa()
{
    queue<int> q;
    memset(dis, -0x3f, sizeof(dis));
    dis[0]=0; vis[0]=1;
    q.push(0);
    while(!q.empty())
    {
        int x=q.front(); q.pop(); vis[x]=0;
        for(int i=head[x]; i; i=edge[i].next)
        {
            int to=edge[i].to;
            if(dis[to]<dis[x]+edge[i].dis)
            {
                dis[to]=dis[x]+edge[i].dis;
                if(!vis[to]) vis[to]=1, q.push(to);
            }
        }
    }
}

int main()
{
    scanf("%d", &n);
    for(int i=1; i<=n; i++)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        addedge(a, b+1, c);
        maxn=max(maxn, b+1);
    }
    for(int i=0; i<maxn; i++) addedge(i, i+1, 0), addedge(i+1, i, -1);
    spfa();
    printf("%d\n", dis[maxn]);
}

发表评论

邮箱地址不会被公开。 必填项已用*标注