差分约束_POJ 1752 Advertisement

    好久没做差分约束系统了，有点陌生。

    简述：给定一个数K和若干个区间Li , Ri(Li可能大于Ri，交换下即可)。|Li|,|Ri|<=10000。要在区间 [ Li , Ri ]上选出 K个点涂上颜色。求数轴上最少的被涂色的点的个数。(简单起见,假设 Li,Ri>=0)

    思路：差分约束系统:

    记 S_i 为 [ 0 , i ] 这个区间内染色的点的个数。那么就有S_Ri - S_( Li-1) >= min( K , Ri - Li + 1)。并且对于任意两个点i < j,有S_i + j - i >= S_ j，S_i <= S_ j.

于是得到：S_( Li - 1 ) <= S_Ri - min( K, Ri - Li +1);

          S_ j <= S_i + j - i. 

          S_i <= S_ j + 0.

然后连边的时候，鉴于后面两个不等式满足传递性，只要对相邻的两个点连一下就好，不需要两两连边。

Ps:初始化所有S_i 的值要相等。然后减掉 min{ S_i }，得到非负解。

下面代码稍微离散的一下。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define LL long long
#define clr(A) memset(A,0,sizeof(A))
using namespace std;

int const maxn =  10005;
int const B = 10003;
int N,K;

int b[maxn],e[maxn],w[maxn],tot;
int s[maxn*3];
int a[maxn],sum;
int main()
{
    int T;
    
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&K,&N);
        sum = tot = 0;
        int x,y;
        for(int i = 1;i<=N;i++)
        {
            scanf("%d%d",&x,&y);
            if(x>y) swap(x,y);
            x--;
            b[tot] = y, e[tot] = x,w[tot] = -min(K,y-x),tot++;
            a[sum++] = x, a[sum++] = y;
        }

        sort(a,a+sum);a[sum] = maxn;
        int cnt = 0;
        for(int i = 0;i<sum;i++)
        if(a[i] != a[i+1]) a[cnt++]=a[i];
        sum = cnt;

        for(int i = 1;i<sum;i++)
        {
            b[tot]=a[i-1],e[tot] = a[i],w[tot] = a[i]-a[i-1],tot++;
            b[tot]=a[i],e[tot] = a[i-1],w[tot] = 0, tot++;
        }

        clr(s);
        for(int i = 0;i<sum;i++)
        for(int j = 0;j<tot;j++)
        s[e[j]+B] = min(s[e[j]+B],s[b[j]+B]+w[j]);

        int tmp = s[a[0] + B];
        s[a[0] + B]  = 0;
        printf("%d\n",s[a[sum-1] + B]-tmp);
        for(int i = 1;i<sum;i++)
        {
            s[a[i] + B] -= tmp;
            int l = s[a[i] + B] - s[a[i-1] + B];
            for(int j = a[i] - l+1;j<=a[i];j++)
            printf("%d\n",j);
        }
        if(T) printf("\n");
    }
    return 0;
}