写在前面

把所有的图论的代码都敲了一遍，以防止生疏QAQ

邻接表

1
2
3
4
5
6
7
void init(int xx,int yy,int vv)//邻接表
{
    a[++Len].Point=yy;
    a[Len].Next=Link[xx];
    a[Len].Value=vv;
    Link[xx]=Len;
}

边表

1
2
3
4
5
6
void line_init(int xx,int yy,int vv)//边表
{
    a[++len].x=xx;
    a[len].y=y;
    a[len].v=vv;
}

Floyd

1
2
3
4
5
6
7
8
void Floyd()

{
    for(int k=1;k<=n;k++)
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
    d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
}

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
void Dijkstra(int Point)//经过堆优化
{
    struct note
    {
        int ID;
        int Value;
        friend bool operator < (note x,note y)
        { return x.Value>y.Value; }
    }f[501],This;
    priority_queue<note>Q;
    for(int i=1;i<=n;i++)
    {
        f[i].Value=123456789;
        f[i].ID=i;
    }
    f[Point].Value=0;
    Q.push(f[Point]);
    while(Q.empty()==false)
    {
        This=Q.top(); Q.pop();
		if(List[This.ID]) continue;
		List[This.ID]=true;
        for(int i=Link[This.ID];i!=0;i=a[i].Next)
        if(!List[a[i].Point]&&This.Value+a[i].Value<f[a[i].Point].Value)
        {
            f[a[i].Point].Value=This.Value+a[i].Value;
			Q.push(f[a[i].Point]);
        }
    }
}

Bellman-Ford:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
bool Bellman_Ford(int Point)//注意用的是边表
{
    memset(dis,10,sizeof(dis));
    dis[Point]=0;
    for(int i=1;i<=n;i++)
    {
        bool Really=false;
        for(int j=1;j<=m;j++)//枚举每一条边
        {
            if(a[j].Value+dis[a[j].Point_x]<dis[a[j].Point_y])
            {
                dis[a[j].Point]=a[j].Value+dis[a[j].Point_x];
                Really=true;
            }
        }
        if(Really==false) return true;//没有负环
    }
    return false;//有负环
}

SPFA:

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
bool SPFA(int Point)//在NOIP级别比赛就用这个了
{
    memset(dis,10,sizeof(dis));
    memset(vis,false,sizeof(vis));
    head=1;tail=1;dis[Point]=0;
    vis[Point]=true;Queue[1]=Point;
    all[Point]=1;
    while(head<=tail)
    {
        int This=Queue[head++];
        vis[This]=false;
        for(int i=Link[This];i!=0;i=a[i].next)
        {
            int That=a[i].Point;
            if(dis[This]+a[i].Value<dis[That])
            {
                dis[That]=dis[This]+a[i].Value;
                if(vis[That]==false)
                {
                    Queue[++tail]=That;
                    vis[That]=true;
                    all[That]++;
                    if(all[That]>n)
                    return false;//有负环
                }
            }
        }
    }
    return true;//没有负环
}

Prim:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void Prim()//本来可以搞堆优化的，但是性价比不高
{
    memset(dis,10,sizeof(dis));
    memset(vis,false,sizeof(vis));
    for(int i=Link[1];i!=0;i=a[i].Next)
    dis[a[i].Point]=a[i].Value;
    vis[1]=true; Length=0;
    for(int i=2;i<=n;i++)
    {
        int mini=dis[0],This=0;
        for(int j=1;j<=n;j++)
        if(!vis[j]&&dis[j]<mini)
        {
            mini=dis[j];
            This=j;
        }
        vis[This]=true;
        Length+=mini;
        for(int j=Link[This];j!=0;j=a[j].Next)
        if(!vis[a[j].Point]&&a[j].Value<dis[a[j].Point])
        dis[a[j].Point]=a[j].Value;
    }
}

Kruskal：

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
//注意kruskal用的是边表
void Getfather(int x)
{
    int True_father=x;
    while(True_father!=father[True_father])
    True_father=father[True_father];
    while(x!=True_father)
    {
        int This=father[x];
        father[x]=True_father;
        x=This;
    }
    return True_father;
}
void Kruskal()
{
    for(int i=1;i<=n;i++)
    father[i]=i;
    sort(a+1,a+n+1,mycmp);
    int all=0,Length=0;
    for(int i=1;i<=Len;i++)
    {
        int First=Getfather(a[i].x);
        int Second=Getfather(a[i].y);
        if(First!=Second)
        {
            Length+=a[i].Value;
            father[First]=Second;
            if(++all==n-1) return;
        }
    }
}
//以上就是Kruskal算法QAQ

Topsork：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void Topsort()
{
    int head=0,tail=0;
    for(int i=1;i<=n;i++)
    if(!Thing[i]) Queue[++tail]=i;
    while(head<tail)
    {
        head++;
        for(int i=1;i<=n;i++)
        if(a[Queue[head]][i])
        {
            Thing[i]--;
            if(!Thing[i])
            Queue[++tail]=i;
        }
    }
}
//题目中的无向图都不一定是联通的，需要访问每一个连通块：

Tarjan_Point:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int main()
{
    int dfn[max],low[max],ind=0;
    for(int i=1;i<=n;i++)
    if(!dfn[i]) Tarjan(i);
}
void Tarjan_Point(int x,int father=0)
{
    dfn[x]=low[y]=++ind;
    int son=0;
    for(int i=Link[x];i!=0;i=a[i].Next)
    if((y=a[i].Point)!=father)
    {
        if(!dfn[y])
        {
            tarjan(y,x);
            low[x]=min(low[y],low[x]);
            if(dfn[x]<=low[y]) son++;                
        }
        else low[x]=min(low[x],dfn[y]);
    }
    if(son>=2||(son==1&&father)) ans[++tot]=x;
}

Tarjan_Line:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void Tarjan_line(int x,int father=0)
{
    dfn[x]=low[x]=++ind;
    for(int i=Link[x];i;i=a[i].Next)
    {
        int y=a[i].Point;
        if(i!=father)
        if(!dfn[y])
        {
            tarjan(y,i);
            low[x]=min(low[x],low[y]);
        } else low[x]=min(low[x],dfn[y]);
    }
    if(dfn[x]==low[x])
    ans[++tot]=father;//记录的是父亲边（也就是到达点x的边）
}

Tarjan_Connected_Component:

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
//求强连通分量
int ind=0,dfn[2000],low[2000],stack[2000],tot=0,top=0
bool ins[2000]={false};
void Tarjan_Strongly_Connected_Component(int x)
{
    dfn[x]=low[x]=++ind;
    ind[x]=true;
    stack[++top]=x;
    for(int i=Link[x];i;i=a[i].Next)
    {
        int y=a[i].Point;
        if(!dfn[y])
        {
            tarjan(y);
            low[x]=min(low[x],low[y]);
        }else if(ins[y]==true)
        low[x]=min(low[x],dfn[y]);
    }
    if(dfn[x]==low[x])
    {
        int k; tot++;
        do{
            k=stack[top--];
            ins[k]=false;
            bel[k]=tot;
        }while(k!=x);
    }
}

差分约束：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
bool Topsort_SPFA()
{
    for(int i=1;i<=n;i++)
    if(!dis[i]) Queue[++tail]=i;
    while(++head<=tail)
    for(int i=Link[Queue[head]];i;i=a[i].Next)
    {
        int This=a[i].Point; dis[This]--;
        Money[This]=max(Money[This],Money[Queue[head]]+1);
        if(!dis[This]) Queue[++tail]=This;
        if(dis[This]<0) return false;
    }
    sort(Money+1,Money+n+1);
    if(Money[1]<0) return false;
    else return true;
}

FORD-FULKERSON算法

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
void DFS(int x,int Line)
{
    vis[x]=true;
    if(x==n)
    {
        Get=true;
        all+=Line;
        Forward=Line;
        return;
    }
    for(int i=1;i<=n;i++)
    if(dis[x][i]>0&&!vis[i])
    {
        DFS(i,min(dis[x][i],Line));
        if(Get)
        {
            dis[x][i]-=Forward;
            dis[i][x]+=Forward;
            return;
        }
    }
}
while(Get)
{
    Get=false;
    memset(vis,false,sizeof(vis));
    DFS(1,123456789);
}

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
bool GetLevel()
{
    memset(Level,-1,sizeof(Level));
    int head=0,tail=1;
    Queue[1]=1; Level[1]=0;
    while(++head<=tail)
    {
        for(int i=Link[Queue[head]];i;i=a[i].Next)
        if(Level[a[i].Point]<0&&a[i].Value)
        {
            Queue[++tail]=a[i].Point;
            Level[Queue[tail]]=Level[Queue[head]]+1;
        }
    }
    return Level[n]>=0;
}
int GetMaxFlow(int x,int Flow)
{
    if(x==n) return Flow;
    int MaxFlow=0,D=0;
    for(int i=Link[x];i&&MaxFlow<Flow;i=a[i].Next)
    if(a[i].Value&&Level[a[i].Point]==Level[x]+1)
    if(D=GetMaxFlow(a[i].Point,min(Flow-MaxFlow,a[i].Value)))
    {
        MaxFlow+=D;
        a[i].Value-=D;
        a[a[i].Back].Value+=D;
    }
    if(!MaxFlow) Level[x]=-1;
    return MaxFlow;
}
void Dinic()
{
    int ans;
    while(GetLevel())
    while(ans=GetMaxFlow(1,123456789)) all+=ans;
}

SPFA求最小费用最大流

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
bool SPFA()
{
    memset(vis,false,sizeof(vis));
    memset(dis,12,sizeof(dis));
    dis[1]=0; vis[1]=true;
    Queue[1]=1;
    int head=0,tail=1;
    while(++head<=tail)
    {
        int Top=Queue[head];
        for(int i=Link[Top];i;i=a[i].Next)
        if(a[i].Flow&&(dis[Top]+a[i].Value<dis[a[i].Point]))
        {
            if(!vis[a[i].Point])
            {
                Queue[++tail]=a[i].Point;
                vis[a[i].Point]=true;
            }
            dis[a[i].Point]=dis[Top]+a[i].Value;
            LastPoint[a[i].Point]=Top;
            LastEdge[a[i].Point]=i;
        }
        vis[Top]=false;
    }
    return dis[T]!=202116108;
}
void Change()
{
    int Find=123456789;
    for(int i=T;i!=S;i=LastPoint[i])
    if(a[LastEdge[i]].Flow<Find)
    Find=a[LastEdge[i]].Flow;
    for(int i=T;i!=S;i=LastPoint[i])
    {
        a[LastEdge[i]].Flow-=Find;
        a[a[LastEdge[i]].Back].Flow+=Find;
        ans+=Find*(-a[LastEdge[i]].Value);
    }
}