shoi2012 day2（想看T2的算了吧我也不会）

T1(bzoj2834) 【问题描述】 回家的路 【问题描述】 2046 年 OI 城的城市轨道交通建设终于全部竣工，由于前期规划周密，建成 后的轨道交通网络由 2n 条地铁线路构成，组成了一个 n 纵 n 横的交通网。如下 图所示，这 2n 条线路每条线路都包含 n 个车站，而每个车站都在一组纵横线路 的交汇处。 出于建设成本的考虑，并非每个车站都能够进行站内换乘，能够进行站内换 乘的地铁站共有 m 个，在下图中，标上方块标记的车站为换乘车站。已知地铁 运行 1 站需要 2 分钟，而站内换乘需要步行 1 分钟。Serenade 想要知道，在不中 途出站的前提下，他从学校回家最快需要多少时间（等车时间忽略不计）。   【输入格式】 第一行有两个整数 n, m。 接下去 m 行每行两个整数 x, y，表示第 x 条横向线路与第 y 条纵向线路的交 汇站是站内换乘站。 接下去一行是四个整数 x1, y1, x2, y2。表示 Serenade 从学校回家时，在第 x1 条横向线路与第 y1 条纵向线路的交汇站上车，在第 x2 条横向线路与第 y2条纵向 线路的交汇站下车。 【输出格式】 输出文件置有一行，即 Serenade 在合理选择线路的情况下，回家所需要的 时间。如果 Serenade 无法在不出站换乘的情况下回家，请输出-1。 【输入样例 1】 2 1 1 2 1 1 2 2 【输出样例 1】 5 【输入样例 2】 6 9 2 1 2 5 3 2 4 4 5 2 5 6 6 1 6 3 6 4 1 1 4 6 【输出样例 2】 27 【输入样例 3】 6 10 2 1 2 5 3 2 4 4 5 2 5 6 6 1 6 3 6 4 6 6 1 1 4 6 【输出样例 3】 26 【数据规模】 对于 30%的数据，n ≤ 50, m ≤ 1000； 对于 60%的数据，n ≤ 500, m ≤ 2000； 对于 100%的数据，n ≤ 20000, m ≤ 100000； 【题解】 因为只有在100000+2（起，终）点对我们而言是有用的，所以拿这m+2个点建图，距离就是物理距离*2，这里思维转变一下，本来是转弯（此时有必要换乘）时才会去换乘（否则我就一路坐到底），那么只有换方向时才需要+1的换乘时间。dp[m+2][2]表示我现在哪个点，是通过哪个方向坐到这里来的。那么下一转如果同方向就直接加距离即可，否则就要加距离再加1，然后带着这个dp去做spfa即可。 【代码】 #include<iostream> #include<string.h> #include<math.h> #include<algorithm> #include<stdio.h> #include<queue> using namespace std; typedef long long ll; const int V=100050; const int E=400050; const ll INF=0x7f7f7f7f; int head[V],to[E*2],next[E*2],cnt; ll v[E*2]; void add(int f,int t,ll val) { next[++cnt]=head[f]; v[cnt]=val; to[cnt]=t; head[f]=cnt; } ll dis[V][2]; int n,m; struct dian { int x,y; int num; }point[V],point2[V],point3[V]; int cmp1(dian a,dian b) { if(a.x==b.x) return a.y<b.y; return a.x<b.x; } int cmp2(dian a,dian b) { if(a.y==b.y) return a.x<b.x; return a.y<b.y; } struct state { int loc; bool fang; }; int qix,qiy; int zhx,zhy; bool vis[V][2]; queue<state> q; void spfa() { for(int i=2;i<=m;i++) dis[i][1]=dis[i][0]=INF; dis[1][1]=dis[1][0]=0; vis[1][0]=vis[1][1]=1; q.push((state){1,0}); q.push((state){1,1}); while(!q.empty()) { state now=q.front(); q.pop(); vis[now.loc][now.fang]=0; for(int i=head[now.loc];i!=-1;i=next[i]) { if(point[to[i]].x==point[now.loc].x) { ll zhuan= now.fang==1?dis[now.loc][now.fang]+v[i]:dis[now.loc][now.fang]+v[i]+1; if(dis[to[i]][1]>zhuan) { dis[to[i]][1]=zhuan; if(!vis[to[i]][1]) { q.push((state){to[i],1}); vis[to[i]][1]=1; } } } else { ll zhuan= now.fang==0?dis[now.loc][now.fang]+v[i]:dis[now.loc][now.fang]+v[i]+1; if(dis[to[i]][0]>zhuan) { dis[to[i]][0]=zhuan; if(!vis[to[i]][0]) { q.push((state){to[i],0}); vis[to[i]][0]=1; } } } } } ll ans=min(dis[m][1],dis[m][0]); for(int i=head[m];i!=-1;i=next[i]) if(point[to[i]].x==point[m].x&&point[to[i]].y==point[m].y) ans=min(ans,min(dis[to[i]][1],dis[to[i]][0])); ans= ans==INF?-1:ans; printf("%lld\n",ans); } int cnt1=1; int main() { // freopen("gohome.in","r",stdin); // freopen("gohome.ans","w",stdout); memset(head,-1,sizeof(head)); scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) scanf("%d%d",&point3[i].x,&point3[i].y); scanf("%d%d",&qix,&qiy); scanf("%d%d",&zhx,&zhy); if(qix==zhx) { printf("%d\n",abs(zhy-qiy)*2); return 0; } if(qiy==zhy) { printf("%d\n",abs(zhx-qiy)*2); return 0; } sort(point3+1,point3+m+1,cmp1); point[++cnt1]=point3[1]; for(int i=2;i<=m;i++) if((point3[i].x!=point3[i-1].x||point3[i].y!=point3[i-1].y)&&(point3[i].x!=qix||point3[i].y!=qiy)&&(point3[i].x!=zhx||point3[i].y!=zhy)) point[++cnt1]=point3[i]; m=cnt1; for(int i=2;i<=m;i++) point[i].num=i,point2[i]=point[i]; point[1].x=qix,point[1].y=qiy,point[1].num=1,point2[1]=point[1]; point[m+1].x=zhx,point[m+1].y=zhy,point[m+1].num=m+1,point2[m+1]=point[m+1]; m+=1; sort(point2+1,point2+m+1,cmp1); for(int i=1;i<=m;i++) if(point2[i].x==point2[i-1].x&&i!=1) add(point2[i].num,point2[i-1].num,(ll)(point2[i].y-point2[i-1].y)*2),add(point2[i-1].num,point2[i].num,(ll)(point2[i].y-point2[i-1].y)*2); sort(point2+1,point2+m+1,cmp2); for(int i=1;i<=m;i++) if(point2[i].y==point2[i-1].y&&i!=1) add(point2[i].num,point2[i-1].num,(ll)(point2[i].x-point2[i-1].x)*2),add(point2[i-1].num,point2[i].num,(ll)(point2[i].x-point2[i-1].x)*2); spfa(); } T2 不会。。。不敢误人子弟 T3 【问题描述】 Harry Potter 新学了一种魔法：可以让改变树上的果子个数。满心欢喜的他 找到了一个巨大的果树，来试验他的新法术。 这棵果树共有