单纯的HK算法。匈牙利会超时
代码如下
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<queue>
using namespace std;
const int max_n = 3100;
const int max_m = 1e7;
const int inf = 2e9;
struct edge{
int to, next;
}E[max_m];
int head[max_n];
int cnt = 1;
void add(int from, int to) {
E[cnt].to = to;
E[cnt].next = head[from];
head[from] = cnt++;
}
int leftTo[max_n], rightTo[max_n];
int distleft[max_n], distright[max_n];
int dist;
bool seacherpath(int left_tot, int right_tot) {
fill(distleft, distleft + left_tot + 1, -1);
fill(distright, distright + right_tot + 1, -1);
queue<int> que;dist = inf;
for (int i = 1;i <= left_tot;++i)
if (leftTo[i] == -1)
que.push(i);
while (!que.empty()) {
int u = que.front();que.pop();
if (distleft[u] > dist)break;
for (int i = head[u];i;i = E[i].next) {
int v = E[i].to;
if (distright[v] != -1)continue;
distright[v] = distleft[u] + 1;
if (rightTo[v] == -1)dist = distright[v];
else {
distleft[rightTo[v]] = distright[v] + 1;
que.push(rightTo[v]);
}
}
}return dist != inf;
}
bool matchpath(int u) {
for (int i = head[u];i;i = E[i].next) {
int v = E[i].to;
if (distright[v] != distleft[u] + 1)continue;
if (distright[v] == dist && rightTo[v] != -1)continue;
distright[v] = -1;
if (rightTo[v] == -1 || matchpath(rightTo[v])) {
leftTo[u] = v;
rightTo[v] = u;
return true;
}
}return false;
}
int HK(int left_tot, int right_tot) {
fill(leftTo, leftTo + left_tot + 1, -1);
fill(rightTo, rightTo + right_tot + 1, -1);
int ans = 0;
while (seacherpath(left_tot, right_tot)) {
for (int i = 1;i <= left_tot;++i)
if (leftTo[i] == -1 && matchpath(i))
++ans;
}return ans;
}
double g[max_n][3];
double ru[max_n][2];
bool comput(int i,int j,int t) {
return sqrt(pow(g[i][0] - ru[j][0], 2) + pow(g[i][1] - ru[j][1], 2)) <= t * g[i][2];
}
int main() {
int T;scanf("%d", &T);
for (int tcase = 1;tcase <= T;++tcase) {
int t;scanf("%d", &t);
int n, m;
scanf("%d", &n);
fill(head, head + n + 10, 0);cnt = 1;
for (int i = 1;i <= n;++i)
scanf("%lf %lf %lf", &g[i][0], &g[i][1], &g[i][2]);
scanf("%d", &m);
for (int i = 1;i <= m;++i)
scanf("%lf %lf", &ru[i][0], &ru[i][1]);
for (int i = 1;i <= n;++i)
for (int j = 1;j <= m;++j)
if (comput(i, j, t))
add(i, j);
printf("Scenario #%d:\n%d\n\n", tcase, HK(n, m));
}
}