#754670 (C++14) No.1615 Double Down

提出ソース

結果

問題	No.1615 Double Down
ユーザー	Jaehyun Koo
提出日時	2022-04-17 01:39:25
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	TLE
実行時間	-
コード長	7,494 bytes
コンパイル時間	2,225 ms
コンパイル使用メモリ	185,352 KB
実行使用メモリ	24,192 KB
最終ジャッジ日時	2024-06-07 17:43:55
合計ジャッジ時間	26,666 ms
ジャッジサーバーID （参考情報）	judge3 / judge4

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	3,533 ms 24,192 KB
testcase_01	AC	4,693 ms 11,084 KB
testcase_02	TLE	-
testcase_03	--	-
testcase_04	--	-
testcase_05	--	-
testcase_06	--	-
testcase_07	--	-
testcase_08	--	-
testcase_09	--	-
testcase_10	--	-
testcase_11	--	-
testcase_12	--	-
testcase_13	--	-
testcase_14	--	-
testcase_15	--	-
testcase_16	--	-
testcase_17	--	-
testcase_18	--	-
testcase_19	--	-
testcase_20	--	-
testcase_21	--	-
testcase_22	--	-
testcase_23	--	-
testcase_24	--	-
testcase_25	--	-
testcase_26	--	-
testcase_27	--	-
testcase_28	--	-
testcase_29	--	-
testcase_30	--	-
testcase_31	--	-
testcase_32	--	-
testcase_33	--	-
testcase_34	--	-
testcase_35	--	-
testcase_36	--	-
testcase_37	--	-
testcase_38	--	-
testcase_39	--	-
testcase_40	--	-
testcase_41	--	-
testcase_42	--	-
testcase_43	--	-
testcase_44	--	-
testcase_45	--	-
testcase_46	--	-
testcase_47	--	-
testcase_48	--	-
testcase_49	--	-
testcase_50	--	-
testcase_51	--	-
testcase_52	--	-
testcase_53	--	-
testcase_54	--	-
testcase_55	--	-
testcase_56	--	-

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <bits/stdc++.h>
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
using namespace std;
typedef long long lint;
typedef pair<lint, lint> pi;
const int mod = 1e9 + 7;
 
template<class flow_t> struct HLPP {
    struct Edge {
        int to, inv;
        flow_t rem, cap;
    };
 
    vector<basic_string<Edge>> G;
    vector<flow_t> excess;
    vector<int> hei, arc, prv, nxt, act, bot;
    queue<int> Q;
    int n, high, cut, work;
 
    // Initialize for n vertices
    HLPP(int k) : G(k) {}
 
    int addEdge(int u, int v,
                flow_t cap, flow_t rcap = 0) {
        G[u].push_back({ v, sz(G[v]), cap, cap });
        G[v].push_back({ u, sz(G[u])-1, rcap, rcap });
        return sz(G[u])-1;
    }
 
    void raise(int v, int h) {
        prv[nxt[prv[v]] = nxt[v]] = prv[v];
        hei[v] = h;
        if (excess[v] > 0) {
            bot[v] = act[h]; act[h] = v;
            high = max(high, h);
        }
        if (h < n) cut = max(cut, h+1);
        nxt[v] = nxt[prv[v] = h += n];
        prv[nxt[nxt[h] = v]] = v;
    }
 
    void global(int s, int t) {
        hei.assign(n, n*2);
        act.assign(n*2, -1);
        iota(all(prv), 0);
        iota(all(nxt), 0);
        hei[t] = high = cut = work = 0;
        hei[s] = n;
        for (int x : {t, s})
            for (Q.push(x); !Q.empty(); Q.pop()) {
                int v = Q.front();
                for(auto &e : G[v]){
                    if (hei[e.to] == n*2 &&
                        G[e.to][e.inv].rem)
                        Q.push(e.to), raise(e.to,hei[v]+1);
                }
            }
    }
 
    void push(int v, Edge& e, bool z) {
        auto f = min(excess[v], e.rem);
        if (f > 0) {
            if (z && !excess[e.to]) {
                bot[e.to] = act[hei[e.to]];
                act[hei[e.to]] = e.to;
            }
            e.rem -= f; G[e.to][e.inv].rem += f;
            excess[v] -= f; excess[e.to] += f;
        }
    }
 
    void discharge(int v) {
        int h = n*2, k = hei[v];
 
        for(int j = 0; j < sz(G[v]); j++){
            auto& e = G[v][arc[v]];
            if (e.rem) {
                if (k == hei[e.to]+1) {
                    push(v, e, 1);
                    if (excess[v] <= 0) return;
                } else h = min(h, hei[e.to]+1);
            }
            if (++arc[v] >= sz(G[v])) arc[v] = 0;
        }
 
        if (k < n && nxt[k+n] == prv[k+n]) {
            for(int j = k; j < cut; j++){
            while (nxt[j+n] < n)
                raise(nxt[j+n], n);
            }
            cut = k;
        } else raise(v, h), work++;
    }
 
    // Compute maximum flow from src to dst
    flow_t flow(int src, int dst) {
        excess.assign(n = sz(G), 0);
        arc.assign(n, 0);
        prv.assign(n*3, 0);
        nxt.assign(n*3, 0);
        bot.assign(n, 0);
        for(auto &e : G[src]){
            excess[src] = e.rem, push(src, e, 0);
        }
 
        global(src, dst);
 
        for (; high; high--)
            while (act[high] != -1) {
                int v = act[high];
                act[high] = bot[v];
                if (v != src && hei[v] == high) {
                    discharge(v);
                    if (work > 4*n) global(src, dst);
                }
            }
 
        return excess[dst];
    }
 
    // Get flow through e-th edge of vertex v
    flow_t getFlow(int v, int e) {
        return G[v][e].cap - G[v][e].rem;
    }
 
    // Get if v belongs to cut component with src
    bool cutSide(int v) { return hei[v] >= n; }
};
 
template <class T> struct Circulation {
    const T INF = numeric_limits<T>::max() / 2;
    T lowerBoundSum = 0;
    HLPP<T> mf;
 
    // Initialize for n vertices
    Circulation(int k) : mf(k + 2) {}
    void addEdge(int s, int e, T l, T r){
        mf.addEdge(s + 2, e + 2, r - l);
        if(l > 0){
            mf.addEdge(0, e + 2, l);
            mf.addEdge(s + 2, 1, l);
        	lowerBoundSum += l;
        }
        else{
        	mf.addEdge(0, s + 2, -l);
        	mf.addEdge(e + 2, 1, -l);
        	lowerBoundSum += -l;
		}
    }
    bool solve(int s, int e){
 //       mf.addEdge(e+2, s+2, INF); // to reduce as maxflow with lower bounds, in circulation problem skip this line
        return lowerBoundSum == mf.flow(0, 1);
        // to get maximum LR flow, run maxflow from s+2 to e+2 again
    }
};

template <class T> struct MinCostCirculation {
	const int SCALE = 2; // scale by 1/(1 << SCALE)
    const T INF = numeric_limits<T>::max() / 2;
	struct EdgeStack {
		int s, e;
		T l, r, cost;
	};
	struct Edge {
		int pos, rev;
		T rem, cap, cost;
	};
	int n;
	vector<EdgeStack> estk;
	Circulation<T> circ;
	vector<vector<Edge>> gph;
	vector<T> p;
    MinCostCirculation(int k) : circ(k), gph(k), p(k) { n = k; }
	void addEdge(int s, int e, T l, T r, T cost){
		estk.push_back({s, e, l, r, cost});
	}
	pair<bool, T> solve(){
		/*
		for(auto &i : estk){
			if(i.s != i.e) circ.addEdge(i.s, i.e, i.l, i.r);
		}
		if(!circ.solve(-1, -1)){
			return make_pair(false, T(0));
		}
		vector<int> ptr(n);*/
		T eps = 0;
		for(auto &i : estk){
			T curFlow = 0;
			/*
			if(i.s != i.e) curFlow = i.r - circ.mf.G[i.s + 2][ptr[i.s]].rem;
			else curFlow = i.r;
			*/
			int srev = sz(gph[i.e]);
			int erev = sz(gph[i.s]);
			if(i.s == i.e) srev++;
			gph[i.s].push_back({i.e, srev, i.r - curFlow, i.r, i.cost * (n + 1)});
			gph[i.e].push_back({i.s, erev, -i.l + curFlow, -i.l, -i.cost * (n + 1)});
			eps = max(eps, abs(i.cost) * (n + 1));
			/*
			if(i.s != i.e){
				ptr[i.s] += 2;
				ptr[i.e] += 2;
			}*/
		}
		while(eps > 1){
			eps = max(T(1), eps >> SCALE);
			auto cost = [&](Edge &e, int s, int t){
				return e.cost + p[s] - p[t];
			};
			vector<T> excess(n);
			queue<int> que;
			auto push = [&](Edge &e, int src, T flow){
				e.rem -= flow;
				gph[e.pos][e.rev].rem += flow;
				excess[src] -= flow;
				excess[e.pos] += flow;
				if(excess[e.pos] <= flow && excess[e.pos] > 0){
					que.push(e.pos);
				}
			};
			auto relabel = [&](int v){
				p[v] = -INF;
				for(auto &e : gph[v]){
					if(e.rem > 0){
						p[v] = max(p[v], p[e.pos] - e.cost - eps);
					}
				}
			};
			for(int i = 0; i < n; i++){
				for(auto &j : gph[i]){
					if(j.rem > 0 && cost(j, i, j.pos) < 0){
						push(j, i, j.rem);
					}
				}
			}
			while(sz(que)){
				int x = que.front();
				que.pop();
				while(excess[x] > 0){
					for(auto &e : gph[x]){
						if(e.rem > 0 && cost(e, x, e.pos) < 0){
							push(e, x, min(e.rem, excess[x]));
							if(excess[x] == 0) break;
						}
					}
					if(excess[x] == 0) break;
					relabel(x);
				}
			}
		}
		T ans = 0;
		for(int i = 0; i < n; i++){
			for(auto &j : gph[i]){
				j.cost /= (n + 1);
				ans += j.cost * (j.cap - j.rem);
			}
		}
		return make_pair(true, ans / 2);
	}
	void bellmanFord(){
		fill(all(p), T(0));
		bool upd = 1;
		while(upd){
			upd = 0;
			for(int i = 0; i < n; i++){
				for(auto &j : gph[i]){
					if(j.rem > 0 && p[j.pos] > p[i] + j.cost){
						p[j.pos] = p[i] + j.cost;
						upd = 1;
					}
				}
			}
		}
	}
};

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n, m, k, l;
	cin >> n >> m >> k >> l;
	MinCostCirculation<lint> mcc(n+m+2);
	for(int i = 0; i < l; i++){
		int z;
		int x, y; cin >> x >> y >> z;
		mcc.addEdge(x, y + n, 0, 1, -(1 << z));
	}
	for(int i = 1; i <= n; i++) mcc.addEdge(0, i, 0, 1, 0);
	for(int i = 1; i <= m; i++) mcc.addEdge(i+n, n+m+1, 0, 1, 0);
	mcc.addEdge(n+m+1, 0, 0, 1e9, 0);
	cout << -mcc.solve().second << "\n";
}

yukicoder

結果

テストケース

ソースコード