USACO13FEB 牛奶调度Milk Scheduling

发表于 更新于 分类于

本人思路：拓扑思想+简单模拟

1
这道题其实并不难，只是用到了拓扑的思想，A奶牛必须在B奶牛挤奶前挤奶，这就形成了一个有向图，点A指向点B。

我们只需要记一下总量（实际上是每只奶牛挤奶时间的总和），每一次循环将入度为0的奶牛加入要挤奶的数组，并且取挤奶数组的最小值，让在挤奶数组里的奶牛减去最小值，如果一个奶牛挤完奶了，那就删除与它相连的边，并且相连的点入度减一，总时间加上最小值，总量减去最小值*挤奶牛数，直到总量为0结束,如果到这里还不懂可以看代码，代码有更详细的解释。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<iostream>
#include<cstdio>
#include<cstring>
#define maxn 10007
using namespace std;
int n,m,minn,ans,tot,len;  //n奶牛数目 m有先后要求的量 minn挤奶数组的最小值 ans最后答案  tot总量 len挤奶数组长度 
int a[maxn],ru[maxn],q[maxn];  //a[]每只奶牛挤奶时间 ru[]每只奶牛的入度 q[]挤奶数组 
bool edg[20000][20000];  //二维数组建图（模拟大法好） 
int main()  //程序开始 
{
	scanf("%d%d",&n,&m);   
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]),tot+=a[i];  //输入，并且计算总量 
	for(int i=1;i<=m;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		ru[y]++;  //x指向y  y入度+1 
		edg[x][y]=1;  //建图 
	}
	while(tot)  //直到总量为0结束 
	{
		minn=0x7fffffff;  //先赋一个最大值 
		len=0; 
		memset(q,0,sizeof(q));  //挤奶数组长度、内容清零 
		for(int i=1;i<=n;i++)
		{
			if(!ru[i]&&a[i]>0)  q[++len]=i,minn=min(minn,a[i]);  //找还有奶并且入度为0的奶牛加入挤奶数组 && 计算挤奶最小值 
		}
		for(int i=1;i<=len;i++)
		{
			a[q[i]]-=minn;  //每只挤奶奶牛减去最小值 
			if(a[q[i]]<=0)  //处理没奶的奶牛 
			{
				for(int j=1;j<=n;j++)
				{
					if(edg[q[i]][j]==1)  ru[j]--,edg[q[i]][j]=0;  //删除和它相连的所有边以及和它相连点的入度 
				}
			}
		}
		tot-=(minn*len);  //总量减去（最小值*挤奶奶牛数） 
		ans+=minn;   //需要时间（答案）加上最小值 
	}
	printf("%d",ans);  //输出 
	return 0;  //程序结束 
}
另外嘱咐大家一句：数组一定要够大，否则RE

最后祝大家

RP++；