「Poetize3」导弹防御塔

描述 Description

Freda控制着N座可以发射导弹的防御塔。每座塔都有足够数量的导弹，但是每座塔每次只能发射一枚。在发射导弹时，导弹需要T1秒才能从防御塔中射出，而在发射导弹后，发射这枚导弹的防御塔需要T2分钟来冷却。
所有导弹都有相同的匀速飞行速度V，并且会沿着距离最短的路径去打击目标。计算防御塔到目标的距离Distance时，你只需要计算水平距离，而忽略导弹飞行的高度。导弹在空中飞行的时间就是 (Distance/V) 分钟，导弹到达目标后可以立即将它击毁。
现在，给出N座导弹防御塔的坐标，M个入侵者的坐标，T1、T2和V，你需要求出至少要多少分钟才能击退所有的入侵者。

题解：
不太好想。

二分时间+二分图匹配

因为每个塔打每个敌人的时间点不同，能否达到也不同，而我们发现这个时间点只取决于这个该塔发射的第几次导弹。

所以我们把每个点拆成m个点，分别表示这个塔的第 i 发导弹，然后就可以根据当前时间+到达时间是不是小于二分的这个时间来建图。

用匈牙利求最大匹配，如果为m说明可行，缩小上界，否则缩小下界。

打的时候出现了出现了几个错误：

1）没有清空v数组

2）题目输入坑爹，t1的单位是s，其他的单位都是分钟。。。

3）。。。

现在还没有A掉，不过实在受不鸟了。。。

代码；

  1 #include<cstdio>
  2 
  3 #include<cstdlib>
  4 
  5 #include<cmath>
  6 
  7 #include<cstring>
  8 
  9 #include<algorithm>
 10 
 11 #include<iostream>
 12 
 13 #include<vector>
 14 
 15 #include<map>
 16 
 17 #include<set>
 18 
 19 #include<queue>
 20 
 21 #include<string>
 22 
 23 #define inf 1000000000
 24 
 25 #define maxn 200
 26 
 27 #define maxm 200
 28 
 29 #define eps 1e-10
 30 
 31 #define ll long long
 32 
 33 #define pa pair<int,int>
 34 
 35 #define for0(i,n) for(int i=0;i<=(n);i++)
 36 
 37 #define for1(i,n) for(int i=1;i<=(n);i++)
 38 
 39 #define for2(i,x,y) for(int i=(x);i<=(y);i++)
 40 
 41 #define for3(i,x,y) for(int i=(x);i>=(y);i--)
 42 
 43 #define mod 1000000007
 44 #define sqr(x) (x)*(x)
 45 #define num(x,y) (x-1)*(m)+y
 46 
 47 using namespace std;
 48 
 49 inline int read()
 50 
 51 {
 52 
 53     int x=0,f=1;char ch=getchar();
 54 
 55     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
 56 
 57     while(ch>='0'&&ch<='9'){x=10*x+ch-'0';ch=getchar();}
 58 
 59     return x*f;
 60 
 61 }
 62 int n,m,v[maxn*maxn],p[maxn*maxn];
 63 double t1,t2,vv,t[maxn][maxn],d[maxn];
 64 bool f[maxn*maxn][maxn];
 65 struct rec{double x,y;}a[maxn],b[maxn];
 66 inline bool find(int x,int y)
 67 {
 68     for1(i,n*m)
 69      if(f[x][i]&&v[i]!=y)
 70      {
 71          v[i]=y;
 72          if(p[i]==0||find(p[i],y))
 73          {
 74              p[i]=x;
 75              return 1;
 76          }
 77      }
 78     return 0;
 79 }
 80 bool check(double x)
 81 {
 82     int ans=0;//cout<<x<<endl;
 83     memset(f,0,sizeof(f));memset(p,0,sizeof(p));memset(v,0,sizeof(v));
 84     for1(i,m)
 85      for1(j,n)
 86       for1(k,m)
 87         if(d[k]+t[j][i]<=x)f[i][num(j,k)]=1;
 88     for1(i,m)if(find(i,i))ans++;
 89     //cout<<ans<<endl;    
 90     return ans==m;
 91 }
 92 
 93 int main()
 94 
 95 {
 96 
 97     freopen("input.txt","r",stdin);
 98 
 99     freopen("output.txt","w",stdout);
100 
101     n=read();m=read();t1=read();t2=read();vv=read();t1/=60;
102     for1(i,m)b[i].x=read(),b[i].y=read();
103     for1(i,n)a[i].x=read(),a[i].y=read();
104     for1(i,n)
105      for1(j,m)
106       t[i][j]=sqrt((sqr(a[i].x-b[j].x)+sqr(a[i].y-b[j].y)))/vv;
107     for1(i,m)d[i]=t1*i+t2*(i-1);
108     double l=0,r=inf,mid;
109     while(r-l>1e-9)
110     {
111         mid=(l+r)/2;
112         //printf("%lf %lf %lf
",l,mid,r);
113         if(check(mid))r=mid;else l=mid;
114     }
115     printf("%.6lf",l);
116 
117     return 0;
118 
119 }

View Code

数组开小查了一天啊！！！！！！！！！！！！！！！！！！！！！！！！！！！1

怎么这么容易反sb错误。。。。。。。

我是不是没救了TAT

代码：

  1 #include<cstdio>
  2 
  3 #include<cstdlib>
  4 
  5 #include<cmath>
  6 
  7 #include<cstring>
  8 
  9 #include<algorithm>
 10 
 11 #include<iostream>
 12 
 13 #include<vector>
 14 
 15 #include<map>
 16 
 17 #include<set>
 18 
 19 #include<queue>
 20 
 21 #include<string>
 22 
 23 #define inf 1000000000
 24 
 25 #define maxn 200
 26 
 27 #define maxm 200
 28 
 29 #define eps 1e-10
 30 
 31 #define ll long long
 32 
 33 #define pa pair<int,int>
 34 
 35 #define for0(i,n) for(int i=0;i<=(n);i++)
 36 
 37 #define for1(i,n) for(int i=1;i<=(n);i++)
 38 
 39 #define for2(i,x,y) for(int i=(x);i<=(y);i++)
 40 
 41 #define for3(i,x,y) for(int i=(x);i>=(y);i--)
 42 
 43 #define mod 1000000007
 44 #define sqr(x) (x)*(x)
 45 #define num(x,y) (x-1)*(m)+y
 46 
 47 using namespace std;
 48 
 49 inline int read()
 50 
 51 {
 52 
 53     int x=0,f=1;char ch=getchar();
 54 
 55     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
 56 
 57     while(ch>='0'&&ch<='9'){x=10*x+ch-'0';ch=getchar();}
 58 
 59     return x*f;
 60 
 61 }
 62 int n,m,v[maxn*maxn],p[maxn*maxn];
 63 double t1,t2,vv,t[maxn][maxn],d[maxn];
 64 bool f[maxn][maxn*maxn];
 65 struct rec{double x,y;}a[maxn],b[maxn];
 66 inline bool find(int x,int y)
 67 {
 68     for1(i,n*m)
 69      if(f[x][i]&&v[i]!=y)
 70      {
 71          v[i]=y;
 72          if(p[i]==0||find(p[i],y))
 73          {
 74              p[i]=x;
 75              return 1;
 76          }
 77      }
 78     return 0;
 79 }
 80 bool check(double x)
 81 {
 82     int ans=0;
 83     memset(f,0,sizeof(f));memset(p,0,sizeof(p));memset(v,0,sizeof(v));
 84     for1(i,m)
 85      for1(j,n)
 86       for1(k,m)
 87         if(d[k]+t[j][i]<=x)f[i][num(j,k)]=1;
 88     for1(i,m)if(find(i,i))ans++;    
 89     return ans==m;
 90 }
 91 
 92 int main()
 93 
 94 {
 95 
 96     freopen("input.txt","r",stdin);
 97 
 98     freopen("output.txt","w",stdout);
 99 
100     n=read();m=read();t1=read();t2=read();vv=read();t1/=60;
101     for1(i,m)b[i].x=read(),b[i].y=read();
102     for1(i,n)a[i].x=read(),a[i].y=read();
103     for1(i,n)
104      for1(j,m)
105       t[i][j]=sqrt((sqr(a[i].x-b[j].x)+sqr(a[i].y-b[j].y)))/vv;
106     for1(i,m)d[i]=(i-1)*(t1+t2)+t1;
107     double l=0,r=inf,mid;
108     while(r-l>1e-9)
109     {
110         mid=(l+r)/2;
111         if(check(mid))r=mid;else l=mid;
112     }
113     printf("%.6lf",l);
114 
115     return 0;
116 
117 }

View Code