結果

問題 No.3201 Corporate Synergy
ユーザー テナガザル
提出日時 2025-07-11 22:30:34
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 3 ms / 2,000 ms
コード長 2,480 bytes
コンパイル時間 1,457 ms
コンパイル使用メモリ 113,600 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2025-07-11 22:30:37
合計ジャッジ時間 2,863 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

template<typename T>
class maxflow
{
  struct edge {int to, rep; T cap; edge(int t, int r, T c) : to(t), rep(r), cap(c) {}};
  std::vector<std::vector<edge>> g;
  std::vector<int> dis, id;
public:
  maxflow(int n) : g(n), id(n), dis(n) {}
  void add_edge(int s, int t, T f)
  {
    g[s].push_back({t, (int)g[t].size() + (s == t), f});
    g[t].push_back({s, (int)g[s].size() - 1, 0});
  }
  T flow(int s, int t)
  {
    T ret = 0;
    while (bfs(s, t))
    {
      id.assign(id.size(), 0);
      ret += path(s, t, T((1LL << 60) | (1 << 30)));
    }
    return ret;
  }
private:
  bool bfs(int s, int t)
  {
    dis.assign(g.size(), g.size());
    dis[s] = 0;
    std::queue<int> q;
    for (q.push(s); !q.empty(); q.pop())
    {
      int now = q.front();
      for (auto &v : g[now])
      {
        if (v.cap > 0 && dis[v.to] > dis[now] + 1)
        {
          dis[v.to] = dis[now] + 1;
          q.push(v.to);
        }
      }
    }
    return dis[t] < g.size();
  }
  T path(int s, int t, T lim)
  {
    if (s == t) return lim;
    T now = 0;
    for (int &i = id[t]; i < g[t].size(); ++i)
    {
      auto &e = g[t][i], &re = g[e.to][e.rep];
      if (re.cap <= 0 || dis[e.to] >= dis[t] || dis[e.to] < 0) continue;
      T tmp = path(s, e.to, std::min(lim - now, re.cap));
      if (tmp == 0) continue;
      e.cap += tmp;
      re.cap -= tmp;
      now += tmp;
      if (now >= lim) break;
    }
    return now;
  }
};

int main()
{
  int n;
  cin >> n;
  vector<int> p(n);
  long long all = 0;
  for (int i = 0; i < n; ++i) cin >> p[i];
  int m;
  cin >> m;
  vector<int> u(m), v(m);
  for (int i = 0; i < m; ++i) cin >> u[i] >> v[i];
  int k;
  cin >> k;
  maxflow<long long> mf(n + k + 2);
  int sorce = n + k, sink = sorce + 1;
  for (int i = 0; i < n; ++i)
  {
    if (p[i] > 0)
    {
        all += p[i];
        mf.add_edge(sorce, i, 0);
        mf.add_edge(i, sink, p[i]);
    }
    else
    {
        mf.add_edge(sorce, i, -p[i]);
        mf.add_edge(i, sink, 0);
    }
  }
  long long inf = 1e14;
  for (int i = 0; i < m; ++i)
  {
    --u[i], --v[i];
    mf.add_edge(u[i], v[i], inf);
  }
  for (int i = 0; i < k; ++i)
  {
    int a, b, s;
    cin >> a >> b >> s;
    all += s;
    --a, --b;
    mf.add_edge(a, i + n, inf);
    mf.add_edge(b, i + n, inf);
    mf.add_edge(i + n, sink, s);
  }
  long long ans = all - mf.flow(sorce, sink);
  cout << ans << endl;
}
0