题目

传送门

题解

第一次一遍就AC一道bzoj上的题，虽然是一道水题。。。

我们做一边最短路，求出每个点的dist，然后再做一次类似spfa的操作，求出每个点是否可以用于建图。

在新图上拆点跑一边dinic就好辣。

代码

#include <algorithm>

#include <cstdio>

#include <cstring>

#include <queue>

#include <vector>

using namespace std;

#define ll long long

const ll inf = 100000000000;

const int maxn = 1000;

struct edge {

  int from;

  int to;

  ll value;

};

vector<edge> edges;

vector<int> G[maxn];

vector<edge> gg[maxn];

void add(int from, int to, ll value) {

  gg[from].push_back((edge){from, to, value});

}

void add_edge(int from, int to, ll value) {

  edges.push_back((edge){from, to, value});

  edges.push_back((edge){to, from, 0});

  int m = edges.size();

  G[from].push_back(m - 2);

  G[to].push_back(m - 1);

}

ll dist[maxn];

int iter[maxn];

int n, m;

ll c[maxn];

int st, t;

void spfa(int s) {

  for (int i = 1; i <= n; i++)

    dist[i] = inf;

  queue<int> q;

  bool inq[maxn];

  memset(inq, 0, sizeof(inq));

  q.push(s);

  dist[s] = 0;

  inq[s] = 1;

  while (!q.empty()) {

    int u = q.front();

    q.pop();

    inq[u] = 0;

    for (int i = 0; i < gg[u].size(); i++) {

      edge &e = gg[u][i];

      if (dist[e.to] > dist[u] + e.value) {

        dist[e.to] = dist[u] + e.value;

        if (!inq[e.to]) {

          q.push(e.to);

          inq[e.to] = 1;

        }

      }

    }

  }

}

void build_graph(int s, int e) {

  queue<int> q;

  q.push(s);

  bool inq[maxn];

  memset(inq, 0, sizeof(inq));

  inq[s] = 1;

  int vis[maxn];

  memset(vis, 0, sizeof(vis));

  vis[s] = 1;

  add_edge(st, s, inf);

  add_edge(e + n, t, inf);

  add_edge(s, s + n, inf);

  add_edge(e, e + n, inf);

  while (!q.empty()) {

    int u = q.front();

    q.pop();

    inq[u] = 0;

    for (int i = 0; i < gg[u].size(); i++) {

      edge &ee = gg[u][i];

      if (dist[ee.to] == dist[u] + ee.value) {

        add_edge(u + n, ee.to, inf);

        if (!vis[ee.to] && ee.to != e) {

          add_edge(ee.to, ee.to + n, c[ee.to]);

          vis[ee.to] = 1;

        }

        if (!inq[ee.to]) {

          q.push(ee.to);

          inq[ee.to] = 1;

        }

      }

    }

  }

}

void bfs(int s) {

  memset(dist, -1, sizeof(dist));

  dist[s] = 0;

  queue<int> q;

  q.push(s);

  while (!q.empty()) {

    int u = q.front();

    q.pop();

    for (int i = 0; i < G[u].size(); i++) {

      edge &e = edges[G[u][i]];

      if (e.value > 0 && dist[e.to] == -1) {

        dist[e.to] = dist[u] + 1;

        q.push(e.to);

      }

    }

  }

}

ll dfs(int s, int t, ll flow) {

  if (s == t)

    return flow;

  for (int &i = iter[s]; i < G[s].size(); i++) {

    edge &e = edges[G[s][i]];

    if (dist[e.to] > dist[s] && e.value > 0) {

      int d = dfs(e.to, t, min(flow, e.value));

      if (d > 0) {

        e.value -= d;

        edges[G[s][i] ^ 1].value += d;

        return d;

      }

    }

  }

  return 0;

}

ll dinic(int s, int t) {

  ll flow = 0;

  while (1) {

    bfs(s);

    if (dist[t] == -1)

      return flow;

    memset(iter, 0, sizeof(iter));

    ll d;

    while (d = dfs(s, t, inf))

      flow += d;

  }

}

int main() {

  //  freopen("input", "r", stdin);

  scanf("%d %d", &n, &m);

  for (int i = 1; i <= m; i++) {

    int x, y;

    ll z;

    scanf("%d %d %lld", &x, &y, &z);

    add(x, y, z);

    add(y, x, z);

  }

  for (int i = 1; i <= n; i++)

    scanf("%lld", &c[i]);

  spfa(1);

  st = 0, t = n + n + 1;

  build_graph(1, n);

  ll ans = dinic(st, t);

  printf("%lld\n", ans);

}

Excited！