1 条题解
-
1
纪念一下,调了整整两周。
本题题意非常清晰,故不提供题意简述。
Solution
注意到 ,所以即使花 个点包住一棵树也是值的。所以我们考虑包住最多的树,这样一定是最优的。
所以我们对所有点求个凸包,然后对于每一棵树,如果它凸包所有边的同一侧,则它一定在凸包内,拿一个东西存下所有的树。
但是这样不一定是最优的,有一些点可能是无用的,删去之后仍然可以包住所有树。
我们考虑一个算法:对于凸包上的每相邻两条边(设为 ),我都枚举一次。如果这个三角形内部并没有树,那么我们就删掉 这个点。
这样复杂度非常优秀,达到了 。
但是很遗憾,正确性是错的。为什么呢?请看下面这个图:
最优的选择是保留 。但是,如果我们从 开始扫,你会发现 里根本就没有树,所以一开始就把 干掉了,怎么弄都得不到最优解。
看到 ,那我们就考虑一个暴力一些的算法。
先有一个结论:如果所有树出现在一个向量的同一侧,那么这个向量是有可能出现在最后的凸包内的。
所以我们暴力枚举任意两个点构成向量,如果合法我们就将这条边的边权赋为 ,否则设为正无穷。
然后就是一个 Floyd 求最小环问题了,时间复杂度 ,对于 的数据是非常松的。
当然,上面那个错误的做法,如果你对每个点都开始跑一遍,大概率是能得到最优解的,但是估计还是能 hack,这个我不太清楚,有点菜 qwq。
最后是一些阻碍了我很久的坑点:
- 最后的点不一定全是在一开始求的凸包内,所以建图的时候不能只枚举凸包上的点而不枚举凸包内部的点;
- 建图不要建双向边,因为向量带方向,反过来是不对的;
- 如果你 94 分,请注意一个问题:如果所有树都不在凸包内,最小代价显然是不选点,直接输出 。但是我们的 Floyd 是不允许不选点的,它会跑出来选两个点构成一个环。所以这种情况需要特判。
#include<bits/stdc++.h> using namespace std; const double eps = 1e-8; const int N = 100 + 10; int n, m, idx = -1, hd; int g[N][N]; struct node{ double x, y; } p[N], tree[N]; node st[N]; vector<int> inside; double getcro(node oo, node pp, node qq){ return (pp.x - oo.x) * (qq.y - oo.y) - (qq.x - oo.x) * (pp.y - oo.y); } double dis(node pp, node qq){ return sqrt((pp.x - qq.x) * (pp.x - qq.x) + (pp.y - qq.y) * (pp.y - qq.y)); } bool cmp(node a, node b){ double now = getcro(p[1], a, b);//叉积求面积 if(now < 0 || (now == 0 && dis(p[1], a) < dis(p[1], b))) return 1; return 0; } bool isleft(node u, node s, node t){ double f = getcro(u, s, t); return f >= eps; } bool possible(node u, node v){ for(int i=0;i<inside.size();i++){ node pp = tree[inside[i]]; if(!isleft(pp, v, u)) return 0; } return 1; } int main(){ scanf("%d%d", &n, &m); for(int i=1;i<=n;i++){ scanf("%lf%lf", &p[i].x, &p[i].y); if(idx == -1 || p[i].y < p[idx].y) idx = i; } for(int i=1;i<=m;i++) scanf("%lf%lf", &tree[i].x, &tree[i].y); swap(p[1], p[idx]); sort(p + 2, p + 1 + n, cmp); st[++hd] = p[1]; for(int i=2;i<=n;i++){ while(hd > 1 && !isleft(st[hd - 1], p[i], st[hd])) --hd; st[++hd] = p[i]; } int cnt = 0, ans = 1e9; st[++hd] = p[1]; for(int i=1;i<=m;i++){ bool f = 1; for(int j=hd;j>1;j--){ if(!isleft(st[j - 1], tree[i], st[j])){ f = 0; break; } } if(f) inside.push_back(i), ++cnt; } if(!cnt) return printf("%d\n", m * 111), 0; for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ node u = p[i], v = p[j]; if(i != j && possible(u, v)) g[i][j] = 1; else g[i][j] = 1e9; } } for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) g[i][j] = min(g[i][j], g[i][k] + g[k][j]); for(int i=1;i<=n;i++) ans = min(ans, g[i][i]); printf("%d\n", (m - cnt) * 111 + ans * 20); return 0; }
- 1
信息
- ID
- 1390
- 时间
- 1000ms
- 内存
- 64MiB
- 难度
- 9
- 标签
- (无)
- 递交数
- 14
- 已通过
- 3
- 上传者