【DP+拓扑】关键子工程

   【Description】

　　在大型过程的施工前，我们经常把整个工程分为若干个子工程，并把这些子工程编号为 1、2、…、N；这样划分之后，子工程之间就会有一些依赖关系，即一些子工程必须在 某些子工程完成之后才能施工。由于子工程之间有相互依赖关系，因此有两个任务需要 我们去完成：首先，我们需要根据每个子工程的完成时间计算整个工程最少的完成时间；
　　另一方面，由于一些不可预测的客观因素会使某些子工程延期，因此我们必须知道哪些 子工程的延期会影响整个工程的延期，我们把有这种特性的子工程称为关键子工程；因 此第二个任务就是找出所有的关键子工程，以便集中精力管理好这些子工程，尽量避免 这些子工程延期，达到用最快的速度完成整个工程。为了便于编程，现在我们假设： ²根据预算，每一个子工程都有一个完成时间。子工程之间的依赖关系是：部分子工程必须在一些子工程完成之后才开工。 只要满足子工程间的依赖关系，在任何时刻可以有任何多个子工程同时在施工， 也既同时施工的子工程个数不受限制。
　　整个工程的完成是指：所有子工程的完成。
　　例如，有5个子工程的工程规划表:

　　

序号	完成时间	子工程1	子工程2	子工程3	子工程4	子工程5
子工程1	5		0	0	0	0
子工程2	4	0		0	0	0
子工程3	12	0	0		0	0
子工程4	7	1	1	0		0
子工程5	2	1	1	1	0

　　其中，表格中第I+1行J+2列的值如为0表示“子工程I”可以在“子过程J”没完成前施工，为I表示“子工程I”必须在“子过程J”完成后才能施工。上述工程最快完成时间为 14天，其中子工程1、3、4、5为关键子工程。

   【Input】

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

   【Output】

　　如子过程划分不合理，则输出-1；
　　如子过程划分合理，则用两行输出： 第1行为整个过程最好完成时间。
　　第2行为按有小到大顺序输出所有关键子过程的编号。

   【Sample Input 1】

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

【Sample Input 2】
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 1】

14 
1 3 4 5
【Sample Output 2】
-1

【Analysis】
　　拓扑排序+DP
　　关键子过程即最晚完成时间与最早完成时间相同的子过程。
　　第一次使用stack,和priority_queue相似，但stack为先进后出，queue为先进先出，同有top(),pop(),push(),empty(),size()等关键字。
【Code】

#include<cstdio>
#include<queue>
#include<stack>
#include<cstring>
#include<algorithm>
using namespace std;

const int sm = 200+10;

int n,tot,cnt,maxn,x,d;
int f[sm],g[sm],t[sm],h[sm],rd[sm],hh[sm],cd[sm];
stack<int>s;

struct edge{
    int to,nxt;
}e[sm*2],ee[sm*2];

void add(int f,int t) {
    e[++tot].to=t; e[tot].nxt=h[f]; h[f]=tot; rd[t]++;
    ee[tot].to=f; ee[tot].nxt=hh[t]; hh[t]=tot; cd[f]++;
}

int main() {
    
    scanf("%d",&n);
    for(int i=1;i<=n;++i)scanf("%d",&t[i]);
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j) {
            if(i==j)continue;
            scanf("%d",&x);
            if(x)add(j,i);
        }  
        
    for(int i=1;i<=n;++i)
        if(!rd[i]) s.push(i),f[i]=t[i];
        
    while(!s.empty()) {
        int now=s.top();s.pop();
        ++cnt;
        for(int i=h[now];i;i=e[i].nxt) {
            f[e[i].to]=max(f[e[i].to],f[now]+t[e[i].to]);
            rd[e[i].to]--;
            if(!rd[e[i].to])s.push(e[i].to);
        }
    }

    if(cnt!=n){printf("-1
");return 0;}
    
    memset(g,0x3f,sizeof(g));
    for(int i=1;i<=n;++i)
        if(cd[i]==0) {
            s.push(i);
            g[i]=maxn;
        }
    while(!s.empty()) {
        int now=s.top();
        s.pop();
        for(int i=hh[now];i;i=ee[i].nxt) {
            g[ee[i].to]=min(g[ee[i].to],g[now]-t[now]);
            --cd[ee[i].to];
            if(!cd[ee[i].to])s.push(ee[i].to);
        }
    }
    
    for(int i=1;i<=n;++i)maxn=max(maxn,f[i]);
    printf("%d
",maxn);
    for(int i=1;i<=n;++i)if(f[i]==g[i])printf("%d ",i);
    printf("
");
    return 0;
}