ACM_有向图邻接表与链式前向星储存

发布于 2019-09-02  43 次阅读


邻接表:

#pragma comment(linker,"/STACK:1024000000,1024000000")
#pragma GCC optimize(2)
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <experimental/string_view>
#define lodou long double
#define lll __int128
#define INmF 0x3f3f3f3f
#define lbt(x) (x&(-x))
#define mes(a,b) memset(a,b,sizeof(a))
#define qwq(a,b) for(int i=a ;i<=b;++i)
#define qeq(a,b) for(int j=a ;j<=b;++j)
#define IOS ios::sync_with_stdio(false)
#define UPCASE( c ) ( ((c) >= 'c' && (c) <= 'z') ? ((c) - 0x20) : (c) )
#define pb push_back
#define mkp make_pair
using namespace std;
using namespace __gnu_pbds;

using pii=pair<int,int>;
using Balanced_Tree=tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>;
Balanced_Tree seq;

const double Eps = 1e-8 ;
const double pi  = acos(-1) ;
const long long mod = 1e9+7 ;
typedef long long int ll;


inline ll pow_mod (ll a,ll b) {ll res=1;a%=mod; if(b<0) return -1; for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
inline ll fas_mul (ll a,ll b) { return ( (a*b-(ll)(((long double)a*b+0.5)/mod)*mod)%mod+mod)%mod ; }


namespace io {

    #define in(a) a=read()
    #define out(a) write(a)
    #define outn(a) out(a),putchar('\n')

    #define I_int __int128
    inline I_int read() {
        I_int x = 0 , f = 1 ; char c = getchar() ;
        while( c < '0' || c > '9' ) { if( c == '-' ) f = -1 ; c = getchar() ; }
        while( c >= '0' && c <= '9' ) { x = x * 10 + c - '0' ; c = getchar() ; }
        return x * f ;
    }
    char F[ 200 ] ;
    inline void write( I_int x ) {
        if( x == 0 ) { putchar( '0' ) ; return ; }
        I_int tmp = x > 0 ? x : -x ;
        if( x < 0 ) putchar( '-' ) ;
        int cnt = 0 ;
        while( tmp > 0 ) {
            F[ cnt ++ ] = tmp % 10 + '0' ;
            tmp /= 10 ;
        }
        while( cnt > 0 ) putchar ( F[ -- cnt ] ) ;
    }
    #undef I_int

}using namespace io ;

struct Edgenode
{
    int vtxno ;
    int weight;
    Edgenode *next ;
};
struct Vnode
{
    string vertexLabel ;
    Edgenode * first ;
    bool visited ;
    int dis ;
    int path ; //only for Dijkstra
    int indegree ;
};
struct Gragh
{
    Vnode *vertexList ;
    int vertexes ;
    int edges ;
};
void BuildeGragh( Gragh* &gragh , int n )
{
    if( gragh==NULL ){
        gragh = new Gragh  ;
        gragh->vertexList = new Vnode[n] ;
        gragh->vertexes = n ;
        gragh->edges = 0 ;
        for (int i = 0; i < n ; ++i)
        {
            stringstream ss ;
            ss<<"v"<<i+1 ;
            ss>> gragh->vertexList[i].vertexLabel ;
            gragh->vertexList[i].path = -1 ;
            gragh->vertexList[i].visited = false ;
            gragh->vertexList[i].first = NULL ;
            gragh->vertexList[i].indegree = 0 ;
        }
    }
}
void MakeEmpty( Gragh* &gragh )
{
    if( gragh==NULL )
        return ;
    for (int i = 0; i < gragh->vertexes ; ++i)
    {
        Edgenode* pEdge = gragh->vertexList[i].first ;
        while( pEdge )
        {
            Edgenode* tmp = pEdge ;
            pEdge = pEdge->next ;
            delete tmp ;
        }
    }
    delete gragh ;
}
void AddEdge( Gragh* gragh , int v1 , int v2 , int weight )
{
    if( gragh==NULL )
        return ;
    if( v1<0 || v1>gragh->vertexes-1 )
        return ;
    if( v2<0 || v2>gragh->vertexes-1 )
        return ;
    if( v1==v2 )
        return ;

    Edgenode* p = gragh->vertexList[v1].first ;
    if( p==NULL ){
        gragh->vertexList[v1].first = new Edgenode ;
        gragh->vertexList[v1].first->next = NULL ;
        gragh->vertexList[v1].first->vtxno = v2 ;
        gragh->vertexList[v1].first->weight = weight ;
        ++gragh->edges ;
        ++gragh->vertexList[v2].indegree ;
        return ;
    }
    while( p->next )
    {
        if( p->vtxno==v2 )
            return ;
        p=p->next ;
    }
    if( p->vtxno==v2 )//already exits. checking the first or the last node
        return ;

    Edgenode* node = new Edgenode ;
    node->next = NULL ;
    node->vtxno = v2 ;
    node->weight = weight ;
    p->next = node ;
    ++gragh->edges ;
    ++gragh->vertexList[v2].indegree ;
}
void RemoveEdge( Gragh* gragh , int v1 , int v2 )
{
    if( gragh==NULL )
        return ;
    if( v1<0 || v1>gragh->vertexes-1 )
        return ;
    if( v2<0 || v2>gragh->vertexes-1 )
        return ;
    if( v1==v2 )
        return ;

    Edgenode *p = gragh->vertexList[v1].first ;
    if( p==NULL )
        return ;
    if( p->vtxno==v2 ){//found,delete the first
        Edgenode *tmp = p ;
        gragh->vertexList[v1].first = p->next ;
        delete tmp ;
        --gragh->edges ;
        --gragh->vertexList[v2].indegree ;
        return ;
    }
    while( p->next )
    {
        if( p->next->vtxno==v2 )//found 
        {
            Edgenode *tmp = p->next ;
            p=p->next->next ;
            delete tmp ;
            --gragh->edges ;
            --gragh->vertexList[v2].indegree ;
            return ;
        }
        p=p->next ;
    }
}
int Getindegree( Gragh *gragh , int v )
{
    if(gragh==NULL)
        return -1 ;
    if( v<0 || v>gragh->vertexes-1 )
        return -2 ;
    int degree = 0 ;
    for (int i = 0; i < gragh->vertexes; ++i)
    {
        /* code */
        Edgenode *p = gragh->vertexList[i].first ;
        while( p )
        {
            if( p->vtxno == v ){
                ++degree ;
                break ;
            }
            p = p->next ;
        } 
    }
    return degree ;
}
int Getoudegree( Gragh *gragh , int v )
{
    if( gragh==NULL )
        return -1 ;
    if( v<0 || v>gragh->vertexes-1 )
        return -2 ;
    int degree = 0 ;
    Edgenode *p = gragh->vertexList[v].first ;
    while( p )
    {
        p=p->next ;
        ++degree ;
    }
    return degree ;
}
void PrintGragh( Gragh* gragh )
{
    if( gragh==NULL )
        return ;
    cout<<"Vertex: "<<gragh->vertexes<<endl ;
    cout<<"Edge: "<<gragh->edges<<endl ;
    for (int i = 0; i < gragh->vertexes; ++i)
    {
        /* code */
        cout<< i+1 <<":"<<gragh->vertexList[i].vertexLabel<<"->" ;
        Edgenode* p = gragh->vertexList[i].first ;
        while( p )
        {
            cout<<gragh->vertexList[p->vtxno].vertexLabel<<"("<<p->weight<<")->" ;
            p=p->next ;
        }
        puts("") ;
    }
    puts("") ;
}
void Dfs( Gragh *gragh , int i )
{
    if( !gragh->vertexList[i].visited ){
        cout<< gragh->vertexList[i].vertexLabel <<" " ;
        gragh->vertexList[i].visited = true ;
    }
    Edgenode *p = gragh->vertexList[i].first ; 
    while( p )
    {
        if( !gragh->vertexList[p->vtxno].visited )
            Dfs( gragh , p->vtxno ) ;
        p=p->next ;
    }
}
void Dfsini( Gragh* gragh )
{
    if( gragh==NULL )
        return ;
    puts("Dfs");
    for (int i = 0; i < gragh->vertexes ; ++i)
    {
        gragh->vertexList[i].visited = false ;
        /* code */
    }
    for (int i = 0; i < gragh->vertexes; ++i)
    {
        Dfs( gragh , i ) ;
        /* code */
    }
}
void Bfs( Gragh* gragh )
{
    if( gragh==NULL )
        return ;
    puts("Bfs") ;
    for (int i = 0; i < gragh->vertexes ; ++i)
    {
        gragh->vertexList[i].visited = false ;
        /* code */
    }
    queue<int> Qver ;
    for (int i = 0; i < gragh->vertexes; ++i)
    {
        if( !gragh->vertexList[i].visited ){
            Qver.push( i ) ;
            cout<< gragh->vertexList[i].vertexLabel<<" " ;
            gragh->vertexList[i].visited = true ;
        }
        /* code */
    }
    while( !Qver.empty() )
    {
        int vtxNO = Qver.front() ;
        Qver.pop();
        Edgenode *p = gragh->vertexList[vtxNO].first ;
        while( p )
        {
            if( !gragh->vertexList[p->vtxno].visited ){
                cout<< gragh->vertexList[p->vtxno].vertexLabel <<" " ;
                gragh->vertexList[p->vtxno].visited = true ;
                Qver.push( p->vtxno ) ;
            }
            p=p->next ;
        }
    }
    puts("") ;
}
void TopologicalSort( Gragh* gragh )
{
    if (gragh==NULL)
    {
        return ;
        /* code */
    }
    puts("TopologicalSort");
    int counter=0 ;
    queue<int> Qver ;
    for (int i = 0; i < gragh->vertexes; ++i)
    {
        if( !Getindegree( gragh,i ) )
            Qver.push( i ) ;
        /* code */
    }
    while( !Qver.empty() )
    {
        int vtxNO = Qver.front() ;
        ++counter ;
        cout<< gragh->vertexList[vtxNO].vertexLabel ;
        if( counter!=gragh->vertexes )
            cout<<" > " ;
        Qver.pop() ;
        Edgenode *p = gragh->vertexList[vtxNO].first ;
        while( p )
        {
            int pvtx = p->vtxno ;
            p=p->next ;
            if( --gragh->vertexList[pvtx].indegree==0 )
                Qver.push(pvtx) ;
        }
    }
    puts("") ;
}
void Dijkstra( Gragh* gragh , int v )
{
    if( gragh==NULL )
        return ;
    if( v<0 || v>gragh->vertexes-1 )
        return ;
    for (int i = 0; i < gragh->vertexes; ++i)
    {
        gragh->vertexList[i].visited = false ;
        gragh->vertexList[i].dis = INmF;
        gragh->vertexList[i].path = -1 ;
        /* code */
    }
    gragh->vertexList[v].dis = 0 ;
    while(233)
    {
        int minDisinx = -1 ;
        int minDis = INmF ;
        for (int i = 0; i < gragh->vertexes; ++i)
        {
            if( !gragh->vertexList[i].visited )
            {
                if( gragh->vertexList[i].dis < minDis )
                {
                    minDis = gragh->vertexList[i].dis ;
                    minDisinx = i ;
                }
            }
            /* code */
        }
        if( !~minDisinx )
            break ;
        gragh->vertexList[minDisinx].visited = true ;
        Edgenode *p = gragh->vertexList[minDisinx].first ;
        while( p )
        {
            int pvtx = p->vtxno ;
            if( !gragh->vertexList[pvtx].visited )
            {
                if (gragh->vertexList[minDisinx].dis+p->weight < gragh->vertexList[pvtx].dis )
                {
                    gragh->vertexList[pvtx].dis = gragh->vertexList[minDisinx].dis + p->weight ;
                    gragh->vertexList[pvtx].path = minDisinx ;
                    cout<< gragh->vertexList[pvtx].vertexLabel<<" Updated to "<< gragh->vertexList[pvtx].dis<<endl ;
                    /* code */
                }
            }
            p = p->next ;
        }
    }
    puts("Vertex\tVisited\tDistance   \tPath") ;
    for (int i = 0; i < gragh->vertexes; ++i)
    {
        cout<< gragh->vertexList[i].vertexLabel<<"\t";
        cout<< gragh->vertexList[i].visited<< "\t";
        cout<< gragh->vertexList[i].dis<<"\t" ;
        //putchar('\t');
        if( !~gragh->vertexList[i].path )
            puts("NONE") ;
        else
            cout<< gragh->vertexList[gragh->vertexList[i].path].vertexLabel<<"\t"<<endl ;
        /* code */
    }
}
void Prim( Gragh* gragh , int v )
{
    if( gragh==NULL )
        return ;
    if( v<0 || v>gragh->vertexes-1 )
        return ;
    for (int i = 0; i < gragh->vertexes ; ++i)
    {
        gragh->vertexList[i].visited = false ;
        gragh->vertexList[i].dis = INmF ;
        gragh->vertexList[i].path = -1 ;
        /* code */
    }
    gragh->vertexList[v].dis = 0 ;
    while(233)
    {
        int minDisinx = -1 ;
        int minDis = INmF ;
        for (int i = 0; i < gragh->vertexes ; ++i)
        {
            if( !gragh->vertexList[i].visited )
            {
                if (gragh->vertexList[i].dis<minDis)
                {
                    minDis = gragh->vertexList[i].dis ;
                    minDisinx = i ;
                    /* code */
                }
            }
            /* code */
        }
        if( !~minDisinx )
            break ;
        gragh->vertexList[minDisinx].visited = true ;
        Edgenode *p=gragh->vertexList[minDisinx].first ;
        while( p )
        {
            int pvtx = p->vtxno ;
            if( !gragh->vertexList[pvtx].visited )
            {
                if( p->weight < gragh->vertexList[pvtx].dis )
                {
                    gragh->vertexList[pvtx].dis = p->weight ;
                    gragh->vertexList[pvtx].path = minDisinx ;
                    cout<< gragh->vertexList[pvtx].vertexLabel<<" Update to "<<gragh->vertexList[pvtx].dis<<endl ;
                }
            }
            p = p ->next ;
        }
    }
    puts("Vertex\tVisited\tDistance   \tPath") ;
    for (int i = 0; i < gragh->vertexes; ++i)
    {
        cout<< gragh->vertexList[i].vertexLabel<<"\t" ;
        cout<< gragh->vertexList[i].visited<<"\t" ;
        cout<< gragh->vertexList[i].dis<< "\t";
        //putchar('\t');
        if( !~gragh->vertexList[i].path )
            puts("NONE") ;
        else
            cout<< gragh->vertexList[gragh->vertexList[i].path].vertexLabel<<"\t"<<endl ;
        /* code */
    }
}
signed main(int argc, char const *argv[])
{
    Gragh *gragh=NULL ;
    BuildeGragh( gragh,7 ) ;
    PrintGragh( gragh ) ;
    
    AddEdge( gragh ,0,1,1);
  AddEdge( gragh ,0,2,1);
  AddEdge( gragh ,0,3,1);
  AddEdge( gragh ,1,3,1);
  AddEdge( gragh ,1,4,1);
  AddEdge( gragh ,2,5,1);
  AddEdge( gragh ,3,2,1);
  AddEdge( gragh ,3,5,1);
  AddEdge( gragh ,3,6,1);
  AddEdge( gragh ,4,3,1);
  AddEdge( gragh ,4,6,1);
  AddEdge( gragh ,6,5,1);
  PrintGragh( gragh );
  
  RemoveEdge(gragh,6,5);
  
  PrintGragh( gragh );
  Dfsini( gragh );
  puts("") ;
  Bfs( gragh );
  for (int i = 0; i <  gragh ->vertexes; i++)
  {
    puts("") ;
    Dijkstra( gragh ,i);
  }
  Prim( gragh ,0);

  TopologicalSort(  gragh  );
  MakeEmpty(  gragh  );
    return 0;
}

链式前向星:

#pragma comment(linker,"/STACK:1024000000,1024000000")
#pragma GCC optimize(2)
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <experimental/string_view>
#define lodou long double
#define lll __int128
#define INmF 0x3f3f3f3f
#define lbt(x) (x&(-x))
#define mes(a,b) memset(a,b,sizeof(a))
#define qwq(a,b) for(int i=a ;i<=b;++i)
#define qeq(a,b) for(int j=a ;j<=b;++j)
#define IOS ios::sync_with_stdio(false)
#define UPCASE( c ) ( ((c) >= 'c' && (c) <= 'z') ? ((c) - 0x20) : (c) )
#define pb push_back
#define mkp make_pair
using namespace std;
using namespace __gnu_pbds;

using pii=pair<int,int>;
using Balanced_Tree=tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>;
Balanced_Tree seq;

const double Eps = 1e-8 ;
const double pi  = acos(-1) ;
const long long mod = 1e9+7 ;
typedef long long int ll;


inline ll pow_mod (ll a,ll b) {ll res=1;a%=mod; if(b<0) return -1; for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
inline ll fas_mul (ll a,ll b) { return ( (a*b-(ll)(((long double)a*b+0.5)/mod)*mod)%mod+mod)%mod ; }


namespace io {

    #define in(a) a=read()
    #define out(a) write(a)
    #define outn(a) out(a),putchar('\n')

    #define I_int __int128
    inline I_int read() {
        I_int x = 0 , f = 1 ; char c = getchar() ;
        while( c < '0' || c > '9' ) { if( c == '-' ) f = -1 ; c = getchar() ; }
        while( c >= '0' && c <= '9' ) { x = x * 10 + c - '0' ; c = getchar() ; }
        return x * f ;
    }
    char F[ 200 ] ;
    inline void write( I_int x ) {
        if( x == 0 ) { putchar( '0' ) ; return ; }
        I_int tmp = x > 0 ? x : -x ;
        if( x < 0 ) putchar( '-' ) ;
        int cnt = 0 ;
        while( tmp > 0 ) {
            F[ cnt ++ ] = tmp % 10 + '0' ;
            tmp /= 10 ;
        }
        while( cnt > 0 ) putchar ( F[ -- cnt ] ) ;
    }
    #undef I_int

}using namespace io ;

const int Max_v = 1e5+50 ;
const int Max_e = 1e6+50 ;
int Vertes , Edges , cnt ;
int heap[Max_v] , dis[Max_v] ;
struct Edge
{
    int to ,
        next ,
        cost ; 
}rng[Max_e]; 

void Add( int u , int v , int cost )
{
    rng[cnt].to = v ;
    rng[cnt].next = heap[u] ;
    rng[cnt].cost = cost ;
    heap[u] = cnt++ ;
}
struct Rule
{
    bool operator ()( int &a , int &b )const
    {
        return dis[a] > dis[b] ;
    }
};
void Dijkstra( int a_ )
{
    mes( dis , INmF ) ;
    priority_queue <int , vector<int> , Rule > q ;
    dis[a_] = 0 ;
    q.push( a_ ) ;
    while( !q.empty() )
    {
        int u=q.top() ;
        q.pop() ;
        for( int k=heap[u] ; ~k ; k=rng[k].next )
        {
            int &v = rng[k].to ;
            if( dis[v] > dis[u]+rng[k].cost ){
                dis[v] = dis[u]+rng[k].cost ;
                q.push( v ) ;
            }
        }
    }
}
signed main(int argc, char const *argv[])
{
    cnt = 0 ;
    mes( heap , -1 ) ;
    Vertes=read() , Edges = read() ;
    int x , y, z ;
    qwq( 1 , Edges )
    {
        x=read() , y=read() , z=read() ;
        Add(x,y,z) ;
    }
    Dijkstra(1);
    if( dis[Vertes]==INmF )
        puts("-1") ;
    else
        outn( dis[Vertes] ) ;
    return 0;
}
/*
4 7
1 2 3
2 3 4
3 4 5
1 3 1
4 1 2
1 5 3
4 5 3
*/

 

喜欢这篇文章吗,不妨分享给朋友们吧!

科学是第一生产力