QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#185821#7064. Spy0x4F5DA2Compile Error//C++143.3kb2023-09-22 17:17:102023-09-22 17:17:11

Judging History

你现在查看的是最新测评结果

  • [2023-09-22 17:17:11]
  • 评测
  • [2023-09-22 17:17:10]
  • 提交

answer

#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

const int maxn = 400;
int n;
struct AmyNode{
	long long a;
	int p;
}Amy[maxn + 10];
long long sum[maxn + 10];
bool cmp(AmyNode a, AmyNode b){
	return a.a < b.a;
}

long long b[maxn + 10];
long long c[maxn + 10];

long long getE(long long x){
	int l = 0, r = n;
	while(l != r){
		int mid = (l + r + 1) >> 1;
		if(Amy[mid].a < x)
			l = mid;
		else
			r = mid - 1;
	}
	return sum[l];
}

template<typename T>
struct hungarian {
	int n;
	vector<int> matchx;
	vector<int> matchy;
	vector<int> pre;
	vector<bool> visx;
	vector<bool> visy;
	vector<T> lx;
	vector<T> ly;
	vector< vector<T> >g;
	vector<T> slack;
	T inf;
	T res;
	queue<int> q;
	int org_n;
	int org_m;
	
	hungarian(int _n, int _m){
		org_n = _n;
		org_m = _m;
		n = max(_n, _m);
		inf = numeric_limits<T>::max();
		res = 0;
		g = vector<vector<T> >(n, vector<T>(n));
		matchx = vector<int>(n, -1);
		matchy = vector<int>(n, -1);
		pre = vector<int>(n);
		visx = vector<bool>(n);
		visy = vector<bool>(n);
		lx = vector<T>(n, -inf);
		ly = vector<T>(n);
		slack = vector<T>(n);
	}
	
	void addEdge(int u, int v, T w){
		g[u][v] = max(w, (T)0);
	}
	
	bool check(int v){
		visy[v] = true;
		if(matchy[v] != -1){
			q.push(matchy[v]);
			visx[matchy[v]] = true;
			return false;
		}
		while(v != -1){
			matchy[v] = pre[v];
			swap(v, matchx[pre[v]]);
		}
		return true;
	}
	
	void bfs(int i){
		while(!q.empty()){
			q.pop();
		}
		q.push(i);
		visx[i] = true;
		while(true){
			while(!q.empty()){
				int u = q.front();
				q.pop();
				for(int v = 0; v < n; ++v){
					if(!visy[v]){
						T delta = lx[u] + ly[v] - g[u][v];
						if(slack[v] >= delta){
							pre[v] = u;
							if(delta){
								slack[v] = delta;
							}
							else if (check(v)){
								return ;
							}
						}
					}
				}
			}
			T a = inf;
			for(int j = 0; j < n; ++j){
				if(!visy[j]){
					a = min(a, slack[j]);
				}
			}
			for(int j = 0; j < n; ++j){
				if(visx[j]){
					lx[j] -= a;
				}
				if(visy[j]){
					ly[j] += a;
				}
				else{
					slack[j] -= a;
				}
			}
			for(int j = 0; j < n; ++j){
				if(!visy[j] && slack[j] == 0 && check(j)){
					return ;
				}
			}
		}
	}
	
	T solve(){
		for(int i = 0; i < n; ++i){
			for(int j = 0; j < n; ++j){
				lx[i] = max(lx[i], g[i][j]);
			}
		}
		
		for(int i = 0; i < n; ++i){
			fill(slack.begin(), slack.end(), inf);
			fill(visx.begin(), visx.end(), false);
			fill(visy.begin(), visy.end(), false);
			bfs(i);
		}
		
		for(int i = 0; i < n; ++i){
			if(g[i][matchx[i]] > 0){
				res += g[i][matchx[i]];
			}
			else{
				matchx[i] = -1;
			}
		}
		return res;
	}
};

int main(){
	scanf("%d", &n);
	for(int i = 1; i <= n; ++i){
		scanf("%lld", &Amy[i].a);
	}
	for(int i = 1; i <= n; ++i){
		scanf("%d", &Amy[i].p);
	}
	sort(Amy + 1, Amy + 1 + n, cmp);
	for(int i = 1; i <= n; ++i){
		sum[i] = sum[i] + Amy[i].p;
	}
	for(int i = 1; i <= n; ++i){
		scanf("%lld", &b[i]);
	}
	for(int i = 1; i <= n; ++i){
		scanf("%lld", &c[i]);
	}
	hungarian<long long> temp(n + 1, n + 1);
	for(int i = 1; i <= n; ++i){
		for(int j = 1; j <= n; ++j){
			temp.addEdge(i, j, getE(b[i] + c[j]));
		}
	}
	printf("%lld", temp.solve());
	return 0;
}

详细

answer.code: In constructor ‘hungarian<T>::hungarian(int, int)’:
answer.code:56:23: error: ‘numeric_limits’ was not declared in this scope
   56 |                 inf = numeric_limits<T>::max();
      |                       ^~~~~~~~~~~~~~
answer.code:56:39: error: expected primary-expression before ‘>’ token
   56 |                 inf = numeric_limits<T>::max();
      |                                       ^
answer.code:56:45: error: no matching function for call to ‘max()’
   56 |                 inf = numeric_limits<T>::max();
      |                                        ~~~~~^~
In file included from /usr/include/c++/11/algorithm:61,
                 from answer.code:2:
/usr/include/c++/11/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)
      |     ^~~
/usr/include/c++/11/bits/stl_algobase.h:254:5: note:   template argument deduction/substitution failed:
answer.code:56:45: note:   candidate expects 2 arguments, 0 provided
   56 |                 inf = numeric_limits<T>::max();
      |                                        ~~~~~^~
In file included from /usr/include/c++/11/algorithm:61,
                 from answer.code:2:
/usr/include/c++/11/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)
      |     ^~~
/usr/include/c++/11/bits/stl_algobase.h:300:5: note:   template argument deduction/substitution failed:
answer.code:56:45: note:   candidate expects 3 arguments, 0 provided
   56 |                 inf = numeric_limits<T>::max();
      |                                        ~~~~~^~
In file included from /usr/include/c++/11/algorithm:62,
                 from answer.code:2:
/usr/include/c++/11/bits/stl_algo.h:3461:5: note: candidate: ‘template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)’
 3461 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/11/bits/stl_algo.h:3461:5: note:   template argument deduction/substitution failed:
answer.code:56:45: note:   candidate expects 1 argument, 0 provided
   56 |                 inf = numeric_limits<T>::max();
      |                                        ~~~~~^~
In file included from /usr/include/c++/11/algorithm:62,
                 from answer.code:2:
/usr/include/c++/11/bits/stl_algo.h:3467:5: note: candidate: ‘template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)’
 3467 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/11/bits/stl_algo.h:3467:5: note:   template argument deduction/substitution failed:
answer.code:56:45: note:   candidate expects 2 arguments, 0 provided
   56 |                 inf = numeric_limits<T>::max();
      |                                        ~~~~~^~
answer.code: In function ‘int main()’:
answer.code:164:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  164 |         scanf("%d", &n);
      |         ~~~~~^~~~~~~~~~
answer.code:166:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  166 |                 scanf("%lld", &Amy[i].a);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~
answer.code:169:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  169 |                 scanf("%d", &Amy[i].p);
      |                 ~~~~~^~~~~~~~~~~~~~~~~
answer.code:176:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  176 |                 scanf("%lld", &b[i]);
      |                 ~~~~~^~~~~~~~~~~~~~~
answer.code:179:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  179 |                 scanf("%lld", &c[i]);
      |                 ~~~~~^~~~~~~~~~~~~~~