图论
今天训练的题目，题意：有一些工作要做必须等某些工作做完了才能开始，每个工作也要花费时间去做。输入先给出n，m，表示有n个工作，要求完成第m个工作的最短时间（工作从1到n标号），下面n行给出每个工作的信息，每行第一个数表示做这个工作要多少时间，后面可能有1个或多个或0个数字，表示这个工作要在这些工作做完后才能动工。另外注意一点，同一个时刻只能做一个人工作，不能同时进行多个工作
这题一开始看错，以为又是关键路径，敲了模板发现wa，才看到那句话，同一个时间只能做一个工作不能同时进行多个工作，因为这个条件，这道题可以说和关键路径就毫无关系了。后来想不出方法，在队友的提醒下想到了正解。
其实我们只要知道第m个工作前面有多少个工作，每个工作的时间只能被计算一次
好像1-->2-->3-->4 , 2--->4 , 1-->5--->4
在4只能的点有1,2,3,5，这些点都影响了4，但是俺路径来算，要按点来算，每个点的时间只能算一次，所以完成4的最早时间就是
T[4]=val[1]+val[2]+val[3]+val[5]+val[4]; (做它本身也需要时间)
但是怎么知道m前面有哪些点呢，队友提示，图是有向图而且保证了无环，那么只要把所有有向边取反，从m点出发，遍历一次图即可，因为从m出发能去到的点，在取反前应该是这些点能去到m，而且遍历的话就能保证每个点只被访问一次，时间也就只计算了一次
用了vector建图，如果手动模拟邻接表的话时间会快些
#include <cstdio> #include <cstring> #include <vector> using namespace std; #define N 10010 vector<int>a[N]; int val[N]; int n,m; bool vis[N]; int res; void dfs(int u) { vis[u]=true; res += val[u]; int size=a[u].size(); for(int i=0; i<size; i++) if(!vis[ a[u][i] ]) dfs(a[u][i]); return ; } void solve() { res=0; memset(vis,0,sizeof(vis)); dfs(m); printf("%d\n",res); } int main() { //freopen("input.txt","r",stdin); while(scanf("%d",&n)!=EOF && n) { scanf("%d",&m); for(int i=1; i<=n; i++) a[i].clear(); for(int i=1; i<=n; i++) { char ch; int u,v; scanf("%d",&val[i]); ch=getchar(); if(ch=='\n') continue; while(1) { scanf("%d",&u); a[i].push_back(u); ch=getchar(); if(ch=='\n') break; } } solve(); } return 0; }