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

提出ソース

結果

問題	No.957 植林
ユーザー	ningenMe
提出日時	2019-12-27 04:46:59
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	488 ms / 2,000 ms
コード長	5,213 bytes
コンパイル時間	1,801 ms
コンパイル使用メモリ	184,188 KB
実行使用メモリ	8,960 KB
最終ジャッジ日時	2024-10-06 04:23:33
合計ジャッジ時間	14,176 ms
ジャッジサーバーID （参考情報）	judge4 / judge5

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 ms 5,248 KB
testcase_02	AC	2 ms 5,248 KB
testcase_03	AC	19 ms 8,320 KB
testcase_04	AC	20 ms 8,064 KB
testcase_05	AC	19 ms 8,448 KB
testcase_06	AC	23 ms 8,576 KB
testcase_07	AC	20 ms 8,192 KB
testcase_08	AC	14 ms 8,320 KB
testcase_09	AC	14 ms 8,320 KB
testcase_10	AC	15 ms 8,576 KB
testcase_11	AC	14 ms 8,320 KB
testcase_12	AC	13 ms 8,448 KB
testcase_13	AC	11 ms 6,912 KB
testcase_14	AC	14 ms 8,704 KB
testcase_15	AC	13 ms 8,448 KB
testcase_16	AC	11 ms 6,912 KB
testcase_17	AC	12 ms 8,064 KB
testcase_18	AC	394 ms 8,320 KB
testcase_19	AC	371 ms 8,448 KB
testcase_20	AC	391 ms 8,448 KB
testcase_21	AC	404 ms 8,576 KB
testcase_22	AC	429 ms 8,704 KB
testcase_23	AC	432 ms 8,832 KB
testcase_24	AC	440 ms 8,832 KB
testcase_25	AC	477 ms 8,960 KB
testcase_26	AC	471 ms 8,960 KB
testcase_27	AC	480 ms 8,960 KB
testcase_28	AC	470 ms 8,960 KB
testcase_29	AC	475 ms 8,960 KB
testcase_30	AC	475 ms 8,960 KB
testcase_31	AC	366 ms 8,320 KB
testcase_32	AC	377 ms 8,448 KB
testcase_33	AC	377 ms 8,448 KB
testcase_34	AC	404 ms 8,576 KB
testcase_35	AC	418 ms 8,704 KB
testcase_36	AC	437 ms 8,832 KB
testcase_37	AC	443 ms 8,832 KB
testcase_38	AC	476 ms 8,960 KB
testcase_39	AC	488 ms 8,832 KB
testcase_40	AC	481 ms 8,960 KB
testcase_41	AC	10 ms 8,960 KB
testcase_42	AC	10 ms 8,832 KB
testcase_43	AC	16 ms 8,960 KB
testcase_44	AC	16 ms 8,960 KB
testcase_45	AC	2 ms 6,816 KB
testcase_46	AC	1 ms 6,816 KB
testcase_47	AC	2 ms 6,820 KB

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

ソースコード

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;
    Dinic<ll> dinic(H+W+2,0,LOWINF);
    int S = 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];
		ans += R[i];
		if(R[i]>=sum){
			ans -= sum;
		}
		else{
			dinic.make_edge(S,i,sum-R[i]);
			ans -= R[i];
		}
    }
	//j:Sと接続:使う
	//j:Tと接続:使わない
    for(int j = 0; j < W; ++j) {
		ans += C[j];
		dinic.make_edge(H+j,T,C[j]);
    }
	//この供給は常にある
    for(int i = 0; i < H; ++i) {
        for(int j = 0; j < W; ++j) {
			dinic.make_edge(i,H+j,G[i*W+j]);
		}
    }

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

    return 0;
}

yukicoder

結果

テストケース

ソースコード