bzoj4622 [NOI 2003] 智破连环阵

Description

B国在耗资百亿元之后终于研究出了新式武器——连环阵（Zenith Protected Linked Hybrid Zone）。传说中，连环阵是一种永不停滞的自发性智能武器。但经过A国间谍的侦察发现，连环阵其实是由M个编号为1，2，…，M的独立武器组成的。最初，1号武器发挥着攻击作用，其他武器都处在无敌自卫状态。以后，一旦第i（1<=i< M）号武器被消灭，1秒种以后第i+1号武器就自动从无敌自卫状态变成攻击状态。当第M号武器被消灭以后，这个造价昂贵的连环阵就被摧毁了。为了彻底打击B国科学家，A国军事部长打算用最廉价的武器——炸弹来消灭连环阵。经过长时间的精密探测，A国科学家们掌握了连环阵中M个武器的平面坐标，然后确定了n个炸弹的平面坐标并且安放了炸弹。每个炸弹持续爆炸时间为5分钟。在引爆时间内，每枚炸弹都可以在瞬间消灭离它平面距离不超过k的、处在攻击状态的B国武器。和连环阵类似，最初a1号炸弹持续引爆5分钟时间，然后a2号炸弹持续引爆5分钟时间，接着a3号炸弹引爆……以此类推，直到连环阵被摧毁。显然，不同的序列a1、a2、a3...消灭连环阵的效果也不同。好的序列可以在仅使用较少炸弹的情况下就将连环阵摧毁；坏的序列可能在使用完所有炸弹后仍无法将连环阵摧毁。现在，请你决定一个最优序列a1、a2、a3…使得在第ax号炸弹引爆的时间内连环阵被摧毁。这里的x应当尽量小

Input

第一行包含三个整数：M、n和k（1<=M, n<=100，1<=k<=1000），分别表示B国连环阵由M个武器组成，A国有n个炸弹可以使用，炸弹攻击范围为k。以下M行，每行由一对整数xi，yi（0<=xi，yi<=10000）组成，表示第i（1<=i<=M）号武器的平面坐标。再接下来n行，每行由一对整数ui，vi(0<=ui，vi<=10000)组成，表示第i（1<=i<=n）号炸弹的平面坐标。输入数据保证随机、无误、并且必然有解。

Output

一行包含一个整数x，表示实际使用的炸弹数.

Sample Input

Sample Input 1
4 3 6
0 6
6 6
6 0
0 0
1 5
0 3
1 1

Sample Input 2
10 10 45
41 67
34 0
69 24
78 58
62 64
5 45
81 27
61 91
95 42
27 36
91 4
2 53
92 82
21 16
18 95
47 26
71 38
69 12
67 99
35 94

Sample Output

Sample Output 1
2

Sample Output 2
5
HINT
输出数据为NOI原数据
输出数据由楼教主代码制作
原题有spj 此题去掉spj 只输出最优解

HINT

NOI2003 Day2 T3 感谢sxb_201上传

正解：搜索+$dp$+二分图最大匹配。

丧心病狂的$zjo$竟然把这题出成考试题。。我敢说这是我见过的最玄学的搜索题。。

首先，我们发现每个炸弹肯定炸一段连续的区间。那么有一个很直观的暴力的思路，那就是枚举区间。对于每个区间，能够完全覆盖的炸弹向它连边，跑一遍二分图最大匹配就行了。

这样显然是过不了的，所以我们要剪枝。我们假设每个炸弹可以重复使用，那么我们算出当前武器开始的所有武器最少还需几个炸弹才能消灭。

这个用$dp$来预处理。设$can[p][i][j]$表示$p$号炸弹，是否能够炸$[i,j]$这个区间。那么设$dis[i]$表示炸$[i,m]$需要的最少炸弹，易知$dis[i]=min(dis[j]+1)$，$i<j<=m+1$且$can[p][i][j-1]=1$，$dis[m+1]=0$。这个我们预处理就能得出了。

最优性剪枝：$now+dis[i]>=ans$则剪枝，$now$为当前炸弹数。

可行性剪枝：我们可以每次直接在原图的基础上进行增广，如果当前点不能进行增广，就不用再往下搜索了。

然而这些剪枝还是不足以通过全部数据，我们不妨从可行性剪枝上入手。

我们可以尝试求出当前区间右端点的最大值$maxl$，那么显然，$maxl$及其之前的端点都是可行的。

我们发现这样可以很大程度地优化时间。首先，我们可以从$maxl$到$l$依次枚举右端点，减少搜索量；其次，我们可以只进行一次增广，因为$can[p][i][j]>=can[p][i][j+1]$，那么右端点为$maxl$时连的边，在右端点减小时同样也会出现，并不会影响答案。

如何求出$maxl$？首先我们要求出辅助数组$maxt[p][l]$，表示炸弹$p$从$l$开始能炸到的最远的点的编号，这个很容易预处理出来，就不再赘述。

注意到匈牙利算法的过程，一个炸弹能够使用有两种情况。首先是这个炸弹没有出现在匹配边上；其次是这个炸弹虽然出现在匹配边上，但是它能够通过增广以后和当前区间匹配。那么我们就可以使用$bfs$来解决这个问题，求出所有能够使用的炸弹(具体操作看代码吧。。)，然后不断地取$maxt[p][l]$的最大值，就能求出$maxl$了。

这就是本题的两个重要剪枝，加上这两个剪枝以后极限数据也可以瞬间求解了。

 //It is made by wfj_2048~

 #include <algorithm>

 #include <iostream>

 #include <cstring>

 #include <cstdlib>

 #include <cstdio>

 #include <vector>

 #include <cmath>

 #include <queue>

 #include <stack>

 #include <map>

 #include <set>

 #define inf (1<<30)

 #define N (110)

 #define il inline

 #define RG register

 #define ll long long

 #define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)

 using namespace std;

 int can[N][N][N],maxt[N][N],g[N][N],dis[N],vis[N],lk[N],mt[N],x[N],y[N],u[N],v[N],q[N],n,m,k,cnt,ans;

 il int gi(){

     RG int x=,q=; RG char ch=getchar();

     while ((ch<'' || ch>'') && ch!='-') ch=getchar();

     if (ch=='-') q=-,ch=getchar();

     while (ch>='' && ch<='') x=x*+ch-,ch=getchar();

     return q*x;

 }

 il void pre(){

     for (RG int i=;i<=m;++i) x[i]=gi(),y[i]=gi();

     for (RG int i=;i<=n;++i){

     u[i]=gi(),v[i]=gi();

     for (RG int j=;j<=m;++j)

         g[i][j]=(u[i]-x[j])*(u[i]-x[j])+(v[i]-y[j])*(v[i]-y[j])<=k*k;

     }

     for (RG int p=;p<=n;++p){

     for (RG int i=;i<=m;++i) can[p][i][i]=g[p][i],maxt[p][i]=g[p][i]?i:i-;

     for (RG int i=;i<m;++i)

         for (RG int j=i+;j<=m;++j){

         can[p][i][j]=can[p][i][j-]&g[p][j];

         if (can[p][i][j]) maxt[p][i]=j;

         }

     }

     for (RG int i=m;i;--i){

     dis[i]=inf;

     for (RG int j=i;j<=m;++j)

         for (RG int p=;p<=n;++p)

         if (can[p][i][j]) dis[i]=min(dis[i],dis[j+]+);

     }

     return;

 }

 il int hungry(RG int x){

     for (RG int v=;v<=n;++v){

     if (!g[x][v] || vis[v]==cnt) continue; vis[v]=cnt;

     if (!lk[v] || hungry(lk[v])){ mt[x]=v,lk[v]=x; return ; }

     }

     return ;

 }

 il void dfs(RG int l,RG int id){

     if (l>m){ ans=id-; return; } if (id-+dis[l]>=ans) return;

     ++cnt; RG int LK[N],MT[N],h=,t=,maxl=l-;

     for (RG int i=;i<=n;++i) if (!lk[i]) vis[i]=cnt,q[++t]=i;

     while (h<t){

     RG int x=q[++h]; maxl=max(maxl,maxt[x][l]);

     for (RG int i=;i<id;++i)

         if (g[i][x] && vis[mt[i]]!=cnt) vis[mt[i]]=cnt,q[++t]=mt[i];

     }

     memcpy(LK,lk,sizeof(LK)),memcpy(MT,mt,sizeof(MT));

     for (RG int i=;i<=n;++i) g[id][i]=can[i][l][maxl]; ++cnt,hungry(id);

     for (RG int r=maxl;r>=l;--r){

     for (RG int i=;i<=n;++i) g[id][i]=can[i][l][r]; dfs(r+,id+);

     }

     memcpy(lk,LK,sizeof(lk)),memcpy(mt,MT,sizeof(mt)); return;

 }

 il void work(){

     m=gi(),n=gi(),k=gi(),pre(),ans=n;

     dfs(,),printf("%d\n",ans); return;

 }

 int main(){

     File("boom");

     work();

     return ;

 }

巴特西