题目链接: HDU-2389
此题对时间要求比较高，一共有客人数 <= 3000, 雨伞数 <= 3000. 若用普通的匈牙利算法，即使加上邻接表优化时间复杂度也过高， 所以要使用更优的算法 HK算法Hopcroft-Carp算法求二分图最大匹配数, 时间复杂度为O(sqrt(v)*E), 然后再加上邻接表优化。
匈牙利算法+邻接表优化(TLE)
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <cmath>
using namespace std;const int MAXN = 3005;
struct _Node{int x, y, s;_Node(int _x, int _y, int _s = -1){x = _x;y = _y;s = _s;}_Node(){s = -1;}
};
vector<int> g[MAXN];
int use[MAXN], visit[MAXN];
int t, nx, ny;
_Node pp[MAXN], up[MAXN]; //people position, umbrella positionbool canGet(_Node p, _Node u){return sqrt((p.x - u.x)*(p.x - u.x) + (p.y - u.y)*(p.y - u.y)) <= p.s*t;
}bool dfs(int x){for(int i = 0; i < g[x].size(); ++i){int y = g[x][i];if(!visit[y]){visit[y] = 1;if(use[y] == -1 || dfs(use[y])){use[y] = x;return 1;}}}return 0;
}int getMax(){int sum = 0;memset(use, -1, sizeof(use));for(int x = 1; x <= nx; ++x){memset(visit, 0, sizeof(visit));if(dfs(x)) sum ++;}return sum;
}int main(){int T, cnt = 0;scanf("%d", &T);while(T--){for(int i = 0; i < MAXN; ++i) g[i].clear();scanf("%d", &t);scanf("%d", &nx);for(int i = 1; i <= nx; ++i) scanf("%d%d%d", &pp[i].x, &pp[i].y, &pp[i].s);scanf("%d", &ny);for(int i = 1; i <= ny; ++i) scanf("%d%d", &up[i].x, &up[i].y);for(int x = 1; x <= nx; ++x)for(int y = 1; y <= ny; ++y) if(canGet(pp[x], up[y])) g[x].push_back(y);printf("Scenario #%d:\n%d\n\n", ++cnt, getMax());}return 0;
}邻接矩阵HK算法(TLE)
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <queue>using namespace std;/*hk o（sqrt（v）*e） 算法求二分图最大匹配， 时间复杂度比匈牙利算法o（ve）优秀 */const int inf = 0x3f3f3f3f;
const int maxn = 3005;
struct _node{int x, y, s;
};
int g[maxn][maxn], mx[maxn], my[maxn], visit[maxn];
_node pp[maxn], up[maxn];
int dx[maxn], dy[maxn], dist;
int nx, ny, t;bool isconnected(_node p, _node u){return sqrt((p.x - u.x)*(p.x - u.x) + (p.y - u.y)*(p.y - u.y)) <= p.s*t;
}//找到最短的增广路
bool bfs(){queue<int> q;dist = inf;memset(dx, -1, sizeof(dx));memset(dy, -1, sizeof(dy));for(int i = 1; i <= nx; ++i) if(mx[i] == -1){q.push(i);dx[i] = 0;}while(!q.empty()){int u = q.front();q.pop();if(dx[u] > dist) break;for(int v = 1; v <= ny; v++){if(g[u][v] && dy[v] == -1){dy[v] = dx[u] + 1;if(my[v] == -1) dist = dy[v];else{dx[my[v]] = dy[v] + 1;q.push(my[v]);}}}}return dist != inf;
}bool dfs(int u){for(int v = 1; v <= ny; ++v){if(!visit[v] && g[u][v] && dy[v] == dx[u] + 1){visit[v] = 1;if(my[v] != -1 && dy[v] == dist) continue;if(my[v] == -1 || dfs(my[v])){my[v] = u;my[u] = v;return 1;}}}return 0;
}int maxmatch(){int sum = 0;memset(mx, -1, sizeof(mx));memset(my, -1, sizeof(my));while(bfs()){memset(visit, 0, sizeof(visit));for(int i = 1; i <= nx; ++i){if(mx[i] == -1 && dfs(i)) sum++;}}return sum;
}int main(){int T, cnt = 0;scanf("%d", &T);while(T--){memset(g, 0, sizeof(g));scanf("%d", &t);scanf("%d", &nx);for(int i = 1; i <= nx; ++i) scanf("%d%d%d", &pp[i].x, &pp[i].y, &pp[i].s);scanf("%d", &ny);for(int i = 1; i <= ny; ++i){scanf("%d%d", &up[i].x, &up[i].y);for(int j = 1; j <= nx; ++j){if(isconnected(pp[j], up[i])) g[j][i] = 1;}}printf("scenario #%d:\n%d\n\n", ++cnt, maxmatch());}return 0;
}邻接表HK算法(AC)
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <vector>using namespace std;const int INF = 0x3f3f3f3f;
const int MAXN = 3005;
struct _node{int x, y, s;
};
vector<int> g[MAXN];
int mx[MAXN], my[MAXN];
int dx[MAXN], dy[MAXN];
int dist, t;
bool visit[MAXN];
_node pp[MAXN], up[MAXN];
int un;bool bfs(){queue<int> q;dist = INF;memset(dx, -1, sizeof(dx));memset(dy, -1, sizeof(dy));for(int i = 1; i <= un; ++i) if(mx[i] == -1){q.push(i);dx[i] = 1;}while(!q.empty()){int u = q.front();q.pop();if(dx[u] > dist) break;int size = g[u].size();for(int i = 0; i < size; ++i){int v = g[u][i];if(dy[v] == -1){dy[v] = dx[u] + 1;if(my[v] == -1) dist = dy[v];else{ dx[my[v]] = dy[v] + 1;q.push(my[v]);}} }}return dist != INF;
}bool dfs(int u){for(int i = 0; i < g[u].size(); ++i){int v = g[u][i];if(!visit[v] && dy[v] == dx[u] + 1){visit[v] = 1;if(my[v] != -1 && dy[v] == dist) continue;if(my[v] == -1 || dfs(my[v])){my[v] = u;mx[u] = v;return 1;}}}return 0;
}int MaxMatch(){int sum = 0;memset(mx, -1, sizeof(mx));memset(my, -1, sizeof(my));while(bfs()){memset(visit, 0, sizeof(visit));for(int u = 1; u <= un; ++u){if(mx[u] == -1 && dfs(u)) sum++;}}return sum;
}bool isconnected(_node p, _node u){return (p.x - u.x)*(p.x - u.x) + (p.y - u.y)*(p.y - u.y) <= p.s*p.s*t*t;
}
int main(){int T, cnt = 0, nx, ny;scanf("%d", &T);while(T--){for(int i = 0; i < MAXN; ++i) g[i].clear();scanf("%d", &t);scanf("%d", &nx);un = nx;for(int i = 1; i <= nx; ++i) scanf("%d%d%d", &pp[i].x, &pp[i].y, &pp[i].s);scanf("%d", &ny);for(int i = 1; i <= ny; ++i) scanf("%d%d", &up[i].x, &up[i].y);for(int x = 1; x <= nx; ++x)for(int y = 1; y <= ny; ++y) if(isconnected(pp[x], up[y])) g[x].push_back(y);printf("Scenario #%d:\n%d\n\n", ++cnt, MaxMatch());}return 0;
}