結果

問題 No.2320 Game World for PvP
ユーザー srjywrdnprktsrjywrdnprkt
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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-jC_{ij}ijC_{ij}
sourseEsinkRE_iSinf
*/
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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0