QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#185821 | #7064. Spy | 0x4F5DA2 | Compile Error | / | / | C++14 | 3.3kb | 2023-09-22 17:17:10 | 2023-09-22 17:17:11 |
Judging History
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]); | ~~~~~^~~~~~~~~~~~~~~