Submission #1094583

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1094583	2024-09-30T02:08:34 Z	TIN	Domino (COCI15_domino)	C++17	Compilation error	0 ms	0 KB

domino

#include <bits/stdc++.h>

using namespace std;

#define FNAME "test"

typedef long long ll;

const ll oo = 1e18 + 1;

struct Edge {
	int from, to, cap;
	ll cost;

	Edge(int from, int to, int cap, ll cost) : from(from), to(to), cap(cap), cost(cost) {}
};

struct MinFlow {
	int n, k, s, t;

	vector<vector<int>> adj;
	vector<vector<ll>> cap;
	vector<vector<ll>> cost;

	MinFlow(int _n, int _k, int _s, int _t) {
		n  = _n;
		k = _k;
		s = _s;
		t = _t;
		adj.assign(n, vector<int>());
		cost.assign(n, vector<ll>(n, 0));
		cap.assign(n, vector<ll>(n, 0));
	}

	void addEdge(Edge e) {
		adj[e.from].push_back(e.to);
		adj[e.to].push_back(e.from);
		cost[e.from][e.to] = e.cost;
		cost[e.to][e.from] = -e.cost;
		cap[e.from][e.to] = e.cap;
	}

	void shortest_paths(int v0, vector<ll>& d, vector<int>& p) {
		d.assign(n, oo);
		d[v0] = 0;
		vector<bool> inq(n, false);
		queue<int> q;
		q.push(v0);
		p.assign(n, -1);
		while (!q.empty()) {
			int u = q.front(); q.pop();
			inq[u] = false;
			for (int v : adj[u]) {
				if (cap[u][v] > 0 && d[v] > d[u] + cost[u][v]) {
					d[v] = d[u] + cost[u][v];
					p[v] = u;
					if (!inq[v]) {
						inq[v] = true;
						q.push(v);
					}
				}
			}
		}
	}

	ll min_cost_flow() {
		int flow = 0;
		ll cost = 0;
		vector<ll> d;
		vector<int> p;
		while (flow < k) {
			shortest_paths(s, d, p);
			if (d[t] == oo) break;
			int f = k - flow;
			int cur = t;
			while (cur != s) {
				f = min(f, cap[p[cur]][cur]);
				cur = p[cur];
			}
			flow += f;
			cost += 1LL * f * d[t];
			cur = t;
			while (cur != s) {
				cap[p[cur]][cur] -= f;
				cap[cur][p[cur]] += f;
				cur = p[cur];
			}
		}
		if (flow < k) return -1;
		return cost;
	}
};

int n, k;
ll sum, ans;

void Task() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cout << fixed << setprecision(9);
	if (fopen(FNAME".inp","r")) {
		freopen(FNAME".inp","r",stdin);
		freopen(FNAME".out","w",stdout);
	}
}

void Solve() {
	//Your Code
	cin >> n >> k;
	MinFlow calc(n * n + 5, k, 0, n * n + 1);
	sum = 0;
	for (int i  = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			ll x;
			cin >> x;
			sum += x;
			int id = (i - 1) * n + j;
			if ((i + 1 + j) & 1) {
				calc.addEdge(Edge(0, id, 1, -x));
				if (i > 1) calc.addEdge(Edge(id, id - n, 1, 0));
				if (j > 1) calc.addEdge(Edge(id, id - 1, 1, 0));
			} else {
				calc.addEdge(Edge(id, n * n + 1, 1, -x));
				if (i > 1) calc.addEdge(Edge(id - n, id, 1, 0));
				if (j > 1) calc.addEdge(Edge(id - 1, id, 1, 0));
			}
		}
	}
	ans = calc.min_cost_flow();
	cout << sum + ans << '\n';
}

int main() {
	Task();
	Solve();
	cerr << "\nTime run: " << 1000*clock()/CLOCKS_PER_SEC << "ms";
	return 37^37;
}

Compilation message

domino.cpp: In member function 'll MinFlow::min_cost_flow()':
domino.cpp:77:32: error: no matching function for call to 'min(int&, __gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type&)'
   77 |     f = min(f, cap[p[cur]][cur]);
      |                                ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from domino.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:230:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)'
  230 |     min(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:230:5: note:   template argument deduction/substitution failed:
domino.cpp:77:32: note:   deduced conflicting types for parameter 'const _Tp' ('int' and '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'})
   77 |     f = min(f, cap[p[cur]][cur]);
      |                                ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from domino.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:278:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)'
  278 |     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:278:5: note:   template argument deduction/substitution failed:
domino.cpp:77:32: note:   deduced conflicting types for parameter 'const _Tp' ('int' and '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'})
   77 |     f = min(f, cap[p[cur]][cur]);
      |                                ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from domino.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3468:5: note: candidate: 'template<class _Tp> constexpr _Tp std::min(std::initializer_list<_Tp>)'
 3468 |     min(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3468:5: note:   template argument deduction/substitution failed:
domino.cpp:77:32: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   77 |     f = min(f, cap[p[cur]][cur]);
      |                                ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from domino.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3474:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::min(std::initializer_list<_Tp>, _Compare)'
 3474 |     min(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3474:5: note:   template argument deduction/substitution failed:
domino.cpp:77:32: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   77 |     f = min(f, cap[p[cur]][cur]);
      |                                ^
domino.cpp: In function 'void Task()':
domino.cpp:102:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  102 |   freopen(FNAME".inp","r",stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
domino.cpp:103:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  103 |   freopen(FNAME".out","w",stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~