結果

問題 No.200 カードファイト！
ユーザー koyumeishikoyumeishi
提出日時 2015-06-01 23:25:54
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 4 ms / 2,000 ms
コード長 4,914 bytes
コンパイル時間 878 ms
コンパイル使用メモリ 91,652 KB
実行使用メモリ 4,384 KB
最終ジャッジ日時 2023-08-05 11:55:35
合計ジャッジ時間 2,126 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge14
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
4,376 KB
testcase_01 AC 3 ms
4,376 KB
testcase_02 AC 1 ms
4,380 KB
testcase_03 AC 2 ms
4,380 KB
testcase_04 AC 1 ms
4,376 KB
testcase_05 AC 3 ms
4,376 KB
testcase_06 AC 3 ms
4,376 KB
testcase_07 AC 3 ms
4,376 KB
testcase_08 AC 3 ms
4,380 KB
testcase_09 AC 3 ms
4,380 KB
testcase_10 AC 3 ms
4,376 KB
testcase_11 AC 2 ms
4,376 KB
testcase_12 AC 2 ms
4,380 KB
testcase_13 AC 2 ms
4,380 KB
testcase_14 AC 1 ms
4,380 KB
testcase_15 AC 2 ms
4,380 KB
testcase_16 AC 2 ms
4,376 KB
testcase_17 AC 1 ms
4,376 KB
testcase_18 AC 1 ms
4,380 KB
testcase_19 AC 2 ms
4,376 KB
testcase_20 AC 3 ms
4,376 KB
testcase_21 AC 2 ms
4,376 KB
testcase_22 AC 2 ms
4,376 KB
testcase_23 AC 2 ms
4,380 KB
testcase_24 AC 2 ms
4,384 KB
testcase_25 AC 2 ms
4,376 KB
testcase_26 AC 2 ms
4,376 KB
testcase_27 AC 2 ms
4,376 KB
testcase_28 AC 4 ms
4,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <cstdio>
#include <sstream>
#include <map>
#include <string>
#include <algorithm>
#include <queue>
#include <cmath>
#include <set>
using namespace std;

template<class T>
class Min_Cost_Flow{
public:

	struct edge{
		int to;
		int cap;
		T cost;
		int rev;
		bool reverse;
	};

	const T INF;
	vector<vector<edge>> G;

	Min_Cost_Flow(int n, T inf) : G(n), INF(inf){

	}

	void add_edge(int from, int to, int cap, T cost){
		G[from].push_back((edge){to, cap, cost, (int)G[to].size(), false});
		G[to].push_back((edge){from, 0, -cost, (int)G[from].size()-1, true});
	}


	//min cost : s->t (flow:f)
	T min_cost_flow(int s, int t, int f){
		T cost = 0;
		vector<int> prev_v(G.size(),-1);
		vector<int> prev_e(G.size(),-1);
		vector<T> potantial(G.size(), 0);
		vector<T> dist(G.size(), INF);

		dist[s] = 0;

		/*bellman_ford*/{
			bool update = true;
			for(int cnt = 0; update; cnt++){
				update = false;
				for(int i=0; i<G.size(); i++){
					if(dist[i] >= INF) continue;
					for(int j=0; j<G[i].size(); j++){
						if(G[i][j].cap > 0 && dist[G[i][j].to] > dist[i] + G[i][j].cost){
							dist[G[i][j].to] = dist[i] + G[i][j].cost;

							update = true;
						}
					}
				}

				if(update && cnt >= G.size()){
					cerr << " there is a negative cycle " << endl;
					return -1;
				}
				cnt++;
			}

			for(int i=0; i<G.size(); i++){
				potantial[i] = dist[i];
			}
		}

		while(f>0){
			fill(dist.begin(), dist.end(), INF);
			dist[s] = 0;
			prev_v[s] = s;

			/*dijkstra*/{
				priority_queue<pair<T,int>, vector<pair<T,int>>, greater<pair<T,int>>> pq;
				pq.push({0, s});
				while(pq.size()){
					pair<T, int> p = pq.top(); pq.pop();
					if(dist[p.second] < p.first) continue;
					dist[p.second] = p.first;
					for(int i=0; i<G[p.second].size(); i++){
						edge& e = G[p.second][i];
						T new_dist = dist[p.second] + e.cost + potantial[p.second] - potantial[e.to];
						if(e.cap > 0 && dist[e.to] > new_dist){
							dist[e.to] = new_dist;
							prev_v[e.to] = p.second;
							prev_e[e.to] = i;
							pq.push({dist[e.to], e.to});
						}
					}
				}
			}

			if(potantial[t] + dist[t] == INF){
				cerr << "couldn't insert flow f : " << f << endl;
				return -1;
			}

			for(int i=0; i<G.size(); i++){
				potantial[i] += dist[i];
			}

			int d = f;
			int pos = t;
			while(pos != s){
				int v = prev_v[pos];
				int e = prev_e[pos];
				d = min(d, G[v][e].cap);
				pos = prev_v[pos];
			}

			pos = t;
			while(pos != s){
				int v = prev_v[pos];
				int e = prev_e[pos];
				G[v][e].cap -= d;
				G[G[v][e].to][G[v][e].rev].cap += d;
				pos = v;
			}
			cost += d * potantial[t];	//potential is new_dist
			f -= d;

			//f==0 then end
		}
		return cost;
	}

	vector<vector<int>> get_edge_info(){
		vector<vector<int>> E(G.size());

		for(int i=0; i<G.size(); i++){
			for(int j=0; j<G[i].size(); j++){
				edge& e = G[i][j];
				if(e.reverse) continue;

				edge& rev_e = G[e.to][e.rev];
				if(e.cap == 0){
					E[i].push_back(e.to);
				}
			}
		}
		return E;
	}

};

int main(){
	int n;
	cin >> n;
	int x;
	cin >> x;
	vector<int> a(x);
	for(int i=0; i<x; i++){cin>>a[i];}
	random_shuffle(a.begin(), a.end());

	int y;
	cin >> y;
	vector<int> b(y);
	for(int i=0; i<y; i++){cin>>b[i];}
	random_shuffle(b.begin(), b.end());

	int sz_x = (n/x + (n%x==0?0:1)) * x;
	int sz_y = (n/y + (n%y==0?0:1)) * y;
	
	int sz = sz_x + sz_y + 2;


	int s = sz_x + sz_y + 0;
	int t = sz_x + sz_y + 1;
	Min_Cost_Flow<int> flow(sz, 1e8);

	vector<long long> offset_x;

	for(int k=0; k<sz_x/x; k++){
		for(int i=0; i<x; i++){
			long long cost = 100000 + 10*k;
			flow.add_edge(s, i + x*k, 1, cost);

			offset_x.push_back(cost);
		}
	}

	vector<long long> offset_y;

	for(int k=0; k<sz_y/y; k++){
		for(int i=0; i<y; i++){
			long long cost = 100000 + 10*k;
			flow.add_edge( sz_x + i + y*k, t, 1, cost);
			offset_y.push_back(cost);
		}
	}

	for(int i=0; i<sz_x; i++){
		for(int j=sz_x; j<sz_x+sz_y; j++){
			int l = ( ( (i/x)*x)/y)*y;
			int r = (((i/x + 1)*x - 1)/y + 1)*y;
			if( j-sz_x < l || r <= j-sz_x) continue;
			flow.add_edge( i, j, 1, (a[i%x]>b[(j-sz_x)%y]?0:1) );

		}
	}

	long long ans = 0;
	for(int i=0; i<n; i++){
		ans -= offset_x[i] + offset_y[i];
	}


	ans += flow.min_cost_flow(s,t, n);
	
	ans = n - ans;
	cout << ans << endl;
/*
	
	cerr << s << " " << t << endl;

	auto e = flow.get_edge_info();

	map<int, vector<int>> v;
	for(int i=0; i<e.size(); i++){
		if(i == s || i == t) continue;
		if(i >= sz_x) continue;
		for(int j=0; j<e[i].size(); j++){
			if(e[i][j] == s || e[i][j] == t) continue;
			cerr << i << " -> " << e[i][j]-sz_x << " : ";
			cerr << a[i%x] << " -> " << b[(e[i][j]-sz_x)%y] << endl;

			v[a[i%x]].push_back(b[(e[i][j]-sz_x)%y]);
		}
	}

	for(int i=0; i<x; i++){
		cerr << a[i] << " ";
		for(auto itr = v[a[i]].begin(); itr != v[a[i]].end(); itr++){
			cerr << *itr << " ";
		}cerr << endl;
	}
*/

	return 0;
}
0