[bzoj3389][Usaco2004Dec]Cleaning Shifts安排值班

Cleaning Shifts bzoj-3389 Usaco-2004Dec

题目大意：每天有n个时间段，每个时间段都必须安排一个奶牛值班。有m个奶牛，每个奶牛只有一个空闲时间s[i]~e[i]，求至少动用多少奶牛。

注释：$1\le n\le 10^6$，$1\le m\le 25,000$。

想法：神题

我们将所有的时间点排成一排，然后对每一个i+1向i连一条无代价的边。

对于每一个s[i]向其对应的e[i]连边，代价为1.

然后求1到n的最短路即可

这样建图的道理：首先，从后面的时间点向前面的时间点连边是没有任何问题的。这就相当于我已经管理到了x时间段，我雇佣一个开始于x之前的奶牛，显然是可行且无代价的。

那么从s[i]向e[i]连边，就是说我雇佣这头奶牛，此时我已经管理到了e[i]这个时间点。

最后，附上丑陋的代码... ...

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <queue>

#define M 1000010

#define N 30010

using namespace std;

int dis[M];

bool v[M];

struct cmp

{

	bool operator()(int x,int y)

	{

		return dis[x]>dis[y];

	}

};

priority_queue<int,vector<int>,cmp>q;

int head[M],to[N+M],nxt[N+M],val[N+M],tot;

inline void add(int x,int y,int z)

{

	to[++tot]=y;

	val[tot]=z;

	nxt[tot]=head[x];

	head[x]=tot;

}

inline void original()

{

	memset(dis,0x3f,sizeof dis);

}

int main()

{

	int n,m;

	cin >> n >> m ;

	for(int i=1;i<=m;i++) add(i,i-1,0);

	original();

	for(int x,y,i=1;i<=n;i++)

	{

		scanf("%d%d",&x,&y);

		add(x-1,y,1);

	}

	dis[0]=0;

	q.push(0);

	while(!q.empty())

	{

		int x=q.top();q.pop();

		if(v[x]) continue;

		for(int i=head[x];i;i=nxt[i])

		{

			if(v[to[i]]) continue;

			if(dis[to[i]]>dis[x]+val[i])

			{

				dis[to[i]]=dis[x]+val[i];

				q.push(to[i]);

			}

		}

	}

	if(dis[m]==0x3f3f3f3f) printf("-1\n");

	else printf("%d\n",dis[m]);

	return 0;

}

小结：好题，感觉自己图论菜的一匹... ...

巴特西

[bzoj3389][Usaco2004Dec]Cleaning Shifts安排值班_最短路

最新文章

热门文章