{"id":757,"date":"2020-08-05T11:57:53","date_gmt":"2020-08-05T03:57:53","guid":{"rendered":"http:\/\/www.zyhcoding.club\/?p=757"},"modified":"2020-08-05T12:10:28","modified_gmt":"2020-08-05T04:10:28","slug":"%e7%bc%a9%e7%82%b9","status":"publish","type":"post","link":"http:\/\/www.zyhcoding.club\/index.php\/2020\/08\/05\/%e7%bc%a9%e7%82%b9\/","title":{"rendered":"\u7f29\u70b9"},"content":{"rendered":"

\u7f29\u70b9<\/h3>\n

\u7f29\u70b9\u5c31\u662f\u628a\u6709\u5411\u56fe\u91cc\u7684\u4e00\u4e2a\u5f3a\u8fde\u901a\u5206\u91cf\u5f53\u6210\u662f\u4e00\u4e2a\u70b9\u6765\u5904\u7406\uff0c\u56e0\u4e3a\u4e00\u4e2a\u5f3a\u8fde\u901a\u5206\u91cf\u91cc\u7684\u70b9\u90fd\u53ef\u4ee5\u4e92\u76f8\u5230\u8fbe\uff0c\u6240\u4ee5\u628a\u4ed6\u4eec\u5f53\u6210\u4e00\u4e2a\u70b9\uff0c\u6743\u503c\u4e3a\u6240\u6709\u70b9\u6743\u503c\u4e4b\u548c\uff0c\u8fd9\u6837\u5c31\u53ef\u4ee5\u628a\u4e00\u4e2a\u6709\u5411\u56fe\u7f29\u6210\u4e00\u4e2aDAG(\u6709\u5411\u65e0\u73af\u56fe)\u3002\u6ce8\u610f\u5f3a\u8fde\u901a\u5206\u91cf\u4e4b\u95f4\u7684\u8fb9\u3002<\/p>\n

P3387 \u3010\u6a21\u677f\u3011\u7f29\u70b9<\/a><\/h5>\n
#include <cstdio>\n#include <vector>\n#include <stack>\n#include <algorithm>\n#include <cstring>\nusing namespace std;\nconst int maxn = 1e4+5, maxm = 1e5+5;\nint n, m;\nint val[maxn];\nstruct edge{\n    int from, to, next;\n}e[maxm];\nint head[maxn], tot;\nint dfn[maxn], low[maxn], num, vis[maxn];\nstack<int> sta;\n\nvector<int> G[maxn];\nint val2[maxn], dp[maxn];\nint getDP(int u){\n    if (dp[u]!=-1)  return dp[u];\n    dp[u] = val2[u];\n    int tmp = 0;\n    for (int i=0; i<G[u].size(); i++)\n        tmp = max(tmp, getDP(G[u][i]));\n    dp[u] += tmp;\n    return dp[u];\n}\n\nvoid Tarjan(int u){\n    dfn[u] = low[u] = ++num;\n    sta.push(u);    vis[u] = 1;\n    for (int i=head[u]; i; i=e[i].next){\n        if (!dfn[e[i].to]){\n            Tarjan(e[i].to);\n            low[u] = min(low[u], low[e[i].to]);\n        }else if (vis[e[i].to]) low[u] = min(low[u], dfn[e[i].to]);\n    }\n    if (low[u]==dfn[u]){\n        while (sta.top()!=u){\n            vis[sta.top()] = 0;\n            low[sta.top()] = low[u];\n            sta.pop();\n        }\n        vis[sta.top()] = 0;\n        sta.pop();\n    }\n    return;\n}\ninline void add(int from, int to){\n    tot++;\n    e[tot].from = from, e[tot].to = to, e[tot].next = head[from];\n    head[from] = tot;\n}\nint main(){\n    int from, to;\n    scanf ("%d %d", &n, &m);\n    for (int i=1; i<=n; i++)    scanf ("%d", val+i);\n    for (int i=1; i<=m; i++){\n        scanf ("%d %d", &from, &to);\n        add(from, to);\n    }\n    for (int i=1; i<=n; i++)    if (!dfn[i])\n        Tarjan(i);\n    for (int i=1; i<=tot; i++)  if (low[e[i].from] != low[e[i].to])\n        G[low[e[i].from]].push_back(low[e[i].to]);\n    for (int i=1; i<=n; i++)    val2[low[i]] += val[i];\n    memset (dp, -1, sizeof dp);\n    int ans = 0;\n    for (int i=1; i<=n; i++)\n        ans = max(ans, getDP(i));\n    printf ("%d", ans);\n    return 0;\n}<\/code><\/pre>\n
P3627 [APIO2009]\u62a2\u63a0\u8ba1\u5212<\/a><\/h4>\n
#include <cstdio>\n#include <algorithm>\n#include <stack>\n#include <vector>\n#include <cstring>\nusing namespace std;\nconst int maxn = 5e5+5;\nstruct edge{\n    int from, to, next;\n}e[maxn];\nint n, m, tot, S, P;\nint head[maxn], val[maxn], isbar[maxn];\nint dfn[maxn], low[maxn], num, vis[maxn];\nstack<int> sta;\n\nvector<int> G[maxn];\nint dp[maxn];\nint getDP(int u){\n    if (dp[u]!=-1)  return dp[u];\n    int tmp = 0;\n    for (int i=0; i<G[u].size(); i++){\n        tmp = max(tmp, getDP(G[u][i]));\n    }\n    if (tmp || isbar[u])    dp[u] = val[u] + tmp;\n    else    dp[u] = 0;\n    return dp[u];\n}\n\nvoid Tarjan(int u){\n    dfn[u] = low[u] = ++num;\n    sta.push(u);    vis[u] = 1;\n    for (int i=head[u]; i; i=e[i].next){\n        if (!dfn[e[i].to]){\n            Tarjan(e[i].to);\n            low[u] = min(low[u], low[e[i].to]);\n        }else if (vis[e[i].to]) low[u] = min(low[u], dfn[e[i].to]);\n    }\n    if (low[u]==dfn[u]){\n        while (sta.top()!=u){\n            vis[sta.top()] = 0;\n            low[sta.top()] = low[u];\n            sta.pop();\n        }\n        vis[sta.top()] = 0;\n        sta.pop();\n    }\n    return;\n}\n\ninline void add(int from, int to){\n    tot++;\n    e[tot].from = from, e[tot].to = to, e[tot].next = head[from];\n    head[from] = tot;\n    return;\n}\ninline int read(){\n    int x=0;    char ch = getchar();\n    while (ch<'0' || ch>'9')    ch = getchar();\n    while (ch>='0' && ch<='9'){\n        x = x*10 + ch-'0';\n        ch = getchar();\n    }\n    return x;\n}\nint main(){\n    int from, to;\n    n = read(), m = read();\n    for (int i=1; i<=m; i++){\n        from = read(), to = read();\n        add(from, to);\n    }\n    for (int i=1; i<=n; i++)    if (!dfn[i])\n        Tarjan(i);\n    for (int i=1; i<=tot; i++)    if (low[e[i].from] != low[e[i].to]){\n        G[low[e[i].from]].push_back(low[e[i].to]);\n    }\n    for (int i=1; i<=n; i++){\n        val[low[i]] += read();\n    }\n    S = read(), P = read();\n    for (int i=1; i<=P; i++){\n        isbar[low[read()]] = 1;\n    }\n    memset(dp, -1, sizeof dp);\n    printf ("%d", getDP(low[S]));\n    return 0;\n}<\/code><\/pre>\n
P2002 \u6d88\u606f\u6269\u6563<\/a><\/h4>\n
#include <cstdio>\n#include <algorithm>\n#include <stack>\n#include <cstring>\nusing namespace std;\nconst int maxn = 5e5+5;\nstruct edge{\n    int from, to, next;\n}e[maxn];\nint n, m, tot;\nint head[maxn];\nint dfn[maxn], low[maxn], num, vis[maxn];\nint in[maxn];\nstack<int> sta;\n\nvoid Tarjan(int u){\n    dfn[u] = low[u] = ++num;\n    sta.push(u);    vis[u] = 1;\n    for (int i=head[u]; i; i=e[i].next){\n        if (!dfn[e[i].to]){\n            Tarjan(e[i].to);\n            low[u] = min(low[u], low[e[i].to]);\n        }else if (vis[e[i].to]) low[u] = min(low[u], dfn[e[i].to]);\n    }\n    if (low[u]==dfn[u]){\n        while (sta.top()!=u){\n            vis[sta.top()] = 0;\n            low[sta.top()] = low[u];\n            sta.pop();\n        }\n        vis[sta.top()] = 0;\n        sta.pop();\n    }\n    return;\n}\n\ninline void add(int from, int to){\n    tot++;\n    e[tot].from = from, e[tot].to = to, e[tot].next = head[from];\n    head[from] = tot;\n    return;\n}\ninline int read(){\n    int x=0;    char ch = getchar();\n    while (ch<'0' || ch>'9')    ch = getchar();\n    while (ch>='0' && ch<='9'){\n        x = x*10 + ch-'0';\n        ch = getchar();\n    }\n    return x;\n}\nint main(){\n    int from, to;\n    n = read(), m = read();\n    for (int i=1; i<=m; i++){\n        from = read(), to = read();\n        if (from==to)   continue;\n        add(from, to);\n    }\n    for (int i=1; i<=n; i++)    if (!dfn[i])\n        Tarjan(i);\n    int ans = 0;\n    for (int i=1; i<=n; i++)    vis[low[i]] = 1;\n    for (int i=1; i<=m; i++)    if (low[e[i].from]!=low[e[i].to]){\n        in[low[e[i].to]]++;\n    }\n    for (int i=1; i<=n; i++)    if (vis[i] && !in[i])\n        ans++;\n    printf ("%d", ans);\n    return 0;\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
\u7f29\u70b9 \u7f29\u70b9\u5c31\u662f\u628a\u6709\u5411\u56fe\u91cc\u7684\u4e00\u4e2a\u5f3a\u8fde\u901a\u5206\u91cf\u5f53\u6210\u662f\u4e00\u4e2a\u70b9\u6765\u5904\u7406\uff0c\u56e0\u4e3a\u4e00\u4e2a\u5f3a\u8fde\u901a\u5206\u91cf\u91cc\u7684\u70b9\u90fd\u53ef\u4ee5\u4e92\u76f8\u5230\u8fbe\uff0c […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[55],"tags":[],"_links":{"self":[{"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/posts\/757"}],"collection":[{"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/comments?post=757"}],"version-history":[{"count":2,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/posts\/757\/revisions"}],"predecessor-version":[{"id":760,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/posts\/757\/revisions\/760"}],"wp:attachment":[{"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/media?parent=757"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/categories?post=757"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/tags?post=757"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}