图论模板（未掌握）-白红宇

图论模板（未掌握）

阅读量：5014 次

发布时间：2019-06-12

本文共 2625 字，大约阅读时间需要 8 分钟。

SPFA（洛谷P1339热浪）

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;struct edge{    int rs,re,ci;}ed[30000];int dis[10000];int head[10000];int que[100000];bool pd[10000];int cn=0;void add(int x,int y,int z){    cn++;    ed[cn].rs=head[x];    ed[cn].re=y;    ed[cn].ci=z;    head[x]=cn;}int main(){    int t,c,ts,te,pf1,pf2,pf3,hr=0,tr=1;    cin>>t>>c>>ts>>te;    for(int i=1;i<=c;i++)    {        cin>>pf1>>pf2>>pf3;        add(pf1,pf2,pf3);        add(pf2,pf1,pf3);    }    memset(dis,127,sizeof(dis));    dis[ts]=0,pd[ts]=1,que[0]=ts;    while(hr
          
           dis[temp]+ed[i].ci) { dis[ed[i].re]=dis[temp]+ed[i].ci; if(pd[ed[i].re]==0) { pd[ed[i].re]=1; que[tr++]=ed[i].re; } } } pd[temp]=0; } cout<

迪杰斯特拉（来自）

#include
     
      #include
      
       #include
       
        using namespace std;int a[101][101];int dis[101];int maxn=0x7f;int vis[1001];int pass[1001];void print(int bg,int ed){    int ans[101];    int now=1;    ans[now]=ed;    now++;    //    ans[now]=ed;    //now++;    int tmp=pass[ed];    while(tmp!=bg)    {        ans[now]=tmp;        now++;        tmp=pass[tmp];    }    ans[now]=bg;    for(int i=now; i>=1; i--)    {        if(i!=1)            printf("%d-->",ans[i]);        else            printf("%d",ans[i]);    }}int main(){    memset(a,maxn,sizeof(a));    int n,m;    int beginn=1;    scanf("%d%d",&n,&m);    for(int i=1; i<=m; i++)    {        int x,y,zhi;        scanf("%d%d%d",&x,&y,&zhi);        a[x][y]=zhi;        a[y][x]=zhi;    }    for(int i=1; i<=n; i++)    {        if(a[beginn][i]!=maxn)        {            dis[i]=a[beginn][i];        }    }    dis[beginn]=0;    for(int i=1; i<=n; i++)    {        int minn=maxn;        int k=-1;        for(int j=1; j<=n; j++)        {            if(dis[j]<=minn&&vis[j]==0)            {                minn=dis[j];                k=j;            }        }        vis[k]=1;        for(int j=1; j<=n; j++)        {            if(dis[k]+a[k][j]<=dis[j])            {                dis[j]=dis[k]+a[k][j];                pass[j]=k;            }        }    }    for(int i=1; i<=n; i++)    {        cout<
        
         <<" ";        if(i==1)cout<

克鲁斯卡尔（）

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;const int MAXN=300001;struct node{    int u;    int v;    int w;}edge[MAXN];int num=1;int father[MAXN];int comp(const node & a,const node & b){    if(a.w