网站建设 锋云科技,重庆建筑信息工程官网,网站设计书籍,中小企业网站建设济南兴田德润厉害吗一.分层图问题#xff08;单源传送#xff09;
#xff08;1#xff09;题目
P4568 [JLOI2011] 飞行路线 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
#xff08;2#xff09;思路
可知背景就是求最短路问题#xff0c;但难点是可以使一条路距离缩短至0#xf…一.分层图问题单源传送
1题目
P4568 [JLOI2011] 飞行路线 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
2思路
可知背景就是求最短路问题但难点是可以使一条路距离缩短至0那如何更好的利用这个机会呢
此时我们可以用到分层图如下 即我们可以免费往下传一次其实也就相当于两点距离为0了这时终点应该9号节点。
于是建图如下 add(u(j-1)*n,vj*n,0);add(v(j-1)*n,uj*n,0);add(uj*n,vj*n,w);add(vj*n,uj*n,w);
第一个是从上到下是使用传送的边
第二个是第一个的逆向
第三个是已经用过一次机会已经在下面了所以正常边
第四个是第三个的逆向 for(int j1;jk;j){add(s(j-1)*n,sj*n,0);}
这个是特殊情况起点即终点一路传送其实多此一举但没办法只怪我们把图分层了。不能在自环到达了。
3参考代码
#includebits/stdc.h
using namespace std;
int n,m,k;
int s,e;
struct Edge{int u,v,w,next;
}edge[2500001];
int head[110005],cnt;
void add(int u,int v,int w){edge[cnt](Edge){u,v,w,head[u]}; head[u]cnt;
}
int dis[110005],vis[110005];
struct node{int u,w;bool operator (const node x) const{return x.ww;}
};
void dijkstra(){priority_queuenodeq;memset(dis,0x3f,sizeof(dis));q.push((node){s,0});dis[s]0;while(!q.empty()){node tempq.top(); q.pop();int utemp.u;if(vis[u]) continue;vis[u]1;for(int ihead[u];i;iedge[i].next){int vedge[i].v,wedge[i].w;if(dis[v]dis[u]w){dis[v]dis[u]w;q.push((node){v,dis[v]});}}}
}
int main(){cinnmkse;for(int i1;im;i){int u,v,w;cinuvw;add(u,v,w);add(v,u,w);for(int j1;jk;j){add(u(j-1)*n,vj*n,0);add(v(j-1)*n,uj*n,0);add(uj*n,vj*n,w);add(vj*n,uj*n,w);}}for(int j1;jk;j){add(s(j-1)*n,sj*n,0);}dijkstra();coutdis[ek*n];return 0;
}二.多源传送
1题目
P6464 [传智杯 #2 决赛] 传送门 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
2思路
这题虽然是多源但只有一个传送门而且数据范围小只有100所以直接上floyd算法
因为我们不知道传送门怎么建立所以直接暴力枚举就行了。
我们两重遍历找出门在两重暴力folyd即可。
Qfolyd不是三重吗
A不是已经知道在哪搭桥了吗
Q:其他不也可以搭桥吗
A前面的预处理三重floyd已经处理好了。
3参考代码
#includebits/stdc.h
using namespace std;
int n,m;
int f[101][101];
int F[101][101];
inline void back()
{for(int i1;in;i)for(int j1;jn;j)F[i][j]f[i][j];
}
int main()
{scanf(%d%d,n,m);memset(f,-1,sizeof(f));for(int i1;im;i){int u,v,w;scanf(%d%d%d,u,v,w);if(f[u][v]-1||f[u][v]w) f[u][v]f[v][u]w;//建边防重边不过数据里没有}for(int k1;kn;k) for(int i1;in;i)for(int j1;jn;j)if(f[i][k]!-1f[k][j]!-1)if(f[i][j]-1||f[i][j]f[k][j]f[i][k])f[i][j]f[i][k]f[k][j];//Floydint ans2e9;//较大值for(int i1;in;i) for(int j1;jn;j)//暴力枚举{back();//先让F数组还原成f数组F[i][j]F[j][i]0;//在教学楼 i 和 j 之间建立传送门//i点搭桥 for(int x1;xn;x) for(int y1;yn;y) if(F[x][y]-1||F[x][y]F[x][i]F[i][y])F[x][y]F[x][i]F[i][y];//Floyd//j点搭桥 for(int x1;xn;x)for(int y1;yn;y) if(F[x][y]-1||F[x][y]F[x][j]F[j][y])F[x][y]F[x][j]F[j][y];//Floydint res0;for(int x1;xn;x) for(int y1;yx;y)resF[x][y];ansmin(res,ans);}printf(%d\n,ans);return 0;
}
