JZOJ 3233. 照片

题目

Description

Farmer John决定为他的N头排列好的奶牛（1 <= N<= 200,000）做一张全景合照。这N头奶牛分别以1..N进行编号。他一共拍了M（1<= M <=100,000）张相片，每张相片都只包含有一部分位置连续的奶牛：第i张照片涵盖着编号从a_i到b_i的所有奶牛。当然，这些照片合起来并不保证包含所有的牛。

Farmer John拍摄完所有的相片后，注意到一个很有趣的现象：他拍的每张照片中有且仅有一只奶牛身上有斑点。 FJ知道他的奶牛中有一部分是身上有斑点的，但他从来没有数过这种奶牛的数目。请根据FJ的这些照片，确定可能出现的斑点牛的最大的数目；若从FJ的照片中无法推测斑点牛的数目，则输出-1。

 

Input

第1行：包含两个整数N、M。

第2.. M+1.. i +1行：每行包含两个整数a_i和b_i。

Output

输出仅一行，要求输出FJ根据他的照片所能推测出的斑点牛的最大数目；若无法推测这些奶牛的数目，则输出-1。

 

 

Sample Input

5 3

1 4

2 5 

3 4

Sample Output

1

 

Data Constraint

​1 <= N<= 200,000

 

分析

 

• 差分约束
• sum[r]-sum[l-1]=1
• sum[i]-sum[i-1]<=1
• 所以l-1 r 1   r l-1 -1  i-1 i 1 i-1 i 0

 

代码

#include<iostream>
#include<queue>
#include<cstdio>
using namespace std;
const int inf=100000000;
struct sb
{
    int to,nx,w;
}g[1000001*4];
int cnt,list[1000001*4];
void add(int x,int y,int w)
{
    g[++cnt].to=y; g[cnt].nx=list[x]; g[cnt].w=w; list[x]=cnt;
}
int dis[1000001],vis[1000001];
int n,m;
int tot;
int spfa()
{
    for(int i=0;i<=n;i++) dis[i]=inf;
    deque<int> q;
    dis[0]=0; q.push_back(0); vis[0]=1;
    while (!q.empty())
    {
        int x=q.front(); q.pop_front(); vis[x]=0;
        for (int i=list[x];i;i=g[i].nx)
        {
            int y=g[i].to;
            if (dis[x]+g[i].w<dis[y])
            {
                dis[y]=dis[x]+g[i].w;
                if (!vis[y])
                {
                    if (++tot>1926817) return -1;
                    vis[y]=1;
                    if (q.size()&&dis[g[i].to]>dis[q.front()]) q.push_back(g[i].to); else q.push_front(g[i].to);
                }
            }
       }
    
    } 
    return dis[n];
} 
int main ()
{
    scanf("%d%d",&n,&m);
    for (int i=1,l,r;i<=m;i++)
    {
        scanf("%d%d",&l,&r);
        add(l-1,r,1); add(r,l-1,-1);
    }
    for (int i=1;i<=n;i++)
      add(i-1,i,1),add(i,i-1,0);
    long long a=spfa();
    if (a==inf||a==-1)  cout<<-1;
    else cout<<a;
 }