洛谷——P1113 杂务 + P3074 [USACO13FEB] Milk Scheduling S（拓扑排序）

---

一、题目

1. 杂务

题目描述

John 的农场在给奶牛挤奶前有很多杂务要完成，每一项杂务都需要一定的时间来完成它。比如：他们要将奶牛集合起来，将他们赶进牛棚，为奶牛清洗乳房以及一些其它工作。尽早将所有杂务完成是必要的，因为这样才有更多时间挤出更多的牛奶。

当然，有些杂务必须在另一些杂务完成的情况下才能进行。比如：只有将奶牛赶进牛棚才能开始为它清洗乳房，还有在未给奶牛清洗乳房之前不能挤奶。我们把这些工作称为完成本项工作的准备工作。至少有一项杂务不要求有准备工作，这个可以最早着手完成的工作，标记为杂务 $1$。

John 有需要完成的 $n$ 个杂务的清单，并且这份清单是有一定顺序的，杂务 $k(k>1)$ 的准备工作只可能在杂务 $1$ 至 $k?1$ 中。

写一个程序依次读入每个杂务的工作说明。计算出所有杂务都被完成的最短时间。当然互相没有关系的杂务可以同时工作，并且，你可以假定 John 的农场有足够多的工人来同时完成任意多项任务。

输入格式

第1行：一个整数 $n(3\le n\le 10,000)$，必须完成的杂务的数目；

第 $2$ 至 $n+1$ 行，每行有一些用空格隔开的整数，分别表示：

• 工作序号（保证在输入文件中是从 $1$ 到 $n$ 有序递增的）；
• 完成工作所需要的时间 $len(1\le len\le 100)$；
• 一些必须完成的准备工作，总数不超过 $100$ 个，由一个数字 $0$ 结束。有些杂务没有需要准备的工作只描述一个单独的 $0$。

保证整个输入文件中不会出现多余的空格。

输出格式

一个整数，表示完成所有杂务所需的最短时间。

样例 #1

样例输入 #1

7
1 5 0
2 2 1 0
3 3 2 0
4 6 1 0
5 1 2 4 0
6 8 2 4 0
7 4 3 5 6 0

样例输出 #1

23

2. [USACO13FEB] Milk Scheduling S

题目描述

Farmer John’s N cows (1 <= N <= 10,000) are conveniently numbered 1…N. Each cow i takes T(i) units of time to milk. Unfortunately, some cows must be milked before others, owing to the layout of FJ’s barn. If cow A must be milked before cow B, then FJ needs to completely finish milking A before he can start milking B.

In order to milk his cows as quickly as possible, FJ has hired a large number of farmhands to help with the task – enough to milk any number of cows at the same time. However, even though cows can be milked at the same time, there is a limit to how quickly the entire process can proceed due to the constraints requiring certain cows to be milked before others. Please help FJ compute the minimum total time the milking process must take.

农民约翰有N头奶牛(1<=N<=10,000)，编号为1…N。每一头奶牛需要T(i)单位的时间来挤奶。不幸的是，由于FJ的仓库布局，一些奶牛要在别的牛之前挤奶。比如说，如果奶牛A必须在奶牛B前挤奶，FJ就需要在给奶牛B挤奶前结束给奶牛A的挤奶。

为了尽量完成挤奶任务，FJ聘请了一大批雇工协助任务——同一时刻足够去给任意数量的奶牛挤奶。然而，尽管奶牛可以同时挤奶，但仍需要满足以上的挤奶先后顺序。请帮助FJ计算挤奶过程中的最小总时间。

输入格式

* Line 1: Two space-separated integers: N (the number of cows) and M (the number of milking constraints; 1 <= M <= 50,000).

* Lines 2…1+N: Line i+1 contains the value of T(i) (1 <= T(i) <= 100,000).

* Lines 2+N…1+N+M: Each line contains two space-separated integers A and B, indicating that cow A must be fully milked before one can start milking cow B. These constraints will never form a cycle, so a solution is always possible.

输出格式

* Line 1: The minimum amount of time required to milk all cows.

样例 #1

样例输入 #1

3 1 
10 
5 
6 
3 2

样例输出 #1

11

提示

There are 3 cows. The time required to milk each cow is 10, 5, and 6, respectively. Cow 3 must be fully milked before we can start milking cow 2.

Cows 1 and 3 can initially be milked at the same time. When cow 3 is finished with milking, cow 2 can then begin. All cows are finished milking after 11 units of time have elapsed.

二、题解

• 基本思路：
  杂物应该是后者改编的，需要用到拓扑排序，在每个事件完成之前都需要完成它的一些前置事件。两题都是拓扑排序的模板题。

杂务

#include<bits/stdc++.h>
using namespace std;

#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define endl "\n"
#define int long long 
#define repn(i,o,n) for(int i=o;i<=n;i++)
#define rep(i,o,n) for(int i=o;i<n;i++)
const int N = 1e4+10;
vector<int> edge[N];
int n,w[N],d[N],q[N];//花费时间、入度、存放的拓扑序列 
int f[N];//记录目前每个点所花费的时间 


inline void TopoSort(){
	int front=1,rear=0;
	repn(i,1,n)
	  if(!d[i])
	    q[++rear]=i,f[i]=w[i];
	while(front<=rear){
		int x=q[front++];
		for(auto y:edge[x]){
		  f[y]=max(f[y],f[x]+w[y]);
		  if(--d[y]==0){
		  	q[++rear]=y;
		  }
	    }
	}
	int ans=0;
	for(int i=1;i<=n;i++)
	  ans=max(ans,f[i]);//取较大值 
	cout<<ans<<endl;
}

void solve(){
	cin>>n;
	repn(i,1,n){
		int num,len,x;
		cin>>num>>len;
		w[num]=len;//工作序号为num完成工作所需要的时间 len 
		while(1){
			cin>>x;
			if(!x) break;
			edge[x].push_back(num);
			++d[num]; 
		}
	} 
//	repn(i,1,n)
//	   cout<<d[i]<<' ';//每个点的入度 
//	cout<<endl;
	TopoSort();
	
}

signed main(){
	int T=1;
	//cin>>T;
	while(T--){
		solve();
	}
	return 0;
}
/*
10
1 3 0
2 9 1 0
3 2 1 2 0
4 2 1 2 3 0
5 12 2 0
6 1 1 2 3 4 5 0
7 17 3 0
8 7 1 2 3 4 5 6 7 0
9 13 1 3 8 0
10 2 1 2 3 4 5 6 7 8 9 0

53
*/

[USACO13FEB] Milk Scheduling S

#include<bits/stdc++.h>
using namespace std;

#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define endl "\n"
#define int long long 
#define repn(i,o,n) for(int i=o;i<=n;i++)
#define rep(i,o,n) for(int i=o;i<n;i++)
const int N = 1e4+10;
vector<int> edge[N];
int n,m,ind[N],w[N],f[N];//入度、花费时间、当前时间 
queue<int> q;

inline void TopoSort(){
	repn(i,1,n)
	  if(!ind[i])
	   q.push(i),f[i]=w[i];
	while(!q.empty()){
		int x=q.front();
		q.pop();
		for(auto y:edge[x]){
			f[y]=max(f[y],f[x]+w[y]); 
			if(--ind[y]==0)
			  q.push(y);
		} 
	}
	int res=0;
	repn(i,1,n)
	  res=max(res,f[i]);
	cout<<res<<endl;
}

void solve(){
	cin>>n>>m;
	repn(i,1,n)
	  cin>>w[i];
	repn(i,1,m){
		int a,b;
		cin>>a>>b;
		edge[a].push_back(b);
		++ind[b];//b点入读加1 
	}
//	repn(i,1,n)
//	 cout<<ind[i]<<' ';//每个点的入度 
//	cout<<endl;
	TopoSort();
}

signed main(){
	int T=1;
	//cin>>T;
	while(T--){
		solve();
	}
	return 0;
}