图论总结

拓扑排序 1.用ru[]存入度，用vector存对应的点 2.找入度为0的点，入队 3.while循环 dijkstra： 贪心+松弛操作 使用前向星 优先队列优化（用于稀疏图——m比n稍大） mlogm

const int N=10000; const int M=50000; int n,m,s; int nex[M+10],to[M+10],head[N+10],w[M+10]; bool tag[N+10]; int dis[N+10]; int totm; struct node{ int x,d;//点，距离 node(int X,int D){ x=X; d=D; } bool operator < (const node& A) const{ return d>A.d;//小根堆 } }; priority_queue<node> q; int main(){ scanf("%d%d%d",&n,&m,&s); for(int i=1;i<=m;i++){ int x,y,z; scanf("%d%d%d",&x,&y,&z); totm++; nex[totm]=head[x]; head[x]=totm; to[totm]=y; w[totm]=z; } memset(dis,255,sizeof(dis)); dis[s]=0; q.push(node(1,0)); while(!q.empty()){ int p=q.top().x;//取出距离最近的一点 q.pop(); if(tag[p]){ continue; } tag[p]=1; for(int j=head[p];j;j=nex[j]){ int y=to[j]; if(dis[y]==-1 ||(!tag[y] && dis[y]>dis[p]+w[j])){ dis[y]=dis[p]+w[j]; q.push(node(y,dis[y])); } } } for(int i=1;i<=n;i++){ cout<<dis[i]<<" "; } return 0; }

稠密图 用普通做法n^2

const int N = 5000; const int M = 500000; int n, m, s; int nex[M+10],to[M+10],w[M+10],head[N+10]; bool tag[N + 10]; int dis[N + 10]; int totm; int main(){ scanf("%d%d%d",&n,&m,&s); for (int i = 1;i <= m; i++){ int x,y,z; scanf("%d%d%d",&x,&y,&z); totm++; nex[totm]=head[x]; head[x]=totm; to[totm]=y; w[totm]=z; } memset(dis,255,sizeof(dis)); dis[s]=0; for(int i=1;i<=n;i++){ int x=-1; for(int j = 1;j <= n ;j++) if(!tag[j] && dis[j]!=-1){ if(x==-1 || dis[j]<dis[x]){ x=j; } } if(x==-1){ break; } tag[x]=true; for(int j=head[x];j>0;j=nex[j]){ int y=to[i]; if(dis[y]==-1 || dis[y]>dis[x]+w[j]){ dis[y]=dis[x]+w[j]; } } } for(int i=1;i<=n;i++){ printf("%d ",dis[i]); } return 0; }

Floyd n<100,m较大,询问较大（任意两点）

for(int k=1;k<=n;k++){//中间点枚举放最前面 for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]); } } }

题模：

商品交易：

1.若有路径，贪心：最小时买入，最大时卖出 2.找路径： 一条路上，必存在中间点使得有最小x，最大y。 故枚举中间点 第一部分：1—>i，找最小，最短路径 第二部分：i—>n，找最大，多源一汇 多源一汇：反向建立新图->以n为单源，最短路径 ans=max(b[i]-a[i])

排名：

具有传递性 而图的传达性也具有传递性 if(merk

费用