Submission #33655383

---

Source Code Expand

#include <bits/stdc++.h>
#include <atcoder/scc>
#include <atcoder/mincostflow>
using namespace std;

typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
#define per(i,a,n) for (ll i=n;i-->(ll)a;)
#define pb push_back

ll read(){ll r;scanf("%lld",&r);return r;} // read

int main() {
  int N = read();
  int M = read();
  int K = read();
  vector<int> A(M), B(M);
  atcoder::scc_graph graph(N); // 0-index 点
  rep(i,0,M){
    A[i] = read() - 1; // 0-index
    B[i] = read() - 1;
    graph.add_edge(A[i], B[i]);
  }
  const vector<vector<int>> scc = graph.scc(); // 连通块
  const int V = scc.size(); // DAG节点个数
  vector<int> belongs(N); // [节点] = 所在块
  rep(i,0,V) for(int u : scc[i]) belongs[u] = i;
  vector<ll> X(V); // 新图每个点上的 值
  rep(i,0,N){
    int x = read();
    X[belongs[i]] += x;
  }
  vector<ll> accum(V + 1, 0); // 前缀和
  rep(i,0,V) accum[i + 1] = accum[i] + X[i];

  atcoder::mcf_graph<int, ll> network(2 * V + 1); // in[1]变成 S
  int S = 2*belongs[0];
  int T = 2*V;
  rep(i,0,V) {
    network.add_edge(2 * i, 2 * i + 1, 1, 0); // in[i] -> out[i], 容量1, 费用 -X[i] + X[i]
    network.add_edge(2 * i, 2 * i + 1, K, X[i]); // in[i] -> out[i], 容量K(无穷), 费用 0 + X[i]
    network.add_edge(2 * i + 1, 2 * V, K, accum[V] - accum[i + 1]); // out[i] -> T 费用 0 + All - X[0..i]
  }
  rep(i,0,M) {
    int u = belongs[A[i]];
    int v = belongs[B[i]];
    // assert(accum[v] - accum[u + 1]); 保证不了啊 如果是拓扑则可以
    if (u != v) network.add_edge(2 * u + 1, 2 * v, K, accum[v] - accum[u + 1]); // out[u] -> in[v] , 容量k, 费用 0 + X[0..v] - X[0..u]
  }
  auto [maxflow, mincost] = network.flow(S,T,K);
  printf("%lld\n",(accum[V] - accum[belongs[0]]) * K - mincost);
}

Submission Info

Compile Error

./Main.cpp: In function ‘ll read()’:
./Main.cpp:11:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   11 | ll read(){ll r;scanf("%lld",&r);return r;} // read
      |                ~~~~~^~~~~~~~~~~

Judge Result