Bzoj 3389: [Usaco2004 Dec]Cleaning Shifts安排值班 最短路,神题

时间：2022-03-06 07:02:05

3389: [Usaco2004 Dec]Cleaning Shifts安排值班

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 218  Solved: 86
[Submit][Status][Discuss]

Description

    一天有T(1≤T≤10^6)个时段．约翰正打算安排他的N(1≤N≤25000)只奶牛来值班，打扫
打扫牛棚卫生．每只奶牛都有自己的空闲时间段[Si，Ei](1≤Si≤Ei≤T)，只能把空闲的奶牛安排出来值班．而且，每个时间段必需有奶牛在值班．  那么，最少需要动用多少奶牛参与值班呢？如果没有办法安排出合理的方案，就输出-1.

Input

 
    第1行：N，T．
    第2到N+1行：Si，Ei．

Output

 
    最少安排的奶牛数．

Sample Input

3 10
1 7
3 6
6 10

Sample Output

2

样例说明
奶牛1和奶牛3参与值班即可．

HINT

 

Source

Silver

题解：

最短路

Orz Hzwer 的最短路。好神！！！

对于每个奶牛看守的区间[l,r]，我们从l-1向r去连边权为1的边，然后从每个i(1<=i<=T)向i-1连边权为0的边(就是可以反向跑)，跑最短路就可以了。

 #include<bits/stdc++.h>

 using namespace std;

 #define MAXN 1000010

 #define INF 1e9

 struct node

 {

     int begin,end,value,next;

 }edge[*MAXN];

 int cnt,Head[MAXN],T,E,dis[MAXN],Heap[MAXN],pos[MAXN],SIZE;

 void addedge(int bb,int ee,int vv)

 {

     edge[++cnt].begin=bb;edge[cnt].end=ee;edge[cnt].value=vv;edge[cnt].next=Head[bb];Head[bb]=cnt;

 }

 int read()

 {

     int s=,fh=;char ch=getchar();

     while(ch<''||ch>''){if(ch=='-')fh=-;ch=getchar();}

     while(ch>=''&&ch<=''){s=s*+(ch-'');ch=getchar();}

     return s*fh;

 }

 void Push1(int k)

 {

     int now=k,root;

     while(now>)

     {

         root=now/;

         if(dis[Heap[root]]<=dis[Heap[now]])return;

         swap(Heap[root],Heap[now]);

         swap(pos[Heap[root]],pos[Heap[now]]);

         now=root;

     }

 }

 void Insert(int k)

 {

     Heap[++SIZE]=k;pos[k]=SIZE;Push1(SIZE);

 }

 void Pop1(int k)

 {

     int now,root=k;

     pos[Heap[k]]=;Heap[k]=Heap[SIZE--];if(SIZE>)pos[Heap[k]]=k;

     while(root<=SIZE/)

     {

         now=root*;

         if(now<SIZE&&dis[Heap[now+]]<dis[Heap[now]])now++;

         if(dis[Heap[root]]<=dis[Heap[now]])return;

         swap(Heap[root],Heap[now]);

         swap(pos[Heap[root]],pos[Heap[now]]);

         root=now;

     }

 }

 void dijkstra(int start)

 {

     int i,u,v;

     for(i=;i<=T;i++)dis[i]=INF;dis[start]=;

     for(i=;i<=T;i++)Insert(i);

     while(SIZE>)

     {

         u=Heap[];Pop1(pos[u]);

         for(i=Head[u];i!=-;i=edge[i].next)

         {

             v=edge[i].end;

             if(dis[v]>dis[u]+edge[i].value){dis[v]=dis[u]+edge[i].value;Push1(pos[v]);}

         }

     }

 }

 int main()

 {

     int i,bb,ee,vv,n;

     n=read();T=read();//T++;E++;

     memset(Head,-,sizeof(Head));cnt=;

     for(i=;i<=T;i++)addedge(i,i-,);

     for(i=;i<=n;i++)

     {

         bb=read();ee=read();

         if(bb>ee)swap(bb,ee);

         addedge(bb-,ee,);

     }

     dijkstra();

     if(dis[T]==INF)printf("-1");

     else printf("%d",dis[T]);

     return ;

 }

相关文章