poj 1201&zoj 1508 Intervals(差分制約)

タイトルはこちらを押してください
n個の整数閉区間[ai,bi]とn個の正の整数ciを与えて、1つの正の整数集合Zを求めて、Zと[ai,bi]が交差する元素の個数がcより小さくないことを要求して、Zの中で元素の最小の個数.
テーマ分析:差分制約.まず,すべての集合の最右端点をst,Siを0−iのすべての正の整数として記録すると,Zは最大stとなる.Zが0−stのすべての要素の集合であると仮定してから,与えられた制約関係に従って徐々に縮小する.
区間[ai,bi],Zとの交差が少なくともciである場合,制約関係が得られる:Sbi−Sai−1>=ci,すなわちSai−1−Sbi<=−ci,点bi,ai−1はエッジを構築し,重み値−ciである.合計n個の制約関係.
しかし,このn個の制約関係だけでは不十分である.ある点iについては、ZにおいてもZにおいてもなくてもよく、iがZにあるときはSi−Si−1=1、iがZにないときはSi−Si−1=0であってもよい.従って,各点に対してまた2つの制約関係がある:0<=Si−Si−1<=1.
テーマはZ中の要素の最小個数を要求し,全区間の最左断点がedであると仮定すると,Sst−Sed−1は求められ,stをソース点として最短絡を走ればよい.
trick:区間端点は0から取るので、下付きでさらに1を引くとREになりますが、解決策は区間を入力するときに同時に1桁右に移動し、結果に影響しません.
詳細はコードを参照してください.

#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1000005;
const int inf = 0x3f3f3f3f;
int n;
int head[N];
bool flag[N];
struct node
{
    int to,next,val;
}g[N<<1];
int num;
int queue[N];
int front,rear;
int dis[N];
int st,ed;
void build(int s,int e,int v)
{
    g[num].to = e;
    g[num].val = v;
    g[num].next = head[s];
    head[s] = num ++;
}
void SPFA()
{
    int i;
    for(i = ed-1;i <= st;i ++)//    ed-1     ，  ed-1           ，poj   ，zoj      ，          。。。

    {
        dis[i] = inf;
        flag[i] = false;
    }
    dis[st] = 0;
    flag[st] = true;
    front = rear = 0;
    queue[rear ++] = st;
    while(front < rear)
    {
        int u = queue[front++];
        flag[u] = false;
        for(i = head[u];i != -1;i = g[i].next)
        {
            if(dis[g[i].to] > dis[u] + g[i].val)
            {
                dis[g[i].to] = dis[u] + g[i].val;
                if(flag[g[i].to] == false)
                {
                    flag[g[i].to] = true;
                    queue[rear ++] = g[i].to;
                }
            }
        }
    }
}
int main()
{
    int i,a,b,c;
    while(~scanf("%d",&n))
    {
        st = 0;ed = N;
        num = 0;
        memset(head,-1,sizeof(head));
        for(i = 1;i <= n;i ++)
        {
            scanf("%d%d%d",&a,&b,&c);
            a ++;b ++;
            if(st < b)
                st = b;
            if(ed > a)
                ed = a;
            build(b,a - 1,-c);
        }
        for(i = ed;i <= st;i ++)
        {
            build(i - 1,i,1);
            build(i,i - 1,0);
        }
        SPFA();
        printf("%d
",dis[st] - dis[ed - 1]);
    }
    return 0;
}
//8456K	297MS