題目鏈接：點擊查看

題目大意：給出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 导弹防御塔(二分图最大匹配-多重匹配(拆点法))的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。