結果

問題 No.3201 Corporate Synergy
ユーザー tnakao0123
提出日時 2025-07-12 13:56:58
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 3,869 bytes
コンパイル時間 1,180 ms
コンパイル使用メモリ 80,128 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2025-07-12 13:57:00
合計ジャッジ時間 2,208 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 13 WA * 7
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:136:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  136 |   scanf("%d", &n);
      |   ~~~~~^~~~~~~~~~
main.cpp:137:36: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  137 |   for (int i = 0; i < n; i++) scanf("%d", ps + i);
      |                               ~~~~~^~~~~~~~~~~~~~
main.cpp:140:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  140 |   scanf("%d", &m);
      |   ~~~~~^~~~~~~~~~
main.cpp:143:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  143 |     scanf("%d%d", &u, &v);
      |     ~~~~~^~~~~~~~~~~~~~~~
main.cpp:149:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  149 |   scanf("%d", &k);
      |   ~~~~~^~~~~~~~~~
main.cpp:152:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  152 |     scanf("%d%d%d", &u, &v, &s);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~

ソースコード

diff # 

/* -*- coding: utf-8 -*-
 *
 * 3201.cc:  No.3201 Corporate Synergy - yukicoder
 */

#include<cstdio>
#include<vector>
#include<queue>
#include<algorithm>
#include<utility>
#include<tuple>

using namespace std;

/* constant */

const int MAX_N = 200;
const int MAX_M = 200;
const int MAX_K = 200;
const int MAX_GN = MAX_N + MAX_K + 2;
const long long LINF = 1LL << 60;

/* typedef */

using ll = long long;
using vi = vector<int>;
using pii = pair<int,int>;
using tp3 = tuple<int,int,int>;
using qi = queue<int>;

template <typename T>
struct MaxFlow {
  using pii = pair<int,int>;
  using vpii = vector<pii>;
  using vvpii = vector<vpii>;
  using qi = queue<int>;

  int n, m;
  vvpii nbrs;
  T inf, max_flow;
  vpii prvs;
  vector<T> minfs, caps, flows;

  MaxFlow(int _n, T _inf): n(_n), m(0), inf(_inf) {
    nbrs.assign(n, vpii());
    minfs.assign(n, 0);
    prvs.assign(n, {-1, -1});
    caps.clear(), flows.clear();
    max_flow = 0;
  }

  int addedges(int u, int v, T c) {
    // edge[m]: u -> v, cap=c
    nbrs[u].push_back({v, m});
    caps.push_back(c); flows.push_back(0);

    // edge[m + 1]: v -> u, cap=0
    nbrs[v].push_back({u, m + 1});
    caps.push_back(0); flows.push_back(0);

    m += 2;
    return m;
  }
  
  T flow(int st, int gl, bool cont = false) {
    if (! cont) {
      fill(flows.begin(), flows.end(), 0);
      max_flow = 0;
    }

    for (;;) {
      //printf("max_flow = %d, limit = %d\n", max_flow, limit);

      fill(prvs.begin(), prvs.end(), pii(-1, -1));
      prvs[st] = {st, -1};
      minfs[st] = inf;

      qi q;
      q.push(st);

      while (! q.empty()) {
	int u = q.front(); q.pop();
	if (u == gl) break;

	for (auto [v, ei]: nbrs[u]) {
	  T vc = caps[ei] - flows[ei];
	  if (prvs[v].first < 0 && vc > 0) {
	    prvs[v] = {u, ei};
	    minfs[v] = (minfs[u] < vc) ? minfs[u] : vc;
	    q.push(v);
	  }
	}
      }
      if (prvs[gl].first < 0) break;

      T min_flow = minfs[gl];
      for (int j = gl; j != st;) {
	auto [i, ei] = prvs[j];
	flows[ei] += min_flow;
	flows[ei ^ 1] -= min_flow;
	j = i;
      }
      max_flow += min_flow;
    }

    return max_flow;
  }
};

/*
int main() {
  const int INF = 1 << 30;
  MaxFlow<int> mf(3, INF);
  mf.addedges(0, 1, 1);
  mf.addedges(1, 2, 3);
  mf.addedges(0, 2, 1);
  int f = mf.flow(0, 2);
  printf("f=%d\n", f);
  return 0;
}
*/

/* global variables */

int ps[MAX_N];
pii es[MAX_M];
tp3 sgs[MAX_K];
bool used[MAX_GN];

/* subroutines */

/* main */

int main() {
  int n;
  scanf("%d", &n);
  for (int i = 0; i < n; i++) scanf("%d", ps + i);

  int m;
  scanf("%d", &m);
  for (int i = 0; i < m; i++) {
    int u, v;
    scanf("%d%d", &u, &v);
    u--, v--;
    es[i] = {u, v};
  }

  int k;
  scanf("%d", &k);
  for (int i = 0; i < k; i++) {
    int u, v, s;
    scanf("%d%d%d", &u, &v, &s);
    u--, v--;
    sgs[i] = {u, v, s};
  }

  int st = n + k, gl = st + 1, gn = gl + 1;
  MaxFlow<ll> mf(gn, LINF);

  for (int u = 0; u < n; u++) {
    if (ps[u] > 0)
      mf.addedges(st, u, ps[u]);
    else if (ps[u] < 0) {
      mf.addedges(u, gl, -ps[u]);
    }
  }

  for (int i = 0; i < m; i++) {
    auto [u, v] = es[i];
    mf.addedges(v, u, LINF);
  }

  for (int i = 0; i < k; i++) {
    auto [u, v, s] = sgs[i];
    int w = n + i;
    mf.addedges(st, w, s);
    mf.addedges(w, u, LINF);
    mf.addedges(w, v, LINF);
  }

  ll f = mf.flow(st, gl);
  //printf(" f=%lld\n", f);

  used[st] = true;
  qi q;
  q.push(st);

  while (! q.empty()) {
    int u = q.front(); q.pop();
    if (u == gl) continue;
    for (auto [v, ei]: mf.nbrs[u])
      if (! used[v] && mf.caps[ei] > 0 && mf.flows[ei] < mf.caps[ei])
	used[v] = true, q.push(v);
  }

  ll sum = 0;
  for (int u = 0; u < n; u++)
    if (used[u]) sum += ps[u];

  for (int i = 0; i < k; i++) {
    auto [u, v, s] = sgs[i];
    if (used[u] && used[v]) sum += s;
  }

  printf("%lld\n", sum);
  
  return 0;
}
0