北京网站设计联系电话,网站建设相关行业有哪些,wordpress 链接小图标,微信小程序怎么退出登录多源 超级源点和汇点最短距离[超级汇点]昂贵的聘礼 多源BFS矩阵距离 超级源点和汇点
超级源点跟超级汇点是模拟出来的虚拟点#xff0c;多用于图中#xff1a; 1同时有多个汇点和一个源点#xff0c;建立超级汇点 1、2、3、6分别到达4或者5或者7的最短路径#xf… 多源 超级源点和汇点最短距离[超级汇点]昂贵的聘礼 多源BFS矩阵距离 超级源点和汇点
超级源点跟超级汇点是模拟出来的虚拟点多用于图中 1同时有多个汇点和一个源点建立超级汇点 1、2、3、6分别到达4或者5或者7的最短路径设立0这个超级汇点。 2同时有多个源点和一个汇点建立超级源点 3同时有多个源点和多个汇点建立超级源点和超级汇点
最短距离[超级汇点]
题目连接https://www.acwing.com/problem/content/1490/ 思路分析这个题的关键就在于模拟出来一个超级汇点对于每个村庄来说目的地都是一个商店具体是哪一个商店是不要求的只需要找到最近的一个商店也就是找到到这些商店集合的最短路径虚拟出来一个超级汇点到这些商店的路径都为0这样每个村庄到达集合的最短路径其实就是到达这个超级汇点的最短路径了也就相当于是这个超级汇点到每个点的最短路径进行一次dijstra就行也就简化成了求点到点的最短路径。 AC代码
#includeiostream
#includequeue
#includevector
using namespace std;
const int N100005;
const int INF0x3f3f3f3f;
typedef pairint,intPII;
vectorPIIadj[N];
int dist[N];
bool visited[N];
int n,m,k,q,x;
priority_queuePII,vectorPII,greaterPIIque;void dijistra(int s)
{for(int i0;in;i) dist[i]INF; dist[s]0; que.push({0,s});while(!que.empty()){int minque.top().second;que.pop();if(visited[min]) continue;visited[min]true;for(int i0;iadj[min].size();i){if(!visited[adj[min][i].first]dist[min]adj[min][i].seconddist[adj[min][i].first]){dist[adj[min][i].first]dist[min]adj[min][i].second;que.push({dist[adj[min][i].first],adj[min][i].first});}}}
}
int main()
{cinnm;while(m--){int u,v,c; cinuvc; adj[u].push_back({v,c}); adj[v].push_back({u,c});}cink;while(k--){cinx; adj[0].push_back({x,0}); adj[x].push_back({0,0});}dijistra(0); cinq; while(q--){cinx; coutdist[x]endl;}return 0;
}昂贵的聘礼
刷题链接https://www.acwing.com/problem/content/905/ 思路分析到底怎么建立图是很关键的必要的时候要加一些超级源点和超级汇点 还是注意要建立一个超级源点表示最后终止继续交换下去的那个人的花费是他的物品的价格 最后要保证求出来的最短路包含的结点的等级相互之间都不超过m只能是枚举这个等级区间了不能说每次更新邻接结点的时候判断该结点距离当前纳入最短路径集合的结点的距离如果超过了m就不更新这样只能保证相邻的两个结点的等级是不超过m的但是最后最短路径包含的全部结点相互间不一定都不超过m规则是只要跟一个很高的人交换了后面涉及的所有等级很低的人都不能再进行交换 AC代码
#includeiostream
#includequeue
#includevector
#includealgorithm
using namespace std;
const int N105;
const int INF0x3f3f3f3f;
typedef pairint,intPII; //first表示未结点编号second表示到达该结点的优惠
vectorPIIadj[N];
int dist[N];
bool visited[N];
int m,n,p,l,x,t,v;
int Rank[N]; //存储每个结点的等级
priority_queuePII,vectorPII,greaterPIIque;int dijistra(int down,int up) //传入区间等级最大和最小值
{for(int i0;in;i){dist[i]INF; visited[i]false;}dist[0]0;que.push({0,0});while(!que.empty()){int minque.top().second;que.pop();if(visited[min]) continue;visited[min]true;for(int i0;iadj[min].size();i){//超级源点跟谁都能到达 if(Rank[adj[min][i].first]up||Rank[adj[min][i].first]down) continue; //等级相差太大无法到达 if(!visited[adj[min][i].first]dist[min]adj[min][i].seconddist[adj[min][i].first]){dist[adj[min][i].first]dist[min]adj[min][i].second;que.push({dist[adj[min][i].first],adj[min][i].first});}}}return dist[1];
}
int main()
{cinmn;for(int i1;in;i){cinplx;adj[0].push_back({i,p}); //建立超级源点到该点的边权Rank[i]l;while(x--) //替代品们 {cintv;adj[t].push_back({i,v}); //建立替代品到该点的边权} }int ansINF;for(int iRank[1]-m;iRank[1];i){ansmin(ans,dijistra(i,im)); //超级源点到每个点的最短路径 }coutansendl; return 0;
}多源BFS
单源BFS起始阶段只需要将某一个元素加入队列 二叉树层序遍历 多源BFS开始阶段加入多个元素入队列可以将其理解为存在一个超级源点然后进行宽搜扩展第一阶段会把距离为0的点扩展进队列进行求解最短距离第二阶段会把距离为1的点扩展进队列进行求解最短距离第三阶段会把距离为2的点扩展进队列进行求解最短距离…最后成功将所有点距离目标点的最短距离求出来了。
矩阵距离
题目链接https://www.acwing.com/problem/content/description/175/ 思路分析曼哈顿距离实际就是从1位置处向外扩展每次扩展距离加1 AC代码
#includeiostream
#includebits/stdc.h
using namespace std;
int n,m;
typedef pairint,intPII;
queuePIItou;
const int INF0x3f3f3f3f;
const int N1005;
int grid[N][N];
int off[4][2]{{0,-1},{0,1},{-1,0},{1,0}};
int main()
{cinnm;for(int i0;in;i){for(int j0;jm;j){char t;cint;if(t1) {grid[i][j]0;tou.push({i,j});}else grid[i][j]-1;}}while(!tou.empty()){int xtou.front().first;int ytou.front().second;tou.pop();for(int i0;i4;i){int xixoff[i][0],yiyoff[i][1];if(xi0 yi0 xin yim grid[xi][yi]0){tou.push({xi,yi});grid[xi][yi]grid[x][y]1;}}}for(int i0;in;i){for(int j0;jm;j){coutgrid[i][j] ;}coutendl;}return 0;
}
