图论小系统

将自己学的知识整合了一下，弄了个小的图论系统。

有关知识请看：http://blog.csdn.net/column/details/tulun.html

#include 
#include 
#include 
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
const   int oo=1e9;/**oo 表示无穷大*/
const  int mm=1111111;/**mm 表示边的最大数量，记住要是原图的两倍，在加边的时候都是双向的*/
const  int mn=2010;/**mn 表示点的最大数量*/
int head[mn];
int ip;
int n,m;///n个点，m条边
int rd[mn],rdd[mn];///入度
int cd[mn];///出度
int dd[999][999],dist[mn];///任意两点距离
struct data
{
    int to,w,next;
} tu[mm];
void init()///初始化
{
    ip=0;
    memset(head,-1,sizeof(head));
    memset(cd,0,sizeof(cd));
    memset(rd,0,sizeof(rd));
    memset(rdd,0,sizeof(rdd));
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
            dd[i][j]=i==j?0:oo;
}
void add(int u,int v,int w)///添加边
{
    tu[ip].w=w,tu[ip].to=v,tu[ip].next=head[u],head[u]=ip++;
}
void input(int flag)///图的输入
{
    cout<>a>>b>>c;
        while(a<1||a>n||b<1||b>n)
        {
            cout<<"请重新输入正确的顶点！！（1到"<>a>>b>>c;
        }
        if(flag)
            add(a,b,c);
        else
            add(a,b,c),add(b,a,c);
        rd[b]++;
        rdd[b]++;
        cd[a]++;
    }
    cout<<"建图完成！正在跳转…………"<>ss;
        while(ss<1||ss>n)
        {
            cout<<"请重新输入1到"<>ss;
        }
        cout<<"请输入第二个点";
        cin>>ee;
        while(ee<1||ee>n)
        {
            cout<<"请重新输入1到"<>ee;
        }
        if(ss!=ee)
        {
            if(dd[ss][ee]>s;
        while(s<0||s>n)
        {
            cout<<"请重新输入1到"<>s;
        }
        if(s==0)break;
        queueq;
        for(int i=0; i<=n; i++)
            dist[i]=oo;
        int vis[mn]= {0};
        q.push(s);
        dist[s]=0;
        while(!q.empty())
        {
            int h=q.front();
            q.pop();
            vis[h]=0;
            for(int i=head[h]; i!=-1; i=tu[i].next)
            {
                int v=tu[i].to;
                int w=tu[i].w;
                if (dist[v]>dist[h]+w)
                {
                    dist[v]=dist[h]+w;
                    if (!vis[v])
                    {
                        vis[v]=1;
                        q.push(v);
                    }
                }
            }
        }
        for(int i=1; i<=n; i++)
            if(i!=s)
            {
                if(dist[i]>=oo)
                    cout< scc[mn];///得出来的缩点，scc[i]里面存i这个缩点具体缩了哪些点
stack S;
void dfs(int u)
{
    dfn[u] = low[u] = ++step;
    S.push(u);
    for (int i = head[u]; i !=-1; i=tu[i].next)
    {
        int v = tu[i].to;
        if (!dfn[v])
        {
            dfs(v);
            low[u] = min(low[u], low[v]);
        }
        else if (!sccno[v])
            low[u] = min(low[u], dfn[v]);
    }
    if (low[u] == dfn[u])
    {
        scc_cnt += 1;
        scc[scc_cnt].clear();
        while(1)
        {
            int x = S.top();
            S.pop();
            if (sccno[x] != scc_cnt) scc[scc_cnt].push_back(x);
            sccno[x] = scc_cnt;
            if (x == u) break;
        }
    }
}
void tarjan()
{
    system("cls");
    for(int i=0; i<=n; i++)
        scc[i].clear();
    memset(sccno, 0, sizeof(sccno));
    memset(dfn, 0, sizeof(dfn));
    step = scc_cnt = 0;
    for (int i = 1; i <=n; i++)
        if (!dfn[i]) dfs(i);
    cout<<"该图的强连通分量有"<=0; j=tu[j].next)
            cout<"<q;
    int flag=0;
    for(int i=1; i<=n; i++)
        if(!rdd[i])
            q.push(i),flag=1;
    if(!flag)
    {
        cout<<"该有向图形成了环，无法进行拓扑排序"<=0; i=tu[i].next)
        {
            int to=tu[i].to;
            rdd[to]--;
            if(!rdd[to])
            {
                q.push(to);
            }
        }
    }
    cout<=0; i=nex[i])
            if(flow[i]&&dis[v=ver[i]]<0)
            {
                dis[q[r++]=v]=dis[u]+1;
                if(v==dest)  return 1;
            }
    return 0;
}
int Dinic_dfs(  int u, int exp)
{
    if(u==dest)  return exp;
    for(  int &i=work[u],v,tmp; i>=0; i=nex[i])
        if(flow[i]&&dis[v=ver[i]]==dis[u]+1&&(tmp=Dinic_dfs(v,min(exp,flow[i])))>0)
        {
            flow[i]-=tmp;
            flow[i^1]+=tmp;
            return tmp;
        }
    return 0;
}
int Dinic_flow()
{
    int i,ret=0,delta;
    while(Dinic_bfs())
    {
        for(i=0; i>tt)
        {
            while(tt<0||tt>6)
            {
                cout<<"请重新输入0到6之间的数字！！"<>tt;
            }
            if(!tt)
                return;
            else if(tt==1)
                bianli();
            else if(tt==2)
                topu();
            else if(tt==3)
                Dinic();
            else if(tt==4)
            {
                floyd();
                break;
            }
            else if(tt==5)
            {
                spfa();
                break;
            }
            else
            {
                tarjan();
                break;
            }
        }
    }
}
void wushow()///展示无向图功能
{
    cout<<"1.无向图的遍历"<ss;
    ss.push(1);
    while(!ss.empty())
    {
        int x=ss.top();
        cout<q;
    q.push(1);
    while(!q.empty())
    {
        int x=q.front();
        cout<>tt;
        while(tt>2||tt<0)
        {
            cout<<"请重新输入0到2！！"<>tt;
        }
        if(tt==1)
            wsbianli();
        else if(tt==2)
            wgbianli();
        else
            break;
    }
}
struct tree
{
    int a,b,w;
    void sett(int x,int y,int z)
    {
        a=x,b=y,w=z;
    }
} ttu[mm];
bool cmp(tree a,tree b)
{
    return a.w"<>tt)
        {
            while(tt<0||tt>5)
            {
                cout<<"请重新输入0到5之间的数字！！"<>tt;
            }
            if(!tt)
                return;
            else if(tt==1)
            {
                wbianli();
                break;
            }
            else if(tt==2)
            {
                floyd();
                break;
            }
            else if(tt==3)
            {
                spfa();
                break;
            }
            else if(tt==4)
            {
                mintree();
                break;
            }
            else
            {
                tarjan();
                break;
            }
        }
    }
}
int main()
{
    while(1)
    {
        system("cls");
        cout<<"----------这是一个图论小系统----------"<>n;
        if(!n)break;
        cout<<"请输入要建图的边数：";
        cin>>m;
        cout<<"正在跳转…………"<>tt)
        {
            if(tt==1)
            {
                youxiangtu();
                system("cls");
                break;
            }
            else if(tt==2)
            {
                wuxiangtu();
                break;
            }
            else if(tt==0)
            {
                system("cls");
                break;
            }
            cout<<"请输入0，1，2！"<



图论小系统