題目大意：

有n個城市，有一部分是A國的，有一部分是B國的（小于A國的），A國每個城市都有一枚導彈（只有一枚），炸毀別的城市的時間是到這個城市的距離，請問A國最快要多久可以炸毀B國所有城市

---

解題思路：

先用Floyed來求出最短路，然后二分枚舉答案再用匈牙利算法確認是否可以，即可

---

代碼

#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> using namespace std; int bg[105],head[105],a[105][105],b[105],c[105],w,sum,l,r,mid,n,m,nm; bool pd[105]; struct rec {int to,next; }f[10005];//每一條路線 bool js(int xx) {int l=0;for (int i=head[xx];i;i=f[i].next)//連接此點的每一條線if (!pd[f[i].to])//可以搶{l=bg[f[i].to];//之前是誰打的bg[f[i].to]=xx;//代替pd[f[i].to]=true;//不能搶了if ((!l)||(js(l))) return true;//之前沒人或搶到了bg[f[i].to]=l;//沒法打這個城市就還給之前的}return false;//找不到可以打的 } bool sj(int now) {memset(head,0,sizeof(head));//清零memset(bg,0,sizeof(bg));//清零w=0;//清零sum=0;//清零for (int i=1;i<=n;i++)for (int j=1;j<=m;j++)if (a[b[i]][c[j]]<=now)//判斷是否少于當前的時間{f[++w].to=j;//下一個點f[w].next=head[i];//下一條線head[i]=w;//這個點的第一條線} for (int i=1;i<=n;i++){memset(pd,false,sizeof(pd));//清零if (js(i)) sum++;//判斷是否能打到敵人}return sum==m;//判斷是否打完 } int main() {scanf("%d",&nm);for (int i=1;i<=nm;i++)for (int j=1;j<=nm;j++)scanf("%d",&a[i][j]);for (int k=1;k<=nm;k++)for (int i=1;i<=nm;i++)for (int j=1;j<=nm;j++)if ((i!=j)&&(j!=k)&&(k!=i)&&(a[i][k]+a[k][j]<a[i][j]))a[i][j]=a[i][k]+a[k][j];//Floyedscanf("%d",&n);for (int i=1;i<=n;i++)scanf("%d",&b[i]);scanf("%d",&m);for (int i=1;i<=m;i++)scanf("%d",&c[i]);l=1;r=10000;while(l<=r){mid=(l+r)/2;//二分答案if (sj(mid)) r=mid-1;else l=mid+1;}printf("%d",l);//輸出return 0; }

總結

以上是生活随笔為你收集整理的【Floyed】【匈牙利算法】导弹（jzoj 1610）的全部內容，希望文章能夠幫你解決所遇到的問題。

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