結果
| 問題 |
No.1615 Double Down
|
| ユーザー |
 tko919
|
| 提出日時 | 2023-12-15 05:29:10 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 986 ms / 10,000 ms |
| コード長 | 13,909 bytes |
| コンパイル時間 | 3,039 ms |
| コンパイル使用メモリ | 227,904 KB |
| 最終ジャッジ日時 | 2025-02-18 11:17:35 |
|
ジャッジサーバーID （参考情報） |
judge4 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 54 |
ソースコード
#line 1 "library/Template/template.hpp"
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define ALL(v) (v).begin(),(v).end()
#define UNIQUE(v) sort(ALL(v)),(v).erase(unique(ALL(v)),(v).end())
#define SZ(v) (int)v.size()
#define MIN(v) *min_element(ALL(v))
#define MAX(v) *max_element(ALL(v))
#define LB(v,x) int(lower_bound(ALL(v),(x))-(v).begin())
#define UB(v,x) int(upper_bound(ALL(v),(x))-(v).begin())
using ll=long long int;
using ull=unsigned long long;
const int inf = 0x3fffffff;
const ll INF = 0x1fffffffffffffff;
template<typename T>inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
template<typename T>inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<typename T,typename U>T ceil(T x,U y){assert(y!=0); if(y<0)x=-x,y=-y; return (x>0?(x+y-1)/y:x/y);}
template<typename T,typename U>T floor(T x,U y){assert(y!=0); if(y<0)x=-x,y=-y; return (x>0?x/y:(x-y+1)/y);}
template<typename T>int popcnt(T x){return __builtin_popcountll(x);}
template<typename T>int topbit(T x){return (x==0?-1:63-__builtin_clzll(x));}
template<typename T>int lowbit(T x){return (x==0?-1:__builtin_ctzll(x));}
#line 2 "library/Utility/fastio.hpp"
#include <unistd.h>
class FastIO{
static constexpr int L=1<<16;
char rdbuf[L];
int rdLeft=0,rdRight=0;
inline void reload(){
int len=rdRight-rdLeft;
memmove(rdbuf,rdbuf+rdLeft,len);
rdLeft=0,rdRight=len;
rdRight+=fread(rdbuf+len,1,L-len,stdin);
}
inline bool skip(){
for(;;){
while(rdLeft!=rdRight and rdbuf[rdLeft]<=' ')rdLeft++;
if(rdLeft==rdRight){
reload();
if(rdLeft==rdRight)return false;
}
else break;
}
return true;
}
template<typename T,enable_if_t<is_integral<T>::value,int> =0>inline bool _read(T& x){
if(!skip())return false;
if(rdLeft+20>=rdRight)reload();
bool neg=false;
if(rdbuf[rdLeft]=='-'){
neg=true;
rdLeft++;
}
x=0;
while(rdbuf[rdLeft]>='0' and rdLeft<rdRight){
x=x*10+(neg?-(rdbuf[rdLeft++]^48):(rdbuf[rdLeft++]^48));
}
return true;
}
inline bool _read(__int128_t& x){
if(!skip())return false;
if(rdLeft+40>=rdRight)reload();
bool neg=false;
if(rdbuf[rdLeft]=='-'){
neg=true;
rdLeft++;
}
x=0;
while(rdbuf[rdLeft]>='0' and rdLeft<rdRight){
x=x*10+(neg?-(rdbuf[rdLeft++]^48):(rdbuf[rdLeft++]^48));
}
return true;
}
inline bool _read(__uint128_t& x){
if(!skip())return false;
if(rdLeft+40>=rdRight)reload();
x=0;
while(rdbuf[rdLeft]>='0' and rdLeft<rdRight){
x=x*10+(rdbuf[rdLeft++]^48);
}
return true;
}
template<typename T,enable_if_t<is_floating_point<T>::value,int> =0>inline bool _read(T& x){
if(!skip())return false;
if(rdLeft+20>=rdRight)reload();
bool neg=false;
if(rdbuf[rdLeft]=='-'){
neg=true;
rdLeft++;
}
x=0;
while(rdbuf[rdLeft]>='0' and rdbuf[rdLeft]<='9' and rdLeft<rdRight){
x=x*10+(rdbuf[rdLeft++]^48);
}
if(rdbuf[rdLeft]!='.')return true;
rdLeft++;
T base=.1;
while(rdbuf[rdLeft]>='0' and rdbuf[rdLeft]<='9' and rdLeft<rdRight){
x+=base*(rdbuf[rdLeft++]^48);
base*=.1;
}
if(neg)x=-x;
return true;
}
inline bool _read(char& x){
if(!skip())return false;
if(rdLeft+1>=rdRight)reload();
x=rdbuf[rdLeft++];
return true;
}
inline bool _read(string& x){
if(!skip())return false;
for(;;){
int pos=rdLeft;
while(pos<rdRight and rdbuf[pos]>' ')pos++;
x.append(rdbuf+rdLeft,pos-rdLeft);
if(rdLeft==pos)break;
rdLeft=pos;
if(rdLeft==rdRight)reload();
else break;
}
return true;
}
template<typename T>inline bool _read(vector<T>& v){
for(auto& x:v){
if(!_read(x))return false;
}
return true;
}
char wtbuf[L],tmp[50];
int wtRight=0;
inline void _write(const char& x){
if(wtRight>L-32)flush();
wtbuf[wtRight++]=x;
}
inline void _write(const string& x){
for(auto& c:x)_write(c);
}
template<typename T,enable_if_t<is_integral<T>::value,int> =0>inline void _write(T x){
if(wtRight>L-32)flush();
if(x==0){
_write('0');
return;
}
else if(x<0){
_write('-');
if (__builtin_expect(x == std::numeric_limits<T>::min(), 0)) {
switch (sizeof(x)) {
case 2: _write("32768"); return;
case 4: _write("2147483648"); return;
case 8: _write("9223372036854775808"); return;
}
}
x=-x;
}
int pos=0;
while(x!=0){
tmp[pos++]=char((x%10)|48);
x/=10;
}
rep(i,0,pos)wtbuf[wtRight+i]=tmp[pos-1-i];
wtRight+=pos;
}
inline void _write(__int128_t x){
if(wtRight>L-40)flush();
if(x==0){
_write('0');
return;
}
else if(x<0){
_write('-');
x=-x;
}
int pos=0;
while(x!=0){
tmp[pos++]=char((x%10)|48);
x/=10;
}
rep(i,0,pos)wtbuf[wtRight+i]=tmp[pos-1-i];
wtRight+=pos;
}
inline void _write(__uint128_t x){
if(wtRight>L-40)flush();
if(x==0){
_write('0');
return;
}
int pos=0;
while(x!=0){
tmp[pos++]=char((x%10)|48);
x/=10;
}
rep(i,0,pos)wtbuf[wtRight+i]=tmp[pos-1-i];
wtRight+=pos;
}
inline void _write(double x){
ostringstream oss;
oss << fixed << setprecision(15) << double(x);
string s = oss.str();
_write(s);
}
template<typename T>inline void _write(const vector<T>& v){
rep(i,0,v.size()){
if(i)_write(' ');
_write(v[i]);
}
}
public:
FastIO(){}
~FastIO(){flush();}
inline void read(){}
template <typename Head, typename... Tail>inline void read(Head& head,Tail&... tail){
assert(_read(head));
read(tail...);
}
template<bool ln=true,bool space=false>inline void write(){if(ln)_write('\n');}
template <bool ln=true,bool space=false,typename Head, typename... Tail>inline void write(const Head& head,const Tail&... tail){
_write(head);
write<ln,true>(tail...);
if(space)_write(' ');
}
inline void flush(){
fwrite(wtbuf,1,wtRight,stdout);
wtRight=0;
}
};
/**
* @brief Fast IO
*/
#line 3 "sol.cpp"
#line 2 "library/Graph/maxflow.hpp"
struct MaxFlow {
struct Edge {
int to, rev;
ll cap;
};
int V;
vector<vector<Edge>> G;
vector<int> itr, level;
using P = pair<int, int>;
vector<P> es;
public:
MaxFlow() {}
MaxFlow(int V) : V(V) { G.assign(V, vector<Edge>()); }
int add_vertex() {
G.push_back(vector<Edge>());
return V++;
}
void add_edge(int from, int to, ll cap) {
es.push_back({from, (int)G[from].size()});
G[from].push_back({to, (int)G[to].size(), cap});
G[to].push_back({from, (int)G[from].size() - 1, 0});
}
struct Type {
int from, to;
ll cap, recap;
};
Type get_edge(int i) {
auto [from, pos] = es[i];
auto e = G[from][pos];
auto re = G[e.to][e.rev];
return Type{from, e.to, e.cap, re.cap};
}
void bfs(int s) {
level.assign(V, -1);
queue<int> q;
level[s] = 0;
q.push(s);
while (!q.empty()) {
int v = q.front();
q.pop();
for (auto &e : G[v]) {
if (e.cap > 0 && level[e.to] < 0) {
level[e.to] = level[v] + 1;
q.push(e.to);
}
}
}
}
ll dfs(int v, int t, ll f) {
if (v == t)
return f;
for (int &i = itr[v]; i < (int)G[v].size(); i++) {
Edge &e = G[v][i];
if (e.cap > 0 && level[v] < level[e.to]) {
ll d = dfs(e.to, t, min(f, e.cap));
if (d > 0) {
e.cap -= d, G[e.to][e.rev].cap += d;
return d;
}
}
}
return 0;
}
ll run(int s, int t) {
ll ret = 0, f;
while (bfs(s), level[t] >= 0) {
itr.assign(V, 0);
while ((f = dfs(s, t, INF)) > 0)
ret += f;
}
return ret;
}
};
/**
* @brief Maximum Flow
*/
#line 5 "sol.cpp"
// yosupo orz
template <class Cap, class Cost> struct MinCostFlow {
struct X {
int from, to;
Cap lb, ub, flow;
Cost cost;
};
struct Edge {
int to, rev;
Cap cap;
Cost cost;
};
using P = pair<int, int>;
int n, m;
vector<X> es;
vector<Cap> exc;
vector<Cost> dual;
vector<vector<Edge>> g;
Cost MX;
MinCostFlow(int _n) : n(_n), m(0), exc(n), dual(n), g(n), MX(0) {}
void add_edge(int from, int to, Cap lb, Cap ub, Cost cost) {
m++;
chmax(MX, cost);
chmax(MX, -cost);
es.push_back({from, to, lb, ub, 0, cost});
}
void add_excess(int v, Cap c) { exc[v] += c; }
pair<bool, Cost> run() {
MaxFlow mf(n + 2);
int S = n, T = n + 1;
Cap psum = 0, nsum = 0;
rep(i, 0, n) {
if (exc[i] > 0) {
psum += exc[i];
mf.add_edge(S, i, exc[i]);
}
if (exc[i] < 0) {
nsum += -exc[i];
mf.add_edge(i, T, -exc[i]);
}
}
for (auto &e : es) {
exc[e.to] += e.lb;
exc[e.from] -= e.lb;
mf.add_edge(e.from, e.to, e.ub - e.lb);
}
if (psum != nsum or mf.run(S, T) != psum)
return {false, 0};
using P = pair<int, int>;
vector<P> pos;
rep(i, 0, m) {
auto e = mf.get_edge(i);
Cost cost = es[i].cost * n;
int fid = SZ(g[e.from]), tid = SZ(g[e.to]);
if (e.from == e.to)
tid++;
pos.push_back({e.from, fid});
g[e.from].push_back({e.to, tid, e.cap, cost});
g[e.to].push_back({e.from, fid, e.recap, -cost});
}
// solve
Cost eps = MX * n + 1;
while (eps > 1) {
eps = max<Cost>(eps >> 2, 1);
refine(eps);
}
Cost ret = 0;
rep(i, 0, m) {
auto [from, fid] = pos[i];
es[i].flow = es[i].ub - g[from][fid].cap;
ret += es[i].flow * es[i].cost;
}
for (;;) {
bool upd = 0;
rep(i, 0, n) {
for (auto &e : g[i])
if (e.cap) {
auto cost = dual[i] + e.cost / n;
if (chmin(dual[e.to], cost)) {
upd = 1;
}
}
}
if (!upd)
break;
}
return {true, ret};
}
private:
void refine(Cost &eps) {
vector<bool> used(n);
queue<int> que;
vector<int> iter(n);
auto cost = [&](int from, const Edge &e) {
return e.cost + dual[from] - dual[e.to];
};
auto push = [&](int from, Edge &e, Cap cap) {
exc[from] -= cap;
exc[e.to] += cap;
g[e.to][e.rev].cap += cap;
e.cap -= cap;
};
auto relabel = [&](int v) {
iter[v] = 0;
Cost down = MX * (n + 1);
for (auto &e : g[v])
if (e.cap) {
chmin(down, eps + cost(v, e));
}
dual[v] -= down;
que.push(v);
used[v] = 1;
};
rep(i, 0, n) {
for (auto &e : g[i])
if (e.cap and cost(i, e) < 0) {
push(i, e, e.cap);
}
}
rep(i, 0, n) if (exc[i] > 0) {
used[i] = 1;
que.push(i);
}
while (!que.empty()) {
auto v = que.front();
que.pop();
used[v] = 0;
for (int &i = iter[v]; i < SZ(g[v]); i++) {
auto &e = g[v][i];
if (e.cap and cost(v, e) < 0) {
push(v, e, min(exc[v], e.cap));
if (!used[e.to] and exc[e.to] > 0) {
used[e.to] = 1;
que.push(e.to);
}
if (exc[v] == 0)
break;
}
}
if (exc[v] > 0)
relabel(v);
}
eps = 0;
rep(i, 0, n) {
for (auto &e : g[i])
if (e.cap) {
chmax(eps, -cost(i, e));
}
}
}
};
FastIO io;
int main() {
int n, m, k, L;
io.read(n, m, k, L);
vector<int> x(L), y(L), z(L);
rep(i, 0, L) { io.read(x[i], y[i], z[i]); }
MinCostFlow<ll, ll> buf(n + m + 1);
int S = n + m;
rep(i, 0, n) { buf.add_edge(S, i, 0, 1, 0); }
rep(i, 0, m) { buf.add_edge(n + i, S, 0, 1, 0); }
rep(i, 0, L) { buf.add_edge(x[i] - 1, y[i] - 1 + n, 0, 1, -(1 << z[i])); }
auto [_, ret] = buf.run();
io.write(-ret);
return 0;
}