CH - 6803 导弹防御塔(二分图最大匹配-多重匹配(拆点法))

题目链接：点击查看

题目大意：给出n个炮塔，再给出m个敌人，每个炮塔都可以持续发射导弹，不过发射导弹的时间是t1秒，炮塔冷却的时间是t2分钟，炮弹飞行的速度是v，炮塔和敌人之间的距离按照欧几里得距离计算，现在要求清除完所有敌人的最小时间（分钟）

题目分析：因为这个题目满足二分的基本条件，也就是在时间比较大的时候，也肯定是可以清除掉所有敌人的，所以我们可以二分一下清除所有敌人所用的时间，现在的问题就转换成了如何判断当前的答案是否合理了，很显然这个题目是一个二分图多重匹配的题目，因为每个炮塔可以和多个敌人匹配，但是又不是简单的多重匹配，因为每一个导弹的时间开销都是互不相同的，我们必须保证每一个导弹在击中敌人的时候，时间还在二分的答案范围内才行，这样我们可以预处理出每一个导弹发射的时间，然后每次检查答案的时候，我们需要重新建边，建好边后跑一下匈牙利就可以判断答案的合理性了

因为这个题目的多重匹配对于炮塔而言，每一次的时间状态都是互不相同的，所以这个题目我们选择用拆点法来处理，将每一个炮塔拆成m个点来处理即可（因为最坏情况是一个炮塔发射了m颗导弹），然后实现就可以了

代码：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=55;const double eps=1e-8;int n,m;double t1,t2,v;struct Pos {int x,y; }a[N],b[N];//a:敌人 b:炮塔 double dis(Pos& a,Pos& b) {return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); }struct Node {double time;int id; }c[N*N];int cnt;bool maze[N*N][N*N],vis[N*N];int match[N*N];bool dfs(int x) {for(int i=1;i<=cnt;i++){if(maze[x][i]&&!vis[i]){vis[i]=true;if(!match[i]||dfs(match[i])){match[i]=x;return true;}}}return false; }bool check(double mid) {memset(maze,false,sizeof(maze));memset(match,0,sizeof(match));for(int i=1;i<=m;i++)//根据当前二分的mid建边，边权必须满足小于等于midfor(int j=1;j<=cnt;j++){if(dis(a[i],b[c[j].id])/v+c[j].time<=mid)maze[i][j]=true;}for(int i=1;i<=m;i++){memset(vis,false,sizeof(vis));if(!dfs(i))return false;}return true; }int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);scanf("%d%d%lf%lf%lf",&n,&m,&t1,&t2,&v);t1/=60;//注意这里，是个小坑，给出的t1单位是秒for(int i=1;i<=m;i++)scanf("%d%d",&a[i].x,&a[i].y);for(int i=1;i<=n;i++)scanf("%d%d",&b[i].x,&b[i].y);for(int i=1;i<=n;i++)//枚举炮塔 for(int j=1;j<=m;j++)//枚举第几个导弹 (最多用一个炮塔发射m颗导弹就够了){c[++cnt].id=i;c[cnt].time=(j-1)*(t1+t2)+t1; } double l=0,r=1e5;while(fabs(l-r)>=eps)//二分答案{double mid=(l+r)/2;if(check(mid))r=mid;elsel=mid;}printf("%.6f\n",r);return 0; }

 

总结

以上是生活随笔为你收集整理的CH - 6803 导弹防御塔(二分图最大匹配-多重匹配(拆点法))的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。