結果

問題 No.161 制限ジャンケン
ユーザー tonyu0tonyu0
提出日時 2020-04-20 00:14:59
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 2,221 bytes
コンパイル時間 766 ms
コンパイル使用メモリ 75,836 KB
最終ジャッジ日時 2024-11-14 22:24:46
合計ジャッジ時間 1,466 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
main.cpp:49:17: error: 'numeric_limits' was not declared in this scope
   49 |         T inf = numeric_limits<T>::max() / 3;
      |                 ^~~~~~~~~~~~~~
main.cpp:49:33: error: expected primary-expression before '>' token
   49 |         T inf = numeric_limits<T>::max() / 3;
      |                                 ^
main.cpp:49:39: error: no matching function for call to 'max()'
   49 |         T inf = numeric_limits<T>::max() / 3;
      |                                  ~~~~~^~
In file included from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/string:50,
                 from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/locale_classes.h:40,
                 from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/ios_base.h:41,
                 from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/ios:42,
                 from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/ostream:38,
                 from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/iostream:39,
                 from main.cpp:1:
/home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/stl_algobase.h:254:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
  254 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/stl_algobase.h:254:5: note:   template argument deduction/substitution failed:
main.cpp:49:39: note:   candidate expects 2 arguments, 0 provided
   49 |         T inf = numeric_limits<T>::max() / 3;
      |                                  ~~~~~^~
/home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/stl_algobase.h:300:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
  300 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/home/linuxbrew/.l

ソースコード

diff # 

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

template <typename T>
class MinCostFlow
{
public:
	MinCostFlow(int n) : n(n), capacity(n, vector<T>(n)), cost(n, vector<T>(n)), edge(n), prev(n) {}

	void add_edge(int src, int dst, T cap, T cos)
	{
		capacity[src][dst] = cap;
		capacity[dst][src] = 0;
		cost[src][dst] = cos;
		cost[dst][src] = -cos;
		edge[src].push_back(dst);
		edge[dst].push_back(src);
	}

	T min_cost_flow(int s, int t, T f)
	{
		T res = 0;
		h.assign(n, 0);
		while (f > 0)
		{
			if (!dijkstra(s, t))
				return -1;
			for (int i = 0; i < n; ++i)
				h[i] += min_cost[i];

			T d = f;
			for (int v = t; v != s; v = prev[v])
				d = min(d, capacity[prev[v]][v]);
			f -= d;
			res += d * h[t];
			for (int v = t; v != s; v = prev[v])
			{
				capacity[prev[v]][v] -= d;
				capacity[v][prev[v]] += d;
			}
		}
		return res;
	}

private:
	int n;
	T inf = numeric_limits<T>::max() / 3;
	vector<vector<T>> capacity, cost;
	vector<vector<int>> edge;
	vector<T> min_cost, h;
	vector<int> prev;

	bool dijkstra(int s, int t)
	{
		min_cost.assign(n, inf);
		min_cost[s] = 0;
		priority_queue<pair<T, int>, vector<pair<T, int>>, greater<pair<T, int>>> pq;
		pq.emplace(0, s);
		while (!pq.empty())
		{
			int c = pq.top().first;
			int v = pq.top().second;
			pq.pop();
			if (min_cost[v] < c)
				continue;
			for (int nv : edge[v])
			{
				if (capacity[v][nv] > 0 && min_cost[nv] > min_cost[v] + cost[v][nv] + h[v] - h[nv])
				{
					min_cost[nv] = min_cost[v] + cost[v][nv] + h[v] - h[nv];
					prev[nv] = v;
					pq.emplace(min_cost[nv], nv);
				}
			}
		}
		return min_cost[t] != inf;
	}
};


int g, c, p, n, a[4], b[4];
string s;

int main()
{
	cin >> a[0] >> a[1] >> a[2] >> s;
	n = (int)s.size();
	for (int i = 0; i < n; ++i) {
		if (s[i] == 'G') ++b[0];
		if (s[i] == 'C') ++b[1];
		if (s[i] == 'P') ++b[2];
	}

	MinCostFlow<int> mcf(8);

	int INF = 333;
	int s = 6;
	int t = 7;
	for (int i = 0; i < 3; ++i) {
		mcf.add_edge(s, i, a[i], 0);
		mcf.add_edge(i + 3, t, b[i], 0);

		mcf.add_edge(i, i + 3, INF, -1);
		mcf.add_edge(i, (i + 4) % 3 + 3, INF, -3);
		mcf.add_edge(i, (i + 5) % 3 + 3, INF, 0);
	}

	cout << -mcf.min_cost_flow(s, t, n) << endl;

	return 0;
}
0