今天讲图论，顺便搞一搞之前没弄完的前向星dij
1.图的基本概念（课件原话）：
G （图）= (V（点）; E（边）)
一般来说，图的存储难度主要在记录边的信息
无向图的存储中，只需要将一条无向边拆成两条即可
邻接矩阵：用一个二维数组 edg[N][N] 表示
edg[i][j] 就对应由 i 到 j 的边信息
edg[i][j] 可以记录 Bool，也可以记录边权
缺点：如果有重边有时候不好处理
空间复杂度 O(V2)
点度（出边入边条数）等额外信息也是很好维护的
模板（传说中的链式前向星/链式存图）：
#include<bits/stdc++.h>
using namespace std;
const int N=100;
int n,m,s;
struct Ed{
int next,dis,to;
}ed[N];
int ed_num;
int tail[N];
inline void add(int from,int to,int dis){
ed_num++;
ed[ed_num].dis=dis;
ed[ed_num].to=to;
ed[ed_num].next=tail[from];
tail[from]=ed_num;
}
int main(){
scanf("%d%d%d",&n,&m,&s);
for(int i=1;i<=m;i++){
int a,b,c;
add(a,b,c);
}
//use it
for(int i=tail[s];i;i=ed[i].next){
//bla bla bla...
}
printf("What ever it takes\n");
return 0;
}
2.vector
用于灵活储存一定范围内（指不会爆栈）数据的变长数组
队列好像就是这么存的，然而这个东西很慢...
最小生成树：
3.kruskal（前置知识：并查集）：
将每条边排序，按从小到大加入生成树，并将两端点合并作同一并查集，
如果边的两端点再加入此边之前已属于同一集合，说明其已经连通，无需加入这一条边
如果当前边数已经为n-1，则跳出循环，已经找到目标
#include<bits/stdc++.h>
using namespace std;
int n,m;
int fa[5005];
inline int father(int t){
if(fa[t]!=t) fa[t]=father(fa[t]);
return fa[t];
}
inline void u(int l,int r){
int fl=father(l);
int fr=father(r);
if(fl!=fr) fa[fl]=fr;
}
struct ed{
int len;
int begin,end;
}dis[200005];
inline bool cmp(ed a,ed b){
return a.len<b.len;
}
int sum;
int num;
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
fa[i]=i;
for(int i=1;i<=m;i++){
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
dis[i].begin=x;
dis[i].end=y;
dis[i].len=z;
}sort(dis+1,dis+1+m,cmp);
for(int i=1;i<=m;i++){
if(father(dis[i].begin)!=father(dis[i].end)){
u(dis[i].begin,dis[i].end);
sum+=dis[i].len;
num++;
}
if(num==n-1){
cout<<sum<<endl;
return 0;
}
}
cout<<"orz";
return 0;
}
4.kosaraju（偷一波baidu）
对原图G进行深度优先遍历，记录每个节点的离开时间num[i]
选择具有最晚离开时间的顶点，对反图GT（由G的反向边组成）进行遍历，删除能够遍历到 的顶点
这些顶点构成一个强连通分量（好像是互相连通的意思）
如果还有顶点没有删除，继续步骤2，否则算法结束
5.prim
思想：一开始有n个连通块，从起点开始，每次找距离最短的连通块连到一起
代码：咕咕咕
总的来说，最小生成树还是用kruskal吧...
最短路问题（共四个,真正意义上是3个）：
给一个有向图，求s到e的最短距离（距离：两点之间边的边权和）
6.松弛操作——最短路算法的本质
dis[i][j]<=dis[i][k]+dis[k][j]
7.floyd（之前打的一直是错的）：
三层循环找上面式子的i（起点），j（终点），k（中间点）
代码（邻接矩阵）：
#include <bits/stdc++.h>
using namespace std;
const int N=505;
const int inf=1<<29;
int d[N][N],n,m;
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++) d[i][j]=inf;
for(int u,v,w,i=1;i<=m;i++)
cin>>u>>v>>w,d[u][v]=min(d[u][v],w);
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
printf("并没有输出\n");
return 0;
}
要点：
1.先要枚举k，不然就是错的
2.把最大边初始化为inf（infinite），即为极大（无穷），不然你min怎么取...（全是0）
3.主要思路是在k=t循环结束时，dis[i][j]只经过1,2...t，此时dis[i][j]为真实值
4.负权环（一个可以跑死SPFA的东西）：
Floyd跑完以后判断下有没有负边权就好，Floyd能处理，但SPFA会凉，
具体解决办法就是加一个计数变量，如果处理次数大于预期最大次数，就输出无解或关闭程序
单源最短路问题：
8.Bellman-Ford：
枚举每一条边（e（u，v，w））并松弛d（v）=min{d（v），d（u）+w}
松弛n次即可，可以加一个优化，
添加bool变量判断有没有进行松弛，没有就不用再进行该层循环了
9.SPFA：
把需要松弛的边用queue存储，等松弛时拿出操作，代码：
#include<bits/stdc++.h>
using namespace std;
const int inf=2147483647;
bool vis[500010];
int dis[500010];
int tail[500010];
struct Ed{
int next,to,dis;
}ed[500010];
int m,n,s;
int num_edge;
inline void join(int from,int to,int dis){
num_edge++;
ed[num_edge].dis=dis;
ed[num_edge].to=to;
ed[num_edge].next=tail[from];
tail[from]=num_edge;
}
queue<int> q;
int main(){
scanf("%d%d%d",&n,&m,&s);
for(int i=1;i<=m;i++)
dis[i]=inf;
vis[s]=1;
dis[s]=0;
for(int i=1;i<=m;i++){
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
join(x,y,z);
}
q.push(s);
while(!q.empty()){
int now=q.front();
q.pop();
vis[now]=0;
for(int i=tail[now];i;i=ed[i].next){
int end=ed[i].to;
if(dis[end]>dis[now]+ed[i].dis){
dis[end]=dis[now]+ed[i].dis;
if(!vis[end]){
q.push(end);
vis[end]=1;
}
}
}
}
for(int i=1;i<=n;i++){
printf("%d ",dis[i]);
}
return 0;
}
优化（上面提到过）：
记录每个点加入queue次数，如果大于n-1次，则这个点可能已经在负权环里面无限快乐了
SPFA跑稀疏图很快，跑网格图就非常慢了