【poj1201】 Intervals

http://poj.org/problem?id=1201 (题目链接)

题意

　　给出n个区间${[ai,bi]}$，要求选出尽可能少的数，使得每个区间i中至少存在${c[i]}$个数。

Solution

　　差分约束。

　　区间可以表示为${sum[b_i]-sum[a_i-1]}$，所以可以列出n个不等式：${sum[b_i]-sum[a_i-1]>=c[i]}$，然后每个${sum[x]}$满足$${0<=sum[x+1]-sum[x]<=1}$$$${sum[x+1]-sum[x]>=0，sum[x]-sum[x+1]>=-1}$$

　　这样的话构图就确定了连通性。建完图后，跑SPFA最长路即可。

代码

// poj1201

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<cmath>

#include<queue>

#define LL long long

#define inf 2147483640

#define MOD 998244353

#define Pi acos(-1.0)

#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);

using namespace std;

inline LL getint() {

    int f,x=0;char ch=getchar();

    while (ch<='0' || ch>'9') {if (ch=='-') f=-1;else f=1;ch=getchar();}

    while (ch>='0' && ch<='9') {x=x*10+ch-'0';ch=getchar();}

    return x*f;

}

const int maxn=50010;

struct edge {int to,w,next;}e[maxn<<2];

int vis[maxn],dis[maxn],head[maxn],n,cnt,L,R;

void insert(int u,int v,int w) {

    e[++cnt].to=v;e[cnt].next=head[u];head[u]=cnt;e[cnt].w=w;

}

int SPFA() {

    queue<int> q;

    for (int i=L;i<=R;i++) {

        vis[i]=1;

        dis[i]=0;

        q.push(i);

    }

    while (!q.empty()) {

        int x=q.front();

        q.pop();

        vis[x]=0;

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

            if (e[i].w+dis[x]>dis[e[i].to]) {

                dis[e[i].to]=e[i].w+dis[x];

                if (!vis[e[i].to]) {vis[e[i].to]=1;q.push(e[i].to);}

            }

    }

    return dis[R];

}

int main() {

    while (scanf("%d",&n)!=EOF) {

        memset(head,0,sizeof(head));

        L=inf,R=0;

        for (int u,v,w,i=1;i<=n;i++) {

            scanf("%d%d%d",&u,&v,&w);

            insert(u-1,v,w);

            L=min(L,u-1);

            R=max(R,v);

        }

        for (int i=L;i<=R;i++) {

            insert(i,i+1,0);

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

        }

        printf("%d\n",SPFA());

    }

    return 0;

}