WC 2007 racing jsb 两题

概述关于石头剪刀布和Racing那题题解很清晰，所以就不多说了。 但是，racing这一题竟然卡SPFA，吐槽不能。。。。。。 还有关于racing为什么是从赛道上一点走到另一赛道端点而不是中间某点的证明请看题解PPT的第11张(相信很多人都木有认真看题解) Code jsb racing(SPFA 60分,懒得改了) #include<cstdio>#include<cstdlib>#inclu

关于石头剪刀布和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;}

总结

以上是内存溢出为你收集整理的WC 2007 racing jsb 两题全部内容，希望文章能够帮你解决WC 2007 racing jsb 两题所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。