AcWing374 导弹防御塔

二分图

此题看书的时候觉得特别难，实际的代码却非常简单

现在分析是什么让代码如此简单的：

1. 首先预处理出第i个防御塔发射第j个导弹的时间（计算发射时间，不计冷却时间）

2. 二分答案，判断时间mid内能否解决问题

3. 利用vector建边，不用管标号的冲突，在二分图中十分方便（一般网络流可能就没办法了）

时间复杂度：\(O(n^4*log(T))\) 实际更快

#include
using namespace std;#define go(i,a,b) for(int i=a;i<=b;++i)
#define com(i,a,b) for(int i=a;i>=b;--i)
#define mem(a,b) memset(a,b,sizeof(a))const int inf=0x3f3f3f3f,N=60,M=2510;
const double eps=1e-8;
typedef long long ll;int n,m,v,match[M],tot;
bool vis[M];
double t1,t2;
vectore[N];
struct node{double x,y;
}a[N],b[N];
struct new_node{int id;double t;
}c[M];bool dfs(int u){for(int i=0;ieps){double mid=(l+r)*0.5;if(pd(mid)) r=mid;else l=mid;}printf("%.6lf",r);return 0;
}

转载于:https://www.cnblogs.com/White-star/p/11526325.html

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！