WC 2007 racing jsb 两题

前端之家收集整理的这篇文章主要介绍了WC 2007 racing jsb 两题前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

关于石头剪刀布和Racing那题题解很清晰,所以就不多说了。

但是,racing这一题竟然卡SPFA,吐槽不能。。。。。。

还有关于racing为什么是从赛道上一点走到另一赛道端点而不是中间某点的证明请看题解PPT的第11张(相信很多人都木有认真看题解)

Code

jsb racing(SPFA 60分,懒得改了)

#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
bool vis[20005];
int next[2000005],w[2000005],now[20005],head[20005],d[20005],pre[20005],sta[200005],que[200005],c[2000005],link[2000005],n=0,nn=0,m=0,e=1,top=0;
bool spfa()
{
  memset(d,60,sizeof(d));
  memset(vis,sizeof(vis));
  memset(pre,sizeof(pre));
  int oo=d[0]-1;
  sta[1]=n-1;
  int top=0,tail=1,x=0,y=0,ne=0;
  d[n-1]=0;
  vis[n-1]=1;
  while (top<tail)
    {
      x=sta[++top];
      for (ne=head[x];ne;ne=next[ne])
	if (w[ne] && d[x]+c[ne]<d[link[ne]])
	  {
	    y=link[ne];
	    d[y]=d[x]+c[ne];
	    pre[y]=x;
	    now[y]=ne;
	    if (!vis[y])
	      {
		sta[++tail]=y;
		vis[y]=1;
	      }
	  }
      vis[x]=0;
    }
  if (d[n]<oo) return 1;
  else
    return 0;
}
int getcost()
{
  int nowp=0,flows=1,ctot=0;
  for (nowp=n;nowp!=n-1;nowp=pre[nowp])
    {
      w[now[nowp]]-=flows;
      w[now[nowp]^1]+=flows;
      ctot+=(flows*c[now[nowp]]);
    }
  return ctot;
}
int mincost()
{
  int cost=0;
  while (spfa())
    cost+=getcost();
  return cost;
}
void push(int u,int v)
{
  sta[++top]=u;
  que[top]=v;
}
void add(int u,int v,int ww,int cc)
{
  next[++e]=head[u];
  head[u]=e;
  link[e]=v;
  w[e]=ww;
  c[e]=cc;
  next[++e]=head[v];
  head[v]=e;
  link[e]=u;
  c[e]=-cc;
}
int main()
{
  freopen("jsb.in","r",stdin);
  freopen("jsb.out","w",stdout);
  scanf("%d",&nn);
  int i=0,j=0,tmp=0,mtot=0;
  n=nn;
  for (i=1;i<=nn;i++)
    for (j=1;j<=nn;j++)
      {
	scanf("%d",&tmp);
	if (tmp==1)
	  {
	    d[j]++;
	    mtot++;
	  }
	else
	  if (tmp==2 && i<j)
	    {
	      push(i,j);
	      mtot++;
	    }
      }
  int cost=0;
  for (i=1;i<=nn;i++) 
    cost+=d[i]*d[i];
  int nowd=0;
  for (i=1;i<=top;i++)
    {
      ++n;
      add(n,sta[i],1,0);
      add(n,que[i],0);
    }
  for (++n,i=nn+1;i<n;i++)
    add(n,i,0);
  for (++n,i=1;i<=nn;i++)
    for (nowd=d[i];nowd<=nn;nowd++)
      add(i,n,2*nowd+1);
  cost+=mincost();
  int ans=nn*(nn-1)/2*(nn-2)/3-(cost-mtot)/2;
  printf("%d",ans);
  return 0;
}
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
const double eps=1e-8;
double x[1005*1005],y[1005*1005],w[2005*2005],d[1005*1005];
int next[2005*2005],head[1005*1005],link[1005*1005],c[1005];
int esum=0,node=0,n=0;
double va=0,vb=0;
int sta[4005*4005];
bool vis[1005*1005];
double dis(double x,double y,double xx,double yy)
{
 return sqrt((x-xx)*(x-xx)+(y-yy)*(y-yy));
}
int cmp(const void *a,const void *b)
{
 double tmp=x[*(int *)a]+y[*(int *)a]-x[*(int *)b]-y[*(int *)b];
 if (fabs(tmp)<eps)
  return 0;
 else
  if (tmp>0) return 1;
   else return -1;
}
void add(int u,double &vv)
{
 double d=dis(x[u],y[u],x[v],y[v])/vv;
 next[++esum]=head[u];
 head[u]=esum;
 link[esum]=v;
 w[esum]=d;
 next[++esum]=head[v];
 head[v]=esum;
 link[esum]=u;
 w[esum]=d;
}
void dit(double p,double q,double &xx,double &yy,int i,int j)
{
 double left=0,right=1,mid1=0,mid2=0,x1=0,y1=0,x2=0,y2=0,d1=0,d2=0;
 tmp=dis(x[i],y[i],x[i-1],y[i-1])/va;
 while (left+eps<right)
  {
   mid1=left+(right-left)/3;
   mid2=left+(right-left)*2/3;
   x1=x[i-1]+(x[i]-x[i-1])*mid1;
   x2=x[i-1]+(x[i]-x[i-1])*mid2;
   y1=y[i-1]+(y[i]-y[i-1])*mid1;
   y2=y[i-1]+(y[i]-y[i-1])*mid2;
   d1=dis(x[j],y[j],x1,y1)/vb+tmp*(p+q*mid1);
   d2=dis(x[j],x2,y2)/vb+tmp*(p+q*mid2);
   if (d1<d2)
    right=mid2;
   else
    left=mid1;
  }
 xx=x1;
 yy=y1;
}
int main()
{
 freopen("racing.in",stdin);
 freopen("racing.out",stdout);
 scanf("%d",&n);++n;
 scanf("%lf%lf",&va,&vb);
 int i=0,j=0;
 for (i=2;i<=n;i++)
  scanf("%lf%lf",&x[i],&y[i]);
 int nn=n,top=0;
 for (i=2;i<=nn;i++)
  {
   top=2;
   c[1]=i-1;c[2]=i;
   for (j=1;j<=nn;j++)
     {
      if (j<i) add(i,j,vb);
      ++n;
      dit(0,x[n],y[n],j);
      c[++top]=n;
      add(j,vb);
      ++n;
      dit(1,-1,vb);
     }
   qsort(c+1,top,sizeof(c[0]),cmp);
   for (j=2;j<=top;j++)
    add(c[j-1],c[j],va);
  }
 int ne=0,xx=0,yy=0;
 d[1]=0;
 for (i=2;i<=n;i++) d[i]=1e10;
 top=0;
 int tail=1;
 sta[1]=1;vis[1]=1;
 while (top<tail)
  {
   xx=sta[++top];
   ne=head[xx];
   while (ne)
    {
     yy=link[ne];
     if (d[yy]>d[xx]+w[ne])
      {
       d[yy]=d[xx]+w[ne];
       if (!vis[yy])
        {
         sta[++tail]=yy;
         vis[yy]=1;
        }
      }
     ne=next[ne];
    }
   vis[xx]=0;
  }
 printf("%.6f",d[nn]);
 return 0;
}
原文链接:https://www.f2er.com/vb/260272.html

猜你在找的VB相关文章