好久没做差分约束系统了,有点陌生。
简述:给定一个数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;
}