有点绕，两层拓扑排序。
有空再补详细。
甚至有点丑，因为绕，为了区分，当时变量名写得很长。
设题目中每个endpoint为点 即是point
然后设 每个点 里边包含的任务为 task，每个点有k个任务
将每个点的task 的[0 or 1]操作记录在taskqua[][][]里边，表示任务要解决的问题
将每个点的task 的依赖任务，即是每个task前的L后边给出的数，记录再 pointtaskdepend[u][i]，表示第u个点的第i个任务的依赖任务，其中1<=i<=k(k是每个点给出的k)
根据单个点的任务依赖关系，可以排出一个拓扑序列
这是里边一层的事
但是，任务task的询问里还有对*别的点*的调用，这时，就记录每个点里边，taskqua出现的*别的点*，根据各个点的依赖关系，给出一个拓扑序列。这是外层。
于是，排好序。逆序解决外层拓扑序列的点的Q[],即记录最后qi询问的答案，在解决每个Q[]时，逆序解决里层task花费的时间 即是，每个task的 taskcaltime[i] 1<=i<=k
对于解决单个点的Q[],例如一个任务有依赖别的任务，即是有出边，它的花费时间等于本身花费时间（设为x 即是在taskqua里边需要花费的时间）加上**所依赖任务里边的最大时间**
然后就这样子了吧。
巨丑的代码:
#include<cstdio> #include<algorithm> #include<cstring> #include<queue> #include<vector> #define debug printf("!") using namespace std; typedef __int64 ll; const int mod=1e9+7; const int maxn=2e4+5; const int inf=0x3f3f3f3f; /* 设题目中每个endpoint为点 即是point 然后设 每个点 里边包含的任务为 task，每个点有k个任务 将每个点的task 的[0 or 1]操作记录在taskqua[][][]里边，表示任务要解决的问题 将每个点的task 的依赖任务，即是每个task前的L后边给出的数，记录再 pointtaskdepend[u][i]，表示第u个点的第i个任务的依赖任务，其中1<=i<=k(k是每个点给出的k) 根据单个点的任务依赖关系，可以排出一个拓扑序列 这是里边一层的事 但是，任务task的询问里还有对*别的点*的调用，这时，就记录每个点里边，taskqua出现的*别的点*，根据各个点的依赖关系，给出一个拓扑序列。这是外层。 于是，排好序。逆序解决外层拓扑序列的点的Q[],即记录最后qi询问的答案，在解决每个Q[]时，逆序解决里层task花费的时间 即是，每个task的 taskcaltime[i] 1<=i<=k 对于解决单个点的Q[],例如一个任务有依赖别的任务，即是有出边，它的花费时间等于本身花费时间（设为x 即是在taskqua里边需要花费的时间）加上**所依赖任务里边的最大时间** */ int main() { int m,n,u,v,i,j,k,l,y,r,e; int K[maxn]; ll Q[maxn]={0}; vector<int> pointtaskdepend[maxn][110]; vector<int> pointdepend[maxn]; vector<int> pointtaskque[maxn]; vector<int> pointque; int In[maxn]={0}; int taskqua[maxn][110][2]; scanf("%d%d",&n,&m); for(u=1;u<=n;u++) { int in[110]={0}; scanf("%d",&k);K[u]=k; for(i=1;i<=k;i++) { scanf("%d",&l); for(j=1;j<=l;j++) { scanf("%d",&y); pointtaskdepend[u][i].push_back(y); in[y]++; } scanf("%d%d",&taskqua[u][i][0],&taskqua[u][i][1]); if(taskqua[u][i][0]) { pointdepend[u].push_back(taskqua[u][i][1]); In[taskqua[u][i][1]]++; } } queue<int>q; for(i=1;i<=k;i++) if(in[i]==0)q.push(i); while(!q.empty()) { int p=q.front(); q.pop(); pointtaskque[u].push_back(p); for(int i=0;i<pointtaskdepend[u][p].size();i++) { y=pointtaskdepend[u][p][i]; in[y]--; if(in[y]==0) q.push(y); } } } queue<int>q; for(i=1;i<=n;i++) if(In[i]==0) q.push(i); while(!q.empty()) { int p=q.front(); q.pop(); pointque.push_back(p); for(i=0;i<pointdepend[p].size();i++) { y=pointdepend[p][i]; In[y]--; if(In[y]==0) q.push(y); } } for(v=n-1;v>=0;v--) { u=pointque[v]; ll ans=0; ll taskcaltime[110]={0}; for(i=K[u]-1;i>=0;i--) { ll x,y=0; if(taskqua[u][pointtaskque[u][i]][0])x=(Q[taskqua[u][pointtaskque[u][i]][1]]+1)%mod; else x=taskqua[u][pointtaskque[u][i]][1]; if(pointtaskdepend[u][pointtaskque[u][i]].size()==0) { taskcaltime[pointtaskque[u][i]]=x%mod; ans=max(ans,x)%mod; continue; } for(j=0;j<pointtaskdepend[u][pointtaskque[u][i]].size();j++) { y=max(y,(ll)taskcaltime[pointtaskdepend[u][pointtaskque[u][i]][j]]); } taskcaltime[pointtaskque[u][i]]=(x+y)%mod; ans=max(ans,(x+y)%mod); } Q[u]=ans; } for(i=1;i<=m;i++) { scanf("%d",&v); printf("%I64d ",Q[v]); } }
2019-09-06