poj 1752 差分约束（沿路建广告）

题意：有n个人在一条路上跑步，假设这条路上每一个点有一个广告牌，广告商准备在广告牌上贴广告。现在已知这n个人从ai开始跑，到bi结束，现在广告商需要每个人都至少要看到k个广告（对于跑步全程都小于k的人来说，需要他经过的每个广告牌上都有广告）。问满足条件的总的广告数和哪些广告牌上应该张贴广告。

思路：差分约束。Xi表示用起始点到Xi总共需要张贴的广告数量。那么对于第i个人,X(bi+1)-X(ai)>=min(k,bi+1-ai);其次有对于每个i，1>=X(i+1)-X(i)>=0。

我使用hash来表示顶点以减少空间复杂度。注意此时1>=X(i+1)-X(i)需要根据hash做出相应改变，而且这句话必不可少。反例为：

6 2

1 10

8 9

另外因为坐标有负数，所以我向右平移了10000个单位长度。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 1005
#define M 10000
int flag[(M<<1)+10],hh[N<<1];
int dis[N<<1],first[N<<1],q[1000000],used[N<<1];
int n,m,k,top;
struct point{
    int l,r;
}p[N];
struct edge{
    int y,next,w;
}e[8*N];
void add(int x,int y,int w){
    e[top].y = y;
    e[top].w = w;
    e[top].next = first[x];
    first[x] = top++;
}
int relax(int x,int y,int w){
    if(dis[y] < dis[x] + w){
        dis[y] = dis[x] + w;
        return 1;
    }
    return 0;
}
int spfa(){
    int rear,front,now,i;
    memset(used, 0, sizeof(used));
    rear = front = -1;
    for(i = 0;i<=m;i++)
        dis[i] = -0x3fffffff;
    dis[0] = 0;
    q[++rear] = 0;
    used[0] = 1;
    while(front < rear){
        now = q[++front];
        used[now] = 0;
        for(i = first[now];i!=-1;i=e[i].next)
            if(relax(now,e[i].y,e[i].w) && !used[e[i].y]){
                q[++rear] = e[i].y;
                used[e[i].y] = 1;
            }
    }
    return dis[m];
}
void print(int j,int d){
    if(d){
        print(j-1,d-1);
        printf("%d\n",j);
    }
}
int main(){
    int i;
    memset(flag, 0, sizeof(flag));
    memset(first, -1, sizeof(first));
    top = 0;
    scanf("%d %d",&k,&n);
    for(i = 1;i<=n;i++){
        scanf("%d %d",&p[i].l,&p[i].r);
        if(p[i].l > p[i].r)
            swap(p[i].l,p[i].r);
        p[i].l += M;
        p[i].r += M;
        flag[p[i].l] = 1;
        flag[p[i].r+1] = 1;
    }
    for(i = 0,m = 0;i<=2*M+1;i++)
        if(flag[i]){
            flag[i] = ++m;
            hh[m] = i;
        }
    for(i = 1;i<=n;i++)
        add(flag[p[i].l],flag[p[i].r+1],min(k,p[i].r+1-p[i].l));
    for(i = 1;i<m;i++){
        add(i,i+1,0);
        add(i+1,i,-(hh[i+1]-hh[i]));//这句话至关重要
    }
    for(i = 1;i<=m;i++)
        add(0,i,0);
    printf("%d\n",spfa());
    for(i = 2;i<=m;i++)
        if(dis[i] > dis[i-1])
            print(hh[i]-1-M,dis[i]-dis[i-1]);
    return 0;
}