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