結果

問題 No.161 制限ジャンケン
コンテスト
ユーザー ty70
提出日時 2015-05-27 04:51:42
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 2 ms / 5,000 ms
コード長 4,145 bytes
コンパイル時間 861 ms
コンパイル使用メモリ 93,072 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-11-30 04:37:12
合計ジャッジ時間 1,441 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 16
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘void add_edge(int, int, int, int)’:
main.cpp:78:60: warning: narrowing conversion of ‘G[to].std::vector<edge>::size()’ from ‘std::vector<edge>::size_type’ {aka ‘long unsigned int’} to ‘int’ [-Wnarrowing]
   78 |         G[from].push_back ((edge){to, cap, cost, G[to].size() } );
      |                                                  ~~~~~~~~~~^~
main.cpp:79:64: warning: narrowing conversion of ‘(G[from].std::vector<edge>::size() - 1)’ from ‘std::vector<edge>::size_type’ {aka ‘long unsigned int’} to ‘int’ [-Wnarrowing]
   79 |         G[to].push_back ((edge){from, 0, -cost, G[from].size() -1});
      |                                                 ~~~~~~~~~~~~~~~^~

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <algorithm>	// require sort next_permutation count __gcd reverse etc.
#include <cstdlib>	// require abs exit atof atoi 
#include <cstdio>		// require scanf printf
#include <functional>
#include <numeric>	// require accumulate
#include <cmath>		// require fabs
#include <climits>
#include <limits>
#include <cfloat>
#include <iomanip>	// require setw
#include <sstream>	// require stringstream 
#include <cstring>	// require memset
#include <cctype>		// require tolower, toupper
#include <fstream>	// require freopen
#include <ctime>		// require srand
#define rep(i,n) for(int i=0;i<(n);i++)
#define ALL(A) A.begin(), A.end()
#define INF 1<<28

using namespace std;

typedef long long ll;
typedef pair<int, int> P;

/*
	yukicoder: No. 161 制限ジャンケン

	最大費用流(?)
	最大費用流 := 最大費用 - 最小費用流
 
	最大費用 := 3*|S|
	よって 最小費用流を求める.
		         
	    --> G ----> g	
	   /	   \＼ /    \
	  /	    \ /＼     \
	S --->  C ----> c --> T
 	  \        / \／     /
	   \       / ／ \   /
	    --> P ----> p

	G : cap : G C : cap : C P : cap : P
	g : cap : g c : cap : c p : cap : p
	S -> G : cost : 0
	S -> C : cost : 0
	S -> P : cost : 0
	G -> g : cost : 3 - 1
	G -> c : cost : 3 - 3
	G -> p : cost : 3 - 0
	C -> g : cost : 3 - 0
	C -> c : cost : 3 - 1
	C -> p : cost : 3 - 3
	g -> T : cost : 0
	c -> T : cost : 0
	c -> T : cost : 0
*/

const int MAX_V = 3 + 3 + 2;

// 辺を表す構造体 (行き先、容量、コスト、逆辺）
struct edge{ int to, cap, cost, rev; };

int V;					// 頂点数
vector<edge> G[MAX_V];		// グラフの隣接リスト表現
int dist[MAX_V];			// 最短距離
int prevv[MAX_V], preve[MAX_V];	// 直前の頂点と辺

// from から to へ向かう容量 cap の辺をグラフに追加する
void add_edge (int from, int to, int cap, int cost ){
	G[from].push_back ((edge){to, cap, cost, G[to].size() } );
	G[to].push_back ((edge){from, 0, -cost, G[from].size() -1});
}

// s から t への流量 f の最小費用流を求める
// 流せない場合は -1 を返す
int min_cost_flow (int s, int t, int f ){
	int res = 0;
	while (f > 0 ){
		// ベルマンフォード法により、s-t 間最短路を求める
		fill (dist, dist+V, INF );
		dist[s] = 0;
		bool update = true;
		while (update ){
			update = false;
			rep (v, V ){
				if (dist[v] == INF ) continue;
				rep (i, G[v].size() ){
					edge &e = G[v][i];
					if (e.cap > 0 && dist[e.to] > dist[v] + e.cost ){
						dist[e.to] = dist[v] + e.cost;
						prevv[e.to] = v;
						preve[e.to] = i;
						update = true;
					} // end if
				} // end rep
			} // end rep
		} // end while

		if (dist[t] == INF ){
			// これ以上流せない
			return -1;
		} // end if

		// s-t 間最短路に沿って目一杯流す
		int d = f;
		for (int v = t; v != s; v = prevv[v] ){
			d = min (d, G[prevv[v]][preve[v]].cap );
		} // end for
		f -= d;
		res += d*dist[t];
		for (int v = t; v != s; v = prevv[v] ){
			edge &e = G[prevv[v]][preve[v]];
			e.cap -= d;
			G[v][e.rev].cap += d;
		} // end for
	} // end while

	return res;
}

int main()
{
	ios_base::sync_with_stdio(0);
	int G, C, P; cin >> G >> C >> P;
	string s; cin >> s;
	int g = (int)count (ALL (s), 'G' );
	int c = (int)count (ALL (s), 'C' );
	int p = (int)count (ALL (s), 'P' );

	V = MAX_V;
	int S = 0, T = V - 1;
	
	add_edge (S, 1, G, 0 );	// S -> G
	add_edge (S, 2, C, 0 );	// S -> C
	add_edge (S, 3, P, 0 );	// S -> P
	add_edge (1, 4, g, 3-1 );	// G -> g
	add_edge (1, 5, c, 3-3 );	// G -> c
	add_edge (1, 6, p, 3-0 );	// G -> p
	add_edge (2, 4, g, 3-0 );	// C -> g
	add_edge (2, 5, c, 3-1 );	// C -> c
	add_edge (2, 6, p, 3-3 );	// C -> p
	add_edge (3, 4, g, 3-3 );	// P -> g
	add_edge (3, 5, c, 3-0 );	// P -> c
	add_edge (3, 6, p, 3-1 );	// P -> p
	add_edge (4, T, g, 0 );	// g -> T	
	add_edge (5, T, c, 0 );	// c -> T
	add_edge (6, T, p, 0 );	// p -> T

	int ans = min_cost_flow (S, T, G + C + P );
	int res = 3*(int)s.length() - ans;
	cout << res << endl;	

	return 0;
}
0