{"id":795,"date":"2020-08-15T13:25:03","date_gmt":"2020-08-15T05:25:03","guid":{"rendered":"http:\/\/www.zyhcoding.club\/?p=795"},"modified":"2020-08-15T13:28:47","modified_gmt":"2020-08-15T05:28:47","slug":"hdu3416-%e7%bd%91%e7%bb%9c%e6%b5%81%e6%9c%80%e7%9f%ad%e8%b7%af","status":"publish","type":"post","link":"http:\/\/www.zyhcoding.club\/index.php\/2020\/08\/15\/hdu3416-%e7%bd%91%e7%bb%9c%e6%b5%81%e6%9c%80%e7%9f%ad%e8%b7%af\/","title":{"rendered":"HDU3416 \u7f51\u7edc\u6d41+\u6700\u77ed\u8def"},"content":{"rendered":"<h4><a href=\"http:\/\/acm.hdu.edu.cn\/showproblem.php?pid=3416\">HDU3416 Marriage Match IV<\/a><\/h4>\n<p>\u7ed9\u4e00\u4e2a\u5e26\u6743\u6709\u5411\u56fe\uff0c\u4e24\u4e2a\u70b9AB\uff0c\u6c42A\u5230B\u6709\u51e0\u6761\u6700\u77ed\u8def\uff0c\u6bcf\u6761\u8fb9\u53ea\u80fd\u8d70\u4ee5\u6b21\uff01<br \/>\n\u5148\u8dd1\u4e24\u8fb9Dij\uff0c\u6c42\u51faA\u5230\u5404\u4e2a\u70b9\u7684\u6700\u77ed\u8def\u548c\u5404\u4e2a\u70b9\u5230B\u7684\u6700\u77ed\u8def\uff0c\u540e\u8005\u662f\u5148\u53cd\u5411\u5efa\u8fb9\u5728\u8dd1Dij\u5c31\u884c\uff0c\u7136\u540e\u679a\u4e3e\u8fb9\uff0c\u82e5\u6ee1\u8db3dist1[from]+e[i].weight+dist[to] == dist1[B]\uff0c\u5219\u8bf4\u660e\u6240\u6709\u7684\u6700\u77ed\u8def\u4e2d\u5305\u542b\u6b64\u6761\u8fb9\uff0c\u627e\u5230\u6240\u6709\u7684\u8fd9\u6837\u7684\u8fb9\uff0c\u7136\u540e\u5728\u8fd9\u4e9b\u8fb9\u4e0a\u8dd1\u7f51\u7edc\u6d41\uff0c\u6bcf\u6761\u8fb9\u7684\u6d41\u91cf\u8bbe\u7f6e\u4e3a1\uff0c\u6700\u540e\u8dd1\u51fa\u6765\u7684\u7ed3\u679c\u5c31\u662f\u7b54\u6848\u3002<\/p>\n<pre><code class=\"language-c++\">#include &lt;cstdio&gt;\n#include &lt;cstring&gt;\n#include &lt;queue&gt;\n#include &lt;vector&gt;\nusing namespace std;\nconst int maxn = 1005, maxm = 1e5+5;\nstruct node{\n    int pos, dist;\n    node(int a, int b): pos(a), dist(b){}\n    friend bool operator &lt; (const struct node &amp;a, const struct node &amp;b){\n        return a.dist &gt; b.dist;\n    }\n};\nstruct edge{\n    int from, to, dist, next;\n}e[maxm*2];\nint n, m, tot, A, B;\nint head[maxn], vis[maxn], dist1[maxn], dist2[maxn];\n\nstruct Edge{\n    int from, to, c, f;\n    Edge(int a, int b, int e, int d): from(a), to(b), c(e), f(d){}\n};\n\nint cnt, depth[maxn], cur[maxn];\nvector&lt;Edge&gt; E;\nvector&lt;int&gt; G[maxn];\n\ninline bool BFS(int s, int t){\n    for (int i=1; i&lt;=n; i++)    depth[i] = 0;\n    depth[s] = 1;\n    queue&lt;int&gt; q;\n    q.push(s);\n    while (!q.empty()){\n        int tmp = q.front();    q.pop();\n        for (int i=0; i&lt;G[tmp].size(); i++){\n            Edge&amp; e = E[G[tmp][i]];\n            if (e.c&gt;e.f &amp;&amp; !depth[e.to]){\n                depth[e.to] = depth[tmp] + 1;\n                q.push(e.to);\n            }\n        }\n    }\n    return depth[t];\n}\n\ninline int DFS(int s, int t, int flow){\n    if (s==t || flow&lt;=0)    return flow;\n    int rest = flow;\n    for (int &amp;i=cur[s]; i&lt;G[s].size(); i++)  if (depth[E[G[s][i]].to]==depth[s]+1 &amp;&amp; E[G[s][i]].c&gt;E[G[s][i]].f){\n        int tmp = DFS(E[G[s][i]].to, t, min(rest, E[G[s][i]].c-E[G[s][i]].f));\n        if (tmp&lt;=0) depth[E[G[s][i]].to] = 0;\n        rest -= tmp;\n        E[G[s][i]].f += tmp;\n        E[G[s][i]^1].f -= tmp;\n        if (rest==0)    break;\n    }\n    return flow - rest;\n}\n\nint DINIC(int s, int t){\n    int ans = 0;\n    while (BFS(s, t)){\n        ans += DFS(s, t, 9999999);\n        for (int i=1; i&lt;=n; i++)    cur[i] = 0;\n    }\n    return ans;\n}\n\ninline void Add(int from, int to, int cap){\n    E.push_back(Edge(from, to, cap, 0));\n    E.push_back(Edge(to, from, 0, 0));\n    cnt += 2;\n    G[from].push_back(cnt-2);\n    G[to].push_back(cnt-1);\n    return;\n}\n\nvoid Dijkstra(int s, int dist[]){\n    for (int i=1; i&lt;=n; i++)    vis[i] = 0, dist[i] = 999999999;\n    priority_queue&lt;node&gt; q;\n    dist[s] = 0;\n    q.push(node(s, 0));\n    while (!q.empty()){\n        node tmp = q.top();    q.pop();\n        if (vis[tmp.pos])   continue;\n        vis[tmp.pos] = 1;\n        for (int i=head[tmp.pos]; i; i=e[i].next)   if (dist[e[i].to] &gt; tmp.dist+e[i].dist){\n            dist[e[i].to] = tmp.dist+e[i].dist;\n            q.push(node(e[i].to, dist[e[i].to]));\n        }\n    }\n    return;\n}\n\ninline void add(int from, int to, int dist){\n    tot++;\n    e[tot].from = from, e[tot].to = to, e[tot].dist = dist, 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&lt;&#039;0&#039; || ch&gt;&#039;9&#039;)    ch=getchar();\n    while (ch&gt;=&#039;0&#039; &amp;&amp; ch&lt;=&#039;9&#039;){\n        x = x*10 + ch-&#039;0&#039;;\n        ch=getchar();\n    }\n    return x;\n}\n\nint main(){\n    int t = read(), from, to, w;\n    while (t--){\n        n = read(), m = read(), tot = cnt = 0;\n        for (int i=1; i&lt;=n; i++)    head[i] = 0;\n        E.clear();\n        for (int i=1; i&lt;=n; i++)    G[i].clear();\n        for (int i=1; i&lt;=m; i++){\n            from = read(), to = read(), w = read();\n            add(from, to, w);\n        }\n        A = read(), B = read();\n        Dijkstra(A, dist1);\n        for (int j=1; j&lt;=2; j++){\n            for (int i=1; i&lt;=n; i++)    head[i] = 0;\n            for (int i=1; i&lt;=tot; i++){\n                int tmp = e[i].from;\n                e[i].from = e[i].to;\n                e[i].to = tmp;\n                e[i].next = head[e[i].from];\n                head[e[i].from] = i;\n            }\n            if (j==1)   Dijkstra(B, dist2);\n        }\n        for (int i=1; i&lt;=tot; i++)  if (dist1[e[i].from]+e[i].dist+dist2[e[i].to] == dist1[B]){\n            Add(e[i].from, e[i].to, 1);\n        }\n        printf (&quot;%d\\n&quot;, DINIC(A, B));\n    }\n    return 0;\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"<p>HDU3416 Marriage Match IV \u7ed9\u4e00\u4e2a\u5e26\u6743\u6709\u5411\u56fe\uff0c\u4e24\u4e2a\u70b9AB\uff0c\u6c42A\u5230B\u6709\u51e0\u6761\u6700\u77ed [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[59],"tags":[],"_links":{"self":[{"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/posts\/795"}],"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=795"}],"version-history":[{"count":2,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/posts\/795\/revisions"}],"predecessor-version":[{"id":797,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/posts\/795\/revisions\/797"}],"wp:attachment":[{"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/media?parent=795"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/categories?post=795"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/tags?post=795"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}