poj Integer Intervals

传送门
区间上的差分约束问题

思路

若\(d[x]-d[y]<=/>= c\) ,则由y向x连一条权值为\(c\)的边
设\(d[i]\)为从1号点到i最少选出的数的个数
根据题目要求，对于区间\([l,r]\),得约束条件\(1:d[r]-d[l-1]>=2\)
为保证连续性，隐含约束条件\(2：0<=d[i]-d[i-1]<=1\)
即每个点要么不选，要么只能选一次
设总区间\([s,t]\)
那么目的就是 \(d[t]-d[s]>=ans\)
即\(d[t]>=ans+d[s]\)，所以\(spfa\)跑最长路
因为题目中，输入数据端点可能有\(0\)，所以我们将所有的数整体后移一位

code

#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 10002
using namespace std;
int n, minn = N, maxn;
struct node {
    int to,next,w;
}edge[N << 2];
int dis[N], front[N], tot;
bool v[N];

int read() {
	int s = 0, f = 0; char ch = getchar();
	while (!isdigit(ch)) f |= (ch == '-'), ch = getchar();
	while (isdigit(ch)) s = s * 10 + (ch ^ 48), ch = getchar();
	return f ? -s : s;
}

void add(int u, int v, int w) {
    edge[++tot].to = v;
    edge[tot].next = front[u];
    front[u] = tot;
    edge[tot].w = w;
}

void spfa() {
    memset(dis, -1, sizeof dis);
	queue<int>q; q.push(minn);
    v[minn]=true, dis[minn]=0;
    while (!q.empty()) {
        int now = q.front();
        q.pop(), v[now] = false;
        for (int i = front[now]; i; i = edge[i].next) {
            int to = edge[i].to;
            if (dis[to] < dis[now] + edge[i].w) {
                dis[to] = dis[now] + edge[i].w;
                if (!v[to]) v[to] = true, q.push(to);
            }
        }
    }
    printf("%d", dis[maxn]);
}

int main() {
	n = read();
    for (int i = 1, x, y; i <= n; i++) {
        x = read(), y = read(); y++;
        add(x, y, 2);
        minn = min(x, minn);
        maxn = max(maxn, y);
    }
    for (int i = minn; i < maxn; i++) {
        add(i, i + 1, 0);
        add(i + 1, i, -1);
    }
    spfa();
    return 0;
}