工程

Description

张三是某工程公司的项目工程师。一天公司接下一项大型工程，该公司在大型工程的施工前，先要把整个工程划分为若干个子工程，并把这些子工程编号为1、2、…、N；这样划分之后，子工程之间就会有一些依赖关系，即一些子工程必须在某些子工程完成之后才能施工，公司需要工程师张三计算整个工程最少的完成时间。
对于上面问题，可以假设：
1、根据预算，每一个子工程都有一个完成时间。
2、子工程之间的依赖关系是：部分子工程必须在一些子工程完成之后才开工。
3、只要满足子工程间的依赖关系，在任何时刻可以有任何多个子工程同时在施工，也即同时施工的子工程个数不受限制。
例如：有五个子工程的工程规划表：

现在对于给定的子工程规划情况，及每个子工程完成所需的时间，如果子工程划分合理则求出完成整个工程最少要用的时间，如果子工程划分不合理，则输出-1。

Input

第1行为正整数N，表示子工程的个数（N<=200）
第2行为N个正整数，分别代表子工程1、2、…、N的完成时间。
第3行到N+2行，每行有N-1个0或1，其中的第K+2行的这些0或1，分别表示“子工程K”与子工程1、2、…、K-1、K+1、…、N的依赖关系（K=1、2、…、N）。每行数据之间均用空格分开。

Output

如果子工程划分合理则输出完成整个工程最少要用的时间，如果子工程划分不合理，则输出-1。

Sample Input

project.in
5
5 4 12 7 2
0 0 0 0
0 0 0 0
0 0 0 0
1 1 0 0
1 1 1 1.

project.in
5
5 4 12 7 2
0 1 0 0
0 0 0 0
0 0 1 0
1 1 0 0
1 1 1 1

Sample Output

project.out
14

project.out
-1

解题思路

这题也是一道拓扑排序+dp
拓扑排序：
其作用与奖金（拓扑排序）一样
dp：
可以用一个f[i]
表示完成 i 工程最少用多久

AC代码

#include<cstdio>
#include<iostream>
using namespace std;
long long n,m,x,y,h,t,s,tot,b[10005],c[10005],p[10005],f[10005],du[10005],head[10005];
struct node
{
   
	long long to,next;
}a[10005];
void add(int x,int y)
{
   
	a[++tot]=(node){
   y,head[x]};
	head[x]=tot;
}
void tp()//拓扑排序
{
   
	for(int i=1;i<=n;i++)if(du[i]==0){
   f[i]=b[i];p[++t]=i;c[i]=1;};//度为0，就标记，入队
	while(h<t)
	{
   
		h++;
		for(int i=head[p[h]];i;i=a[i].next)
		 if(c[a[i].to]==0)
		 {
   
		 	f[a[i].to]=max(f[a[i].to],f[p[h]]);//找时间最大的父节点
			du[a[i].to]--;//度--
			if(du[a[i].to]==0)//如果没有父节点
			{
   
				f[a[i].to]+=b[a[i].to];//就加上自己的工作量
				c[a[i].to]=1;//标记
				p[++t]=a[i].to;//入队
			}
		 } 	
	}
}
int main()
{
   
	cin>>n;
	for(int i=1;i<=n;i++)cin>>b[i];//输入
	for(int i=1;i<=n;i++)
	 for(int j=1;j<=n;j++)
	  if(i!=j)
	  {
   
	  	int x;
		cin>>x;
		if(x==1)
		{
   
			add(j,i);//邻接表 j=题目中的j i=题目中的k
			du[i]++;//du++
		}
	  }    
	tp();
	for(int i=1;i<=n;i++)//输出
	 if(du[i]!=0){
   cout<<-1;return 0;}
	 else s=max(s,f[i]);//找最大工作时间
	cout<<s; 
}

谢谢