本文共 1679 字，大约阅读时间需要 5 分钟。

2017年东莞市信息学特长生测试题 工程

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

55 4 12 7 20 0 0 00 0 0 00 0 0 01 1 0 01 1 1 1

project.in

55 4 12 7 20 1 0 00 0 0 00 0 1 01 1 0 01 1 1 1

Sample Output

project.out

14

project.out

-1

解题思路

拓扑+BFS+DP

#include<iostream>#include<cstdio>using namespace std;int n,a[210],b[210],c[210];int tot,head[210],f[210],dp[210];struct abc{   	int to,next;}s[40010];void add(int x,int y){   	s[++tot]=(abc){   y,head[x]};	head[x]=tot;}void tp(){   	int hd=0,tl=0;	for(int i=1;i<=n;i++)		if(b[i]==0)			tl++,f[tl]=i,dp[i]=a[i],c[i]=1;	while(hd<tl)	{   		hd++;		int x=f[hd];		for(int i=head[x];i;i=s[i].next)		{   			int y=s[i].to;			if(!c[y])			{   				dp[y]=max(dp[y],dp[x]);				b[y]--;				if(!b[y])				{   					dp[y]+=a[y];					c[y]=1;					tl++;					f[tl]=y;				}			}		}	}}int main(){   	cin>>n;	for(int i=1;i<=n;i++)		scanf("%d",&a[i]);	for(int i=1;i<=n;i++)		for(int j=1;j<=n;j++)			if(i!=j)			{   				int t;				scanf("%d",&t);				if(t)					add(j,i),b[i]++;			}	tp();	int ans=0;	for(int i=1;i<=n;i++)		if(b[i]!=0)		{   			cout<<-1<<endl;			return 0;		}		else			ans=max(ans,dp[i]);	cout<<ans<<endl;}