結果
問題 | No.2320 Game World for PvP |
ユーザー |
![]() |
提出日時 | 2024-11-06 21:44:10 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 4 ms / 2,000 ms |
コード長 | 4,041 bytes |
コンパイル時間 | 2,979 ms |
コンパイル使用メモリ | 220,696 KB |
実行使用メモリ | 6,824 KB |
最終ジャッジ日時 | 2024-11-06 21:44:16 |
合計ジャッジ時間 | 4,177 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 30 |
ソースコード
#include <bits/stdc++.h>using namespace std;using ll = long long;struct edge{int to; ll cap; int rev;};//Dinic(0-indexed)struct MaxFlow{private:static const ll INF=9e18;vector<int> dist, iter;vector<pair<int, int>> idx;void bfs(int s){int from;fill(dist.begin(), dist.end(), -1);queue<int> que;que.push(s);dist[s] = 0;while(!que.empty()){from = que.front(); que.pop();for (auto &e : E[from]){if (e.cap > 0 && dist[e.to] == -1){dist[e.to] = dist[from] + 1;que.push(e.to);}}}}ll dfs(int s, int t, ll flow){if (s == t) return flow;for (int &i=iter[s]; i<E[s].size(); i++){edge &e = E[s][i];if (e.cap <= 0 || dist[s] >= dist[e.to]) continue;ll d = dfs(e.to, t, min(flow, e.cap));if (d > 0){e.cap -= d;E[e.to][e.rev].cap += d;return d;}}return 0;}public:int N, M=0;vector<vector<edge>> E;MaxFlow(int n) : N(n) {E.resize(N);dist.resize(N);iter.resize(N);}void add_edge(int from, int to, ll cap){M++;idx.push_back({from, (int)E[from].size()});E[from].push_back({to, cap, (int)E[to].size()});E[to].push_back({from, 0, (int)E[from].size()-1});}ll solve(int s, int t, ll limit=INF){ll res = 0, flow;while(1){bfs(s);if (dist[t] == -1) break;for (int i=0; i<N; i++) iter[i] = 0;while((flow = dfs(s, t, INF)) > 0){res += flow;if (res >= limit) return limit;}}return res;}//i番目の辺の(from, to, flow)を求める。tuple<int, int, ll> get_flow(int i){assert (i < M);edge &e = E[idx[i].first][idx[i].second];return {idx[i].first, e.to, E[e.to][e.rev].cap};}//最小カット(s->t)を求めるvector<tuple<int, int, ll>> get_cut(int s){vector<bool> vst(N);vector<tuple<int, int, ll>> res;auto dfs=[&](auto self, int from)->void{vst[from] = 1;for (auto &e : E[from]){if (vst[e.to]) continue;if (e.cap) self(self, e.to);}};dfs(dfs, s);for (int i=0; i<M; i++){edge &e = E[idx[i].first][idx[i].second];if (vst[idx[i].first] && !vst[e.to]) res.push_back({idx[i].first, e.to, E[e.to][e.rev].cap});}return res;}};int main(){cin.tie(nullptr);ios_base::sync_with_stdio(false);/*燃やす埋める問題あらかじめ全部もらっておく。i-jにC_{ij}のコストの辺を張ると、iとjが異なる成分に属する時C_{ij}の損失が発生sourseをE側、sinkをR側にするとき、E_iとSが異なる連結成分に属してはいけないのでinfのコストの辺を張る。逆も同様*/ll N, S, T, C, x, sm=0;cin >> N >> S >> T;MaxFlow mf(N+2);for (int i=0; i<S; i++){cin >> x;mf.add_edge(0, x, 1e18);}for (int i=0; i<T; i++){cin >> x;mf.add_edge(x, N+1, 1e18);}for (int i=1; i<=N; i++){for (int j=1; j<=N; j++){cin >> C;mf.add_edge(i, j, C);if (i>j) sm += C;}}cout << sm - mf.solve(0, N+1) << endl;return 0;}