技术

图论的常用算法

在科研中，其实主要用的是最大流开源库，没有自己写过。

为了在效率上优化，实际上maxflow/min-cut这个库写的还挺复杂，我曾看过一些，但只能做到在有代码的情况下弄懂。

最小生成树——Prim

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
int Prim(int** a, int n, int& maxRoad)
{
    int mst=0;
    bool* visit=new bool[n];
    for(int i=0; i<n; ++i) visit[i]=false;
    int* curRow=new int[n];
    for(int i=0; i<n; ++i) curRow[i]=a[0][i];
    visit[0]=true;
    for(int i=1; i<n; i++)
    {
        int next=-1;
        int nextlen=0xfffff;
        for(int j=0; j<n; j++)
        {
            if(!visit[j] && curRow[j]<nextlen)
            {
                next=j;
                nextlen=curRow[j];
            }
        }
        if(next==-1) return -1;
        mst+=curRow[next];
        if(curRow[next]>maxRoad) maxRoad=curRow[next];
        visit[next]=true;
        for(int j=0; j<n; j++)
        {
            if(!visit[j] && a[next][j]<curRow[j]) curRow[j]=a[next][j];
        }
    }
    delete [] visit;
    delete [] curRow;
    return mst;
}

最短路径——Dijkstra

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
int findMinNode(int** a, int s, int n, bool* visit)
{
    int curmin=-1;
    int curlen=maxdist;
    for(int i=0; i<n; i++)
    {
        if(!visit[i] && a[s][i]<curlen)
        {
            curmin=i;
            curlen=a[s][i];
        }
    }
    return curmin;
}
void Dijkstra(int** a, int s, int n)
{
    int* dist=new int[n];
    bool* visit=new bool[n];
    for(int i=0; i<n; i++)
    {
        if(i==s) dist[i]=0;
        else dist[i]=maxdist;
        visit[i]=false;
    }
    //visit[s]=true;
    for(int i=0; i<n; i++)
    {
        int curmin=findMinNode(a,s,n,visit);
        if(curmin==-1) return;
        visit[curmin]=true;
        for(int j=0; j<n; j++)
        {
            if(!visit[j] && dist[j]>dist[curmin]+a[curmin][j]) dist[j]=dist[curmin]+a[curmin][j];
        }
    }
    for(int i=0; i<n; i++)
    {
        if(i==0) cout << dist[i];
        else cout << " " << dist[i];
    }
    cout << endl;
    delete [] dist;
    delete [] visit;
    return;
}

最短路径——BellmanFord

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
void BellmanFord(int** a, int s, int n)
{
    int* dist=new int[n];
    for(int i=0; i<n; i++) dist[i]=maxdist;
    dist[s]=0;
    for(int i=1; i<=n-1; i++)
    {
        for(int j=0; j<n; j++)
        {
            for(int k=0; k<n; k++)
            {
                if(dist[k]>dist[j]+a[j][k]) dist[k]=dist[j]+a[j][k];
            }
        }
    }
    for(int i=0; i<n; i++)
    {
        if(i==0) cout << dist[i];
        else cout << " " << dist[i];
    }
    cout << endl;
    delete [] dist;
    return;
}

最短路径——Floyd

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
void Floyd(int** a, int s, int n)
{
    int* ptr=new int[n*n];
    memset(ptr,maxdist,sizeof(int)*n*n);
    int** distmat=new int*[n];
    for(int i=0; i<n; i++)
    {
        distmat[i]=ptr+i*n;
    }
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<n; j++)
        {
            distmat[i][j]=a[i][j];
        }
    }
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<n; j++)
        {
            for(int k=0; k<n; k++)
            {
                if(distmat[i][j]>distmat[i][k]+distmat[k][j]) distmat[i][j]=distmat[i][k]+distmat[k][j];
            }
        }
    }
    int* dist=distmat[s];
    for(int i=0; i<n; i++)
    {
        if(i==0) cout << dist[i];
        else cout << " " << dist[i];
    }
    cout << endl;
    delete [] distmat;
    delete [] ptr;
    return;
}

最大流——Dinic

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
bool makeLevel(int** a, int s, int t, int* level, int n)
{
    for(int i=0; i<n; i++) level[i]=-1;
    level[s]=0;
    queue<int> mq;
    mq.push(s);
    while(!mq.empty())
    {
        int len=mq.size();
        while(len--)
        {
            int curnode=mq.front();
            mq.pop();
            for(int i=0; i<n; i++)
            {
                if(level[i]==-1 && a[curnode][i]>0)
                {
                    level[i]=level[curnode]+1;
                    mq.push(i);
                }
            }
        }
    }
    return level[t]!=-1;
}
int findFlow(int** a, int x, int t, int n, int* level, int flow)
{
    if(x==t) return flow;
    int ret=0;
    for(int i=0; i<n; i++)
    {
        if(level[i]==level[x]+1 && a[x][i]>0 && (ret=findFlow(a,i,t,n,level,min(flow,a[x][i]))))
        {
            a[i][x]+=ret;
            a[x][i]-=ret;
            return ret;
        }
    }
    return 0;
}
void Dinic(int** a, int s, int t, int n)
{
    int* level=new int[n];
    int flow=0;
    int maxflow=0xfffff;
    while(makeLevel(a,s,t,level,n))
    {
        flow+=findFlow(a,s,t,n,level,maxflow);
    }
    cout << flow << endl;
    delete [] level;
}