POJ - 1716 差分约束

题意：

给出n个区间，现在要你找出一个点集，使得这n个区间都至少有2个元素在这个点集里面，问这个点集最少有几个点

第一行一个整数n。
接下来n行，每行两个整数a,b,表示区间的左端点和右端点，被空格隔开。
所有输入数据的范围[0,10000]

输出集合最小的大小，满足区间都至少有两个点在集合中。

思路：

我们用 $d [i]$ 代表0~i中存在点的个数。

那么d数组满足下列约束条件

对于每个区间 a b，我们有 $d [b] - d [a - 1] > = 2$
每个位置要求 $d [i] > = 0$
相邻位置要求 $0 < = d [i] - d [i - 1] < = 1$

我们可以找出 $a - 1$ 中的最小值 $m i n$ ，b中的最大值 $m a x$ ，令 $d [m i n] = 0$ ,最后求 $d [m a x]$ 的最小值即可

因为求最小值，所以我们用spfa的最长路算法

代码：

#include<iostream>
#include<cstring>
#include<string>
#include<cstdlib>
#include<queue>
#include<stack>
//#include<bits/stdc++.h>
#define mset(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
const  int inf=0x3f3f3f3f;
/* Si代表1~i中取的个数，则满足 S[b]-S[a-1]>=2 b -> a-1 2 序列又满足: S[i]>=S[i-1] i -> i-1 0 S[i-1]+1>=S[i] i-1 -> i -1 */
struct Edge{
int to,w,next;
Edge(){}
Edge(int to,int w):to(to),w(w){}
}edge[3*10000+20];
int dis[10000+20],in[10000+20];
stack<int> qe;
int head[10000+20],tot=0;
void addEdge(int u,int v,int w,int q)
{
    edge[q].to=v;edge[q].w=w;
    edge[q].next=head[u];
    head[u]=q;
}
void spfa(int x,int n)
{
    mset(in,0);
    for(int i=0;i<n;++i) dis[i]=-1*inf;
    qe.push(x);in[x]=1;dis[x]=0;
    while(!qe.empty()){
       int u=qe.top();qe.pop();in[u]=0;
       int to=head[u];
       while(~to)
       {
           int v=edge[to].to,w=edge[to].w;
            if(dis[v]<dis[u]+w){
                dis[v]=dis[u]+w;
                if(!in[v]){
                    in[v]=1;
                    qe.push(v);
                }
            }
           to=edge[to].next;
       }
    }
}
int main()
{
    ios::sync_with_stdio(false);cin.tie(0);
    mset(head,-1);
    int m,maxx=-1,minn=inf;
    cin>>m;
    for(int i=0;i<m;++i){
        int a,b;
        cin>>a>>b;
        ++a,++b;
        maxx=maxx<b?b:maxx;
        minn=min(minn,a-1);
        addEdge(a-1,b,2,tot++);
// adja[a-1].push_back(Edge(b,2));
    }
// cout<<"minn:"<<minn<<" maxx:"<<maxx<<endl;
    for(int i=1;i<=maxx;++i){
        addEdge(i,i-1,-1,tot++);
        addEdge(i-1,i,0,tot++);
    }
    spfa(minn,maxx+1);
    cout<<dis[maxx]-dis[minn]<<endl;
    return 0;
}

POJ - 1716 (spfa差分约束)

POJ - 1716 差分约束