输入输出样例

输入 #1

7
1 5 0
2 2 1 0
3 3 2 0
4 6 1 0
5 1 2 4 0
6 8 2 4 0
7 4 3 5 6 0

输出 #1

23

思路
　　由主次关系可想到拓扑排序，跑一遍拓扑排序得到一种线性的工作方式，维护每个任务点时间花费的最大值即可

CODE

  1 #include <bits/stdc++.h>
  2 #define dbg(x) cout << #x << "=" << x << endl
  3 #define eps 1e-8
  4 #define pi acos(-1.0)
  5 
  6 using namespace std;
  7 typedef long long LL;
  8 
  9 template<class T>inline void read(T &res)
 10 {
 11     char c;T flag=1;
 12     while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0';
 13     while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;
 14 }
 15 
 16 namespace _buff {
 17     const size_t BUFF = 1 << 19;
 18     char ibuf[BUFF], *ib = ibuf, *ie = ibuf;
 19     char getc() {
 20         if (ib == ie) {
 21             ib = ibuf;
 22             ie = ibuf + fread(ibuf, 1, BUFF, stdin);
 23         }
 24         return ib == ie ? -1 : *ib++;
 25     }
 26 }
 27 
 28 int qread() {
 29     using namespace _buff;
 30     int ret = 0;
 31     bool pos = true;
 32     char c = getc();
 33     for (; (c < '0' || c > '9') && c != '-'; c = getc()) {
 34         assert(~c);
 35     }
 36     if (c == '-') {
 37         pos = false;
 38         c = getc();
 39     }
 40     for (; c >= '0' && c <= '9'; c = getc()) {
 41         ret = (ret << 3) + (ret << 1) + (c ^ 48);
 42     }
 43     return pos ? ret : -ret;
 44 }
 45 
 46 const int maxn = 1e5 + 7;
 47 
 48 int in[maxn], out[maxn];
 49 int val[maxn];
 50 int cost[maxn];
 51 int edge[maxn], head[maxn], nxt[maxn], cnt;
 52 int n, ans;
 53 
 54 void BuildGraph(int u, int v) {
 55     cnt++;
 56     edge[cnt] = v;
 57     nxt[cnt] = head[u];
 58     head[u] = cnt;
 59 }
 60 
 61 void topo() {
 62     queue <int> q;
 63     for ( int i = 1; i <= n; ++i ) {
 64         if(in[i] == 0) {
 65             q.push(i);
 66             cost[i] = val[i];
 67         }
 68     }
 69     while (!q.empty()) {
 70         int u = q.front();
 71         q.pop();
 72         for(int i = head[u]; i; i = nxt[i]) {
 73             int v = edge[i];
 74             cost[v] = max(cost[v], cost[u] + val[v]);
 75             --in[v];
 76             if(!in[v]) {
 77                 if(!out[v]) {
 78                     ans = max(ans, cost[v]);
 79                 }
 80                 else {
 81                     q.push(v);
 82                 }
 83             }
 84         }
 85     }
 86     
 87 }
 88 int main()
 89 {
 90     read(n);
 91     for ( int i = 1; i <= n; ++i ) {
 92         int id = 0, c = 0;
 93         scanf("%d %d",&id, &c);
 94         val[id] = c;
 95         int x;
 96         while(scanf("%d",&x) && x) {
 97             BuildGraph(id, x);
 98             out[id]++;
 99             in[x]++;
100         }
101     }
102     topo();
103     printf("%d\n",ans);
104     return 0;
105 }

View Code