#412036 (C++14) No.957 植林

提出ソース

結果

問題	No.957 植林
ユーザー	ningenMe
提出日時	2019-12-26 01:41:54
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	TLE
実行時間	-
コード長	5,709 bytes
コンパイル時間	2,231 ms
コンパイル使用メモリ	181,368 KB
実行使用メモリ	24,648 KB
最終ジャッジ日時	2024-04-09 03:21:57
合計ジャッジ時間	8,349 ms
ジャッジサーバーID （参考情報）	judge2 / judge3

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,824 KB
testcase_01	AC	2 ms 6,944 KB
testcase_02	AC	2 ms 6,948 KB
testcase_03	AC	114 ms 17,812 KB
testcase_04	AC	98 ms 16,724 KB
testcase_05	AC	89 ms 18,180 KB
testcase_06	AC	108 ms 19,080 KB
testcase_07	AC	107 ms 17,352 KB
testcase_08	AC	57 ms 18,092 KB
testcase_09	AC	56 ms 17,964 KB
testcase_10	AC	61 ms 18,676 KB
testcase_11	AC	56 ms 18,112 KB
testcase_12	AC	58 ms 18,052 KB
testcase_13	AC	42 ms 16,208 KB
testcase_14	AC	50 ms 19,428 KB
testcase_15	AC	51 ms 17,684 KB
testcase_16	AC	40 ms 16,076 KB
testcase_17	AC	45 ms 17,036 KB
testcase_18	TLE	-
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	--	-

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

ソースコード

raw source code

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
 
#define REP(i,n) for(long long i = 0; i < (n); i++)
#define FOR(i, m, n) for(long long i = (m);i < (n); ++i)
#define ALL(obj) (obj).begin(),(obj).end()
#define SPEED cin.tie(0);ios::sync_with_stdio(false);
 
template<class T> using V = vector<T>;
template<class T, class U> using P = pair<T, U>;
template<class T> using PQ = priority_queue<T>;
template<class T> using PQR = priority_queue<T,vector<T>,greater<T>>;
 
constexpr long long MOD = (long long)1e9 + 7;
constexpr long long MOD2 = 998244353;
constexpr long long HIGHINF = (long long)1e18;
constexpr long long LOWINF = (long long)1e15;
constexpr long double PI = 3.1415926535897932384626433;
 
template <class T> vector<T> multivector(size_t N,T init){return vector<T>(N,init);}
template <class... T> auto multivector(size_t N,T... t){return vector<decltype(multivector(t...))>(N,multivector(t...));}
template <class T> void corner(bool flg, T hoge) {if (flg) {cout << hoge << endl; exit(0);}}
template <class T, class U>ostream &operator<<(ostream &o, const map<T, U>&obj) {o << "{"; for (auto &x : obj) o << " {" << x.first << " : " << x.second << "}" << ","; o << " }"; return o;}
template <class T>ostream &operator<<(ostream &o, const set<T>&obj) {o << "{"; for (auto itr = obj.begin(); itr != obj.end(); ++itr) o << (itr != obj.begin() ? ", " : "") << *itr; o << "}"; return o;}
template <class T>ostream &operator<<(ostream &o, const multiset<T>&obj) {o << "{"; for (auto itr = obj.begin(); itr != obj.end(); ++itr) o << (itr != obj.begin() ? ", " : "") << *itr; o << "}"; return o;}
template <class T>ostream &operator<<(ostream &o, const vector<T>&obj) {o << "{"; for (int i = 0; i < (int)obj.size(); ++i)o << (i > 0 ? ", " : "") << obj[i]; o << "}"; return o;}
template <class T, class U>ostream &operator<<(ostream &o, const pair<T, U>&obj) {o << "{" << obj.first << ", " << obj.second << "}"; return o;}
template <template <class tmp>  class T, class U> ostream &operator<<(ostream &o, const T<U> &obj) {o << "{"; for (auto itr = obj.begin(); itr != obj.end(); ++itr)o << (itr != obj.begin() ? ", " : "") << *itr; o << "}"; return o;}
void print(void) {cout << endl;}
template <class Head> void print(Head&& head) {cout << head;print();}
template <class Head, class... Tail> void print(Head&& head, Tail&&... tail) {cout << head << " ";print(forward<Tail>(tail)...);}
template <class T> void chmax(T& a, const T b){a=max(a,b);}
template <class T> void chmin(T& a, const T b){a=min(a,b);}
void YN(bool flg) {cout << (flg ? "YES" : "NO") << endl;}
void Yn(bool flg) {cout << (flg ? "Yes" : "No") << endl;}
void yn(bool flg) {cout << (flg ? "yes" : "no") << endl;}

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

template <class T> class Dinic {
public:
	struct info {
		int to, rev;
		T cap;
	};
	T ini, inf;
	vector<vector<info>> edge;
	vector<int> level, iter;

	Dinic(int N, T ini, T inf) : edge(N), level(N), iter(N), ini(ini), inf(inf) {
		// do nothing
	}

	void make_edge(int from, int to, T cap) {
		edge[from].push_back({ to, (int)edge[to].size(), cap });
		edge[to].push_back({ from, (int)edge[from].size() - 1, ini });
	}

	void bfs(int start) {
		for (int i = 0; i < level.size(); ++i) level[i] = -1;
		queue<int> q;
		level[start] = 0;
		q.push(start);
		while (q.size()) {
			int from = q.front();
			q.pop();
			for (auto& e : edge[from]) {
				if (e.cap > 0 && level[e.to] < 0) {
					level[e.to] = level[from] + 1;
					q.push(e.to);
				}
			}
		}
	}

	T dfs(int from, int goal, T flow) {
		if (from == goal) return flow;
		for (int& i = iter[from]; i < edge[from].size(); ++i) {
			auto& e = edge[from][i];
			if (e.cap <= 0 || level[from] >= level[e.to]) continue;
			T dflow = dfs(e.to, goal, min(flow, e.cap));
			if (dflow <= 0) continue;
			e.cap -= dflow;
			edge[e.to][e.rev].cap += dflow;
			return dflow;
		}
		return ini;
	}

	T maxflow(int start, int goal) {
		T maxflow = ini;
		while (1) {
			bfs(start);
			if (level[goal] < 0) return maxflow;
			for (int i = 0; i < iter.size(); ++i) iter[i] = 0;
			T flow;
			while ((flow = dfs(start, goal, inf))>0) maxflow += flow;
		}
	}
};

//verify https://atcoder.jp/contests/arc085/tasks/arc085_c



int main() {
    SPEED
    int H,W;
    cin >> H >> W;
    vector<ll> R(H),C(W),G(H*W);
    for(int i = 0; i < H; ++i) for(int j = 0; j < W; ++j) cin >> G[i*W+j];
    for(int i = 0; i < H; ++i) cin >> R[i];
    for(int j = 0; j < W; ++j) cin >> C[j];
    
	ll ans = 0;
    //先に利益を得ておく
	for(int i = 0; i < H; ++i) ans += R[i];
    for(int j = 0; j < W; ++j) ans += C[j];
    for(int i = 0; i < H; ++i) for(int j = 0; j < W; ++j) ans += G[i*W+j];

    Dinic<ll> dinic(H+W+H*W+2,0,LOWINF);
    int S = H+W+H*W,T = S + 1;
	//i:Sと接続:使わない
	//i:Tと接続:使う
    for(int i = 0; i < H; ++i) {
		ll sum = 0;
        for(int j = 0; j < W; ++j) sum += G[i*W+j]; 
		//i行目を使わないとき R[i]失う
		dinic.make_edge(S,i,R[i]);
		//i行目を使うとき sum失う
		dinic.make_edge(i,T,sum);
    }
	//j:Sと接続:使わない
	//j:Tと接続:使う
    for(int j = 0; j < W; ++j) {
		ll sum = 0;
        for(int i = 0; i < H; ++i) sum += G[i*W+j]; 
		//j行目を使わないとき C[j]失う
		dinic.make_edge(S,H+j,C[j]);
		//j行目を使うとき sum失う
		dinic.make_edge(H+j,T,sum);
    }
    for(int i = 0; i < H; ++i) {
        for(int j = 0; j < W; ++j) {
			//iとj両方使うとG[i*W+j]得る
			dinic.make_edge(H+W+i*W+j,i,LOWINF);
			dinic.make_edge(H+W+i*W+j,H+j,LOWINF);
			dinic.make_edge(S,H+W+i*W+j,G[i*W+j]);
		}
    }

    ll f = dinic.maxflow(S,T);
    ans -= f;
    cout << ans << endl;

    return 0;
}

yukicoder

結果

テストケース

ソースコード