aoe.cpp

AOE网关键路径（Activity On Edge） 数据结构其中前两个数代表两个顶点之间的通路

#include<iostream>
#include<cmath>
#include<algorithm>
#include<stack>
#include<fstream>
using namespace std;
#define MAX 100000

struct node
{
    int v;
    int w;
    node *next;
};

node adj[MAX];
node reversed_adj[MAX];
int indegree[MAX];
int ve[MAX];
int vl[MAX];

void initial(int n)
{
    int i;
    for(i=1;i<=n;i++)
    {
        adj[i].v=i;
        adj[i].w=-1;
        reversed_adj[i].v=i;
        reversed_adj[i].w=-1;
        adj[i].next=NULL;
        reversed_adj[i].next=NULL;
    }
}

void findindegree(node adj[],int n)
{
    int i;
    for(i=1;i<=n;i++)
        indegree[i]=0;
    for(i=1;i<=n;i++)
    {
        node *p=adj[i].next;
        while(p!=NULL)
        {
            indegree[p->v]++;
            p=p->next;
        }
    }
}


void creat(node adj[],node reversed_adj[],int n)
{
    fstream file("test.txt");
    int i;
    cout<<"您将建立一个具有"<<n<<"个顶点的邻接表,请依次输入边和权值，并以0 0 0结束"<<endl;
    for(i=1;;i++)
    {

        int a,b,c;
        printf("请输入第%d条边以及权值(u v w):",i);
        file>>a>>b>>c;
        cout<<endl;
        if(a==0&&b==0&&c==0)
            break;
        node *p;
        node *q;
        /**//////////////////////
        p=&adj[a];
        q=new node;
        q->v=b;
        q->w=c;
        q->next=p->next;
        p->next=q;
        /**/////////////////////
        p=&reversed_adj[b];
        q=new node;
        q->v=a;
        q->w=c;
        q->next=p->next;
        p->next=q;
        /**////////////////////
    }

}


void topsort(node adj[],int n,int v[],int x)
{
    int i;
    node *p;
    stack<int>mystack;
    while(!mystack.empty())
        mystack.pop();
    findindegree(adj,n);
    for(i=1;i<=n;i++)
        v[i]=x;
    for(i=1;i<=n;i++)
    {
        if(indegree[i]==0)
        {

            mystack.push(i);
        }
    }
    /**/////////////////////////////
    while(mystack.size()!=0)
    {

        i=mystack.top();
        mystack.pop();
        for(p=adj[i].next;p!=NULL;p=p->next)
        {

            indegree[p->v]--;
            if(indegree[p->v]==0)
                mystack.push(p->v);
            if(x==0)
            {
                if(v[i]+p->w  >  v[p->v])
                {

                    v[p->v]=v[i]+p->w;
                }
            }
            else
            {
                if(v[i]-p->w  <  v[p->v])
                    v[p->v]=v[i]-p->w;
            }   

        }
    }
}


void printedg(node adj[],int n,int ve[],int vl[])
{
    int i;
    node *p;
    int k;
    int e;
    int l;

    for(i=1;i<=n;i++)
    {
        p=adj[i].next;
        while(p!=NULL)
        { 
            k=p->v;
            e=ve[i];
            l=vl[k]-p->w;
            cout<<i<<' '<<k<<' '<<e<<' '<<l;
            if(e==l) cout<<"*";
            cout<<endl;
            p=p->next;
        }//while
    }//for

}



int main ()
{
    int n;
    cout<<"请输入顶点数n:";
    cin>>n;
    initial(n);
    creat(adj,reversed_adj,n);//建立邻接表和逆邻接表
    topsort(adj,n,ve,0);
    topsort(reversed_adj,n,vl,ve[n]);
    printedg(adj,n,ve,vl);
    system("pause");
    return 0;

}