2 条题解
-
0
#include <bits/stdc++.h> using namespace std; int match[110], chw[110], tsp; vector<int> G[110]; bool findmuniu(int x) { for(int y : G[x]) { if(chw[y] != tsp) { chw[y] = tsp; if(match[y] == 0 || findmuniu(match[y]) == 1) { match[y] = x; return 1; } } } return 0; } struct node{double x, y;}A[110], B[110]; double dis(node n1, node n2){return sqrt( (n1.x - n2.x)*(n1.x - n2.x) + (n1.y - n2.y)*(n1.y - n2.y) );} int main() { int n, m; double s, v; while(scanf("%d%d%lf%lf", &n, &m, &s, &v) != EOF) { for(int i = 1; i <= n; i++) scanf("%lf%lf", &A[i].x, &A[i].y); for(int i = 1; i <= m; i++) scanf("%lf%lf", &B[i].x, &B[i].y); memset(G, 0, sizeof(G)); for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) if(dis(A[i], B[j]) <= s * v) G[i].emplace_back(j); int ans = 0; memset(match, 0, sizeof(match)); memset(chw, 0, sizeof(chw)); for(int i = 1; i <= n; i++) { tsp = i; if(findmuniu(i) == 1) ans++; } printf("%d\n", n - ans); } return 0; }
- 1
信息
- ID
- 317
- 时间
- 2000ms
- 内存
- 128MiB
- 难度
- 8
- 标签
- 递交数
- 380
- 已通过
- 68
- 上传者