怎么把自己做的网站放到网上,克隆网站怎么做后台,网站基础知识域名5个点,校园网站建设培训的心得体会C4上级图部分 TOPO!步骤代码段TOPO排序部分 完整代码 简单的图图题目描述输入输出样例步骤代码段开辟vector容器作为dist二维数组初始化调用Floyd算法查询 完整代码 负环题目描述输入输出样例步骤代码段全局变量定义spfa1函数用于判断是否有负环spfa2用于记录每个点到1号点的距… C4上级图部分 TOPO!步骤代码段TOPO排序部分 完整代码 简单的图图题目描述输入输出样例步骤代码段开辟vector容器作为dist二维数组初始化调用Floyd算法查询 完整代码 负环题目描述输入输出样例步骤代码段全局变量定义spfa1函数用于判断是否有负环spfa2用于记录每个点到1号点的距离 完整代码 直击西溜线地铁最短换乘次数题目描述输入输出样例步骤tip代码段全局变量设定 完整代码 Email loss题目描述输入输出样例tip步骤代码段全局变量设定 完整代码 莫卡的最远点对题目描述输入输出样例 TOPO! 步骤
这道题比较简单因为是要从大到小输出所以用队列的时候用上大根堆。还记得建小堆怎么建吗 priority_queueint,vector int ,greater int heap; 三个参数都不能少哈↑ 构建大根堆只需写 priority_queue int
如果没说顺序那么可以用y总的手搓队列。
代码段
int e[N],ne[N],idx,h[N];
/*
e[i]表示第i个点的值
ne[i]表示第i个点的next点的下标编号
h[a]是值为a的点指向的点的下标
*/
int n,m;
int dgr[N];//dgr[i]表示值为i的点对应的下标
//注意一定是值不是编号
int toposort[N];//存放排序结果
int INDEX;TOPO排序部分
void topo(){priority_queueint heap;//如果没说要按什么顺序输出那普通的队列就可以for(int i1;in;i){if(dgr[i]0){heap.push(i);//先把所有入度为0的点全部放进去}}while(!heap.empty()){int top heap.top();heap.pop();toposort[INDEX]top;//取堆顶for(int ih[top];i!-1;ine[i]){//把堆顶点连着的点全部都遍历一遍所有点的入度都减一如果他变为0了那么入堆int val e[i];dgr[val]--;if(dgr[val]0){heap.push(val);}}}for(int i0;in;i){couttoposort[i] ;}
}完整代码
#include iostream
#includecstring
#includequeue
using namespace std;
const int N 1e63;
int e[N],ne[N],idx,h[N];
int n,m;
int dgr[N];
int toposort[N];//存放排序结果
int INDEX;
void add(int a,int b){e[idx]b;ne[idx]h[a];h[a]idx;
}void topo(){priority_queueint heap;for(int i1;in;i){if(dgr[i]0){heap.push(i);}}while(!heap.empty()){int top heap.top();heap.pop();toposort[INDEX]top;for(int ih[top];i!-1;ine[i]){int val e[i];dgr[val]--;if(dgr[val]0){heap.push(val);}}}for(int i0;in;i){couttoposort[i] ;}
}int main(){cinnm;memset(h,-1,sizeof h);for(int i0;im;i){int a,b;cinab;add(a,b);dgr[b];}topo();
}简单的图图
题目描述 输入输出 样例 步骤
求多源最短路径那就是Floyd算法了。 这道题只需要求u到v的最短路径长度而不需要输出对应的路径序列因此我们并不需要再开辟path数组只需要开辟dist数组即可。 path数组用来存放经过的路径可以用vector开辟一个存放String的二维数组 vectorvector string strings(rows);//rows代表你想开辟的行数 代码段
开辟vector容器作为dist二维数组
vectorvectorll dist(n1,vectorll(n1,INF));后面的参数表示有n1行每一行是一个vector容器每个元素初始化为INF最大值
初始化
for(int i0;im;i){ll u,v,w;cinuvw;dist[u][v]min(dist[u][v],w);//因为有重边则只保留值小的那一个
}
for(int i1;in;i){dist[i][i]0;}//对角线初始化为0调用Floyd算法
for(int k1;kn;k){for(int i1;in;i){for(int j1;jn;j){if(dist[i][k]!INFdist[k][j]!INF)//注意这里要判断一下dist[i][j] min(dist[i][j],dist[i][k]dist[k][j]);}}}查询 int q;cinq;while(q--){ll u,v;cinuv;if(dist[u][v]INF){cout-1endl;}else{coutdist[u][v]endl;}}完整代码
#include iostream
#include cstring
#include vector
#include algorithm
using namespace std;
typedef long long ll;
//const int N 305;
const long long INF 1e18;
int main(){ll n,m;cinnm;vectorvectorll dist(n1,vectorll(n1,INF));for(int i0;im;i){ll u,v,w;cinuvw;dist[u][v]min(dist[u][v],w);//因为有重边则只保留值小的那一个}for(int i1;in;i){dist[i][i]0;}//对角线初始化为0for(int k1;kn;k){for(int i1;in;i){for(int j1;jn;j){if(dist[i][k]!INFdist[k][j]!INF)dist[i][j] min(dist[i][j],dist[i][k]dist[k][j]);}}}int q;cinq;while(q--){ll u,v;cinuv;if(dist[u][v]INF){cout-1endl;}else{coutdist[u][v]endl;}}
}负环
题目描述 输入输出 样例 步骤
先使用SPFA算法判断是否有负环如果有负环则输出“boo how”要注意用SPFA判断图内是否有负环的时候负环不一定在起点到终点的路径上因此开始初始化队列的时候需要把所有的点都放进去。原理是相当于给原图加上了一个虚拟源点从该点向其他所有点都连着一条权为0的弧。cnt【x】等于n时说明从x点到0点有n条边即有n1个点而图内最多有n个点由抽屉原理在0-x的通路上必然有两个相同的点。由于spfa每一次松弛操作都让x到0距离变小则必然存在负环判断完负环以后就可以再用一次spfa算法去计算每一个点到1号点的距离了。由于有负权边的存在只能用spfa或者bellman——ford算法。由于本题是多组数据输入因此在每一次输出完数据之后都要记得把该初始化的全都初始化干净。“打扫干净屋子再请客”。
代码段
全局变量定义
#define INF 1e9
const int N 1e5;
const int M 1e5;
ll e[M],ne[M],w[M],h[N],idx;//这几个数组在编译器允许的范围内能开多大
int st[N];//判断第i个点是否在队里
//st数组设成bool类型也可
ll cnt[N],dist[N];//cnt数组记录第i个点到虚拟源点的最短路径的边数
void add(int a,int b,int c){e[idx]b;ne[idx]h[a];w[idx]c;h[a]idx;
}
int n,m;spfa1函数用于判断是否有负环
bool spfa1(){queueint q;for(int i1;in;i){q.push(i);st[i]1;}while(q.size()){auto top q.front();q.pop();st[top]0;for(int ih[top];i!-1;ine[i]){int j e[i];if(dist[j]dist[top]w[i]){dist[j]dist[top]w[i];cnt[j]cnt[top]1;if(cnt[j]n){return true;}if(!st[j]){q.push(j);st[j]1;}}}}return false;
}spfa2用于记录每个点到1号点的距离
void sfpa2(){fill(dist,distN-1,INF);memset(st,0,sizeof st);dist[1]0;queueint q;q.push(1);st[1]1;while(q.size()){auto top q.front();q.pop();st[top]0;for(int ih[top];i!-1;ine[i]){int j e[i];if(dist[j]dist[top]w[i]){dist[j]dist[top]w[i];if(!st[j]){q.push(j);st[j]1;}}}}for(int i1;in;i){coutdist[i] ;}puts();
}完整代码
#include iostream
#include cstring
#include algorithm
#include cmath
#include queue
using namespace std;
typedef long long ll;
#define INF 1e9
const int N 1e5;
const int M 1e5;
ll e[M],ne[M],w[M],h[N],idx;
int st[N];
ll cnt[N],dist[N];
void add(int a,int b,int c){e[idx]b;ne[idx]h[a];w[idx]c;h[a]idx;
}
int n,m;
bool spfa1(){queueint q;for(int i1;in;i){q.push(i);st[i]1;}while(q.size()){auto top q.front();q.pop();st[top]0;for(int ih[top];i!-1;ine[i]){int j e[i];if(dist[j]dist[top]w[i]){dist[j]dist[top]w[i];cnt[j]cnt[top]1;if(cnt[j]n){return true;}if(!st[j]){q.push(j);st[j]1;}}}}return false;
}
void sfpa2(){fill(dist,distN-1,INF);memset(st,0,sizeof st);dist[1]0;queueint q;q.push(1);st[1]1;while(q.size()){auto top q.front();q.pop();st[top]0;for(int ih[top];i!-1;ine[i]){int j e[i];if(dist[j]dist[top]w[i]){dist[j]dist[top]w[i];if(!st[j]){q.push(j);st[j]1;}}}}for(int i1;in;i){coutdist[i] ;}puts();
}
int main(){int t;cint;while(t--){cinnm;//该初始化的都一定一定要初始化不然各组数据之间会串联memset(h,-1,sizeof h);memset(dist,0,sizeof dist);memset(cnt,0,sizeof cnt);memset(st,0,sizeof st);for(int i0;im;i){ll a,b,c;cinabc;add(a,b,c);}if(spfa1()){coutboo howendl;continue;}else{sfpa2();}}
}直击西溜线地铁最短换乘次数
题目描述 输入输出 样例 步骤
存储每次查询的起点和终点存储每条线路的站点存储每条线路站点的同时将线路号加到map中每个站点对应的数组中专门存放这个站点都属于哪些线路处理G【】【】邻接矩阵用于表示每两条线路之间的换乘代价。初始化时如果两条线之间没有直接换乘点初始化为无穷同一条线初始化为0有直接换乘点初始化为1用floyd算法计算每两条线路之间的最少换乘次数更新G邻接矩阵遍历每次查询的起点和终点取它们所在的所有线路找到换乘次数最小的两条线。注意最少换乘次数和最少乘坐站数不一样。最少换乘次数相当于把同一条线上抽象成了一个点最少乘坐站数则直接用floyd或者dijikstra算法就可解决。
tip
输入需要用getline(cin,需要输入的内容 ,cin输入不能读取字符串之间的空格而本题地铁站名含有空格。类似地cin.get()可以用来接受单个字符也可以接受带空格的字符串由于getline读到回车就结束如果输入整数之后有回车那么根本就不能正确获取地铁站名例如 int a;string b;cina;//cin.ignore();getline(cin,b);coutaendl;coutbendl;如果不加cin.ignore()的话geline读到a后面的回车就会直接结束输入的
除非你这么输入。
访问vector()中的元素如果没有提前给vector申请空间那么不能直接用下标访问这个一会儿结合具体代码说
代码段
全局变量设定
const int INF 1e9;
int G[30][30];//两条线路之间是否能换乘
//同一条线路为0不同线路可以直接换乘为1不同线路不能换乘INF
vectorpairstring,string inquiries;//存放查询的起终点
mapstring,vectorint mp;//存放每个站点属于哪些线路
vectorstring lines[30];//存放每条线路都有哪些站
int n,q;//地铁线路条数和询问次数我们这里开辟inquiries和lines都是没有直接申请空间的因此后面必须先用 resize(m) 给它申请m个空间才能通过下标访问0-m-1的元素。
也可以直接vector string linesINF给它开辟INF个空间。二维vector数组初始化可以看看简单的图图那个题
完整代码
void least_change(){ //将G图初始化为INFfill(G[0],G[0]30*30,INF);cinnq;cin.ignore();inquiries.resize(q);for(int i0;iq;i){getline(cin,inquiries[i].first);getline(cin,inquiries[i].second);//读取每次询问的起终点 }for(int i0;in;i){//读取每一条线路int m;cinm;cin.ignore();lines[i].resize(m);for(int j0;jm;j){//读取每一条线路的每一个站getline(cin,lines[i][j]); if(jm-1(lines[i][m-1]lines[i][0]))continue; mp[lines[i][j]].push_back(i);}}//同一线路上的站点换乘代价为0for(int i0;in;i){G[i][i]0;}//不同线路之间是否能换乘要手动判断for(auto station:mp){auto belongs station.second;int sz belongs.size();for(int i0;isz;i){for(int j0;jsz;j){if(i!jbelongs[i]!belongs[j])G[belongs[i]][belongs[j]]1;}}}//floyd算法找到每两条线路之间的最短换乘次数for(int k0;kn;k){for(int i0;in;i){for(int j0;jn;j){if(G[i][k]!INFG[k][j]!INF)G[i][j] min(G[i][j],G[i][k]G[k][j]);}}}//处理每次查询for(auto inq:inquiries){auto begin_lines mp[inq.first];auto end_lines mp[inq.second];// for(int i0;ibegin_lines.size();i){// coutbegin_lines[i] ;// } // puts();// for(int i0;iend_lines.size();i){// coutend_lines[i] ;// } // puts();int ret INF; for(int i0;ibegin_lines.size();i){for(int j0;jend_lines.size();j){ret min(ret,G[begin_lines[i]][end_lines[j]]);}}coutretendl;}}
int main(){least_change();
}要注意环线必须要进行处理 if(jm-1(lines[i][m-1]lines[i][0]))continue; mp[lines[i][j]].push_back(i);如果是环线的话就别重复加它属于第i条线了因为 //不同线路之间是否能换乘要手动判断for(auto station:mp){auto belongs station.second;int sz belongs.size();for(int i0;isz;i){for(int j0;jsz;j){if(i!jbelongs[i]!belongs[j])G[belongs[i]][belongs[j]]1;}}}i ! j的时候belongs【i】有可能等于belongs【j】,如果两条线相同的话换乘代价应该是0而不是1因此不需要重复加
Email loss
这题看着唬人其实就是个求最短路径没啥难的
题目描述 输入输出 样例 tip
注意这里n和m是一个量级的因此是稀疏图要用堆优化版的dijikstra算法如果m和n^2 是一个量级的那可以用朴素版。无向图和有向图没区别无向图就是A-BB-A就行了。其次dijikstra算法中不能顺便把不能达到的点算了因为根本就遍历不到它只能找到s源点可以到达但是时间超过t的。因此需要在全部点的最短距离计算结束之后再统一找不符合的点.如果输出类型是固定的那么printf要比cout的输出效率更高endl还有刷新缓存区的功能因此多次循环输出如果都用endl的话可能会超时用\n换行效率更高
步骤
先用堆优化dijistra计算所有点到s源点的距离注意堆中存储的数据pair元素1元素2,元素1必须是距离元素2才是编号。因为堆排序的时候默认按照first排序。每次弹出当前回合距离s源点最近的。
代码段
全局变量设定
都是一些套路了
typedef long long ll;
const ll INF 2e18;
using namespace std;
const int N 1e610;
typedef pairll,ll PII;
ll e[N],ne[N],w[N],h[N],idx;
ll n,m,s,t;//点边源点最大时间
ll dist[N];
bool st[N];完整代码
void solve(){cinnmst;memset(h,-1,sizeof h);fill(dist,distN,INF);dist[s]0;for(ll i0;im;i){ll a,b,c;cinabc;add(a,b,c);add(b,a,c);}priority_queuePII,vectorPII,greaterPII q;q.push({0,s});//堆优化while(q.size()){auto top q.top();q.pop();ll val top.second,distance top.first;if(st[val])continue;st[val]true;for(int ih[val];i!-1;ine[i]){int j e[i];if(dist[j]distancew[i]){dist[j]distancew[i];q.push({dist[j],j});}}}vectorPII vec;for(int i1;in;i){if(dist[i]INF){vec.push_back({i,-1});}else if(dist[i]t){vec.push_back({i,dist[i]});}}coutvec.size()\n;for(auto v :vec){coutv.first v.secondendl;}
}
int main(){solve();return 0;
}莫卡的最远点对
题目描述 输入输出 样例
这个题还需要补充一些树型DP还有树的直径的相关知识等我学了再来写这个题吧
