图论初步

Treap_Kongzs · 2024-08-04 22:44:45 · 算法·理论

省流：本篇专供冲击NOIP一等的人使用，坐标HN

博客同步

没图床放图来写图论是真的蛋疼……

1.图的dfs/bfs

图论中的深度优先遍历dfs和广度优先遍历bfs的思想基础和深度优先搜索&&广度优先搜索基本一致。所以你为什么会不会？还不去复习搜索？

对于遍历，我们打一个vis数组，每遍历到一个点，就把它的vis设为true（false也可以，但你自己要记得）

• 对于dfs，我们可以以它为起点进行递归

• 对于bfs，我们可以将它扔进一个队列，下次循环时取出来作为起点。

不同的图有不同的dfs和bfs方法，事实上，对于不同的图论算法，建不同的图，写码难度不尽相同，你马上就会看到这点。

习题1.1.1

P5318 【深基18.例3】查找文献

这个基本上是板子题了，虽然可能有更板的题，但是我忘了是哪道了，不好放上来。

看看例题代码，认真体会遍历与搜索的区别和联系。

还有，如果图不能保证连通，就不要把点数n作为运算和输出的依据！！！

AC Code：

#include<bits/stdc++.h>
using namespace std;
const int maxm=1e6+7;
const int maxn=1e5+7;

vector<int>e[maxm];
int vis[maxn];
int cnt;

void dfs(int n,int len)
{
    vis[n]++;
    cout<<n<<' ';
    for(int i=0;i<e[n].size();i++)
    {
        int v=e[n][i];
        if(!vis[v])

        {
            vis[v]++;
            dfs(v,len);
        }
    }
}

void bfs(int n,int len)
{
    queue<int> q;
    q.push(n);
    vis[n]++;
    cout<<n<<' ';
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(int i:e[u])
        {
            if(!vis[i])
            {
                vis[i]++;
                q.push(i);
                cout<<i<<' ';
            }
        }
    }
}

int main()
{
    int x=0,y=0;
    cin>>x>>y;
    for(int i=1;i<=y;i++)
    {
        int a=0,b=0;
        cin>>a>>b;
        e[a].push_back(b);
    }
    for(int i=0;i<=y;i++)
    {
        sort(e[i].begin(),e[i].end());
    }
    dfs(1,x);
    cnt=0;
    memset(vis,0,sizeof(vis));
    cout<<endl;
    bfs(1,x);
    return 0;
}

2.拓扑排序

拓扑排序吧，你说它很难绝对是不对的，但它牵扯到最长路，基环树、二维莫队这些玩意儿，你又不能说它简单。

拓扑排序可以把图变成一个一维序列，这个一维序列满足实际问题中的先后顺序。

我一直都觉得这句话比较废话，你就姑且认为拓排可以把图变成一个有一定顺序的线性序列吧。

那怎么做呢？我们来思考。

我们考虑把实际问题中的事情抽象为点，事情的依赖（先后）关系抽象为有向边（无向边还算什么依赖？），为了讨论方便，我们将边的方向设定成先完成→后完成

实际问题中，最先要做的事情之前显然没有要做的事情（废话吧），抽象成图后，它所代表的点不会是任何一条边的终点（不会在哪个事件后完成），那么我们就找到拓排的起点了。

然后我们直接选择删掉这个点，以及以它为起点的所有边，那么所有的点连接的边的数目都会减一（剪掉重边的数目，如果有重边的话），如果再次有点满足起点的条件，那就把它扔进起点候选队列呗[doge]。

对于一个点所连接的边的数目，我们称为度数，对于有向图，以这个点为起点的边的数目称为出度，以这个点为终点的边的数目称为入度。显然一个点为起点的充要条件是入度为0。对于每个点的度数，我们直接开个degree数组维护就行。

值得一提的是，拓扑排序不仅要求图是有向的，并且要求图中没有环，什么意思呢？考虑以下邻接表数据，第一行为点数n和边数m。

4 4
1 2
2 3
3 4
4 1

很明显整个图就是四元环，每个点都有先于它的点，显然是没有拓扑序的。因为找不出最先完成谁，即以谁为起点。

那么因为这种优良的对数据过敏的性质，我们可以用拓扑排序来判定一个有向图是否有环（忽略边权正负问题）。

我们设置一个cnt，每遍历到一个点就加一，如果cnt > n，那肯定是有点没删掉（不然就n个点，你怎么走到n后面去），这时，我们按照题目要求，该输出No输出No，该输出NO输出NO，该输出不可以，总司令就输出不可以，总司令。

接下来就做个模板题吧~

习题2.1.1

B3644 【模板】拓扑排序/家谱树

没什么要注意的了，就把题A了就行了。

AC Code：

#include<bits/stdc++.h>
using namespace std;
const int maxn=205;
//#define DEBUG

int edges[maxn][maxn];
int degree[maxn];
queue<int>q;
int cnt=0;

void toposort(int s,int n)
{
    for(int i=1;i<=n;i++)
    {
        if(degree[i]==0)q.push(i);
    }
    int buf=0;
    while(!q.empty())
    {
        buf=q.front();
        q.pop();
        cout<<buf<<' ';
        cnt++;
        for(int i=1;i<=n;i++)
        {
            if(edges[buf][i]==1)
            {
                edges[buf][i]=0;
                degree[i]--;
                if(degree[i]==0)q.push(i);
            }
        }
    }
}

int main()
{
    int n=0,u=0,v=0;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        do
        {
            cin>>v;
            edges[i][v]=1;
            degree[v]++;
        }
        while(v>0);
    }
    #ifdef DEBUG
    cout<<"edges:"<<endl;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            cout<<edges[i][j];
            if(j<n)cout<<' ';
        }
        if(i<n)cout<<endl;
    }
    cout<<endl;
    cout<<"degree:"<<endl;
    for(int i=1;i<=n;i++)
    {
        cout<<degree[i];
        if(i<n)cout<<' ';
    }
    cout<<endl;
    cout<<endl;
    #endif
    toposort(u,n);
    return 0;
}

3.最小生成树

最小生成树MST，是指在一个图中，保留n-1条边，使其边权和最小。名字的来源是树有且只有n-1条边，可以证明，若有n条边，则必定会形成一个环，若边数小于n-1，则图不可能连通，即有点会没有边相连。

注意到对于无向图，最小生成树所形成的图是保证点两两连通的边数最少的形式。这是它的实际意义。

对于有向图，情况比较复杂。我们可以采用朱刘算法，比如JSOI2008就有一道例题。但经验表明，在我们的目标等级，有向图的最小生成树并不多见，所以我们完全可以鸽掉，省一点时间。本文介绍求无向图的最小生成树两种经典算法。

3.1 kruskal

我们观察，发现既然最小生成树使点两两连通，那么所有的点必然都属于一个大的集合，我们可以称大集合为连通块。

那么我们可以考虑给每个点记录它所属的集合，然后将边按边权从小到大排序，从最小的边开始，一条一条边考虑。

我们选择一个边，当且仅当这条边的两个端点所属的集合不同。这样，我们就选择这条边，并将边权累加至答案以统计贡献。最后，将两个端点的集合合并。

当只剩下一个集合时，说明点已两两连通，满足MST的定义。此时可以输出答案。

如果边已完成遍历，而仍然有多个集合时，我们认为这张图的MST无解，这可能是有点不是任何一条边的端点造成的。

描述很啰嗦，但是写起来还是很容易的，而且kruskal基于并查集的思想，在优化算法下，并查集的复杂度为O(n\alpha(n))，其中\alpha(n)为阿克曼函数的反函数，在算法竞赛的规模中一般是不大于4的常数，我们可以认为是个大常数的O(n)，再不济，kruskal的复杂度也是O(n\log n)。好写、跑得快，场上可以优先选择。

习题3.1.1

P3366 【模板】最小生成树

OK，动手！

如果图不连通，你应当输出orz

AC Code：

#include<bits/stdc++.h>
using namespace std;
const int maxn=5e3+5;
const int maxm=2e5+7;

int fa[maxn];
int sz[maxn];

void set_make(int len)
{
    for(int i=1;i<=len;i++)
    {
        fa[i]=i;
        sz[i]=1;
    }
}

struct edge
{
    int a;
    int b;
    int c;
};

edge edges[maxm];

bool operator <(edge x,edge y)
{
    if(x.c<y.c)return true;
    else return false;
}

int find(int n)
{
    if(fa[n]==n)return fa[n];
    else return fa[n]=find(fa[n]);
}

bool merge(int x,int y)
{
    x=find(x);
    y=find(y);
    if(x==y)return false;
    else
    {
        //if(sz[x]>sz[y])swap(x,y);
        fa[x]=y;
        sz[y]+=sz[x];
        return true;
    }
}

/*bool check(int len)
{
    int cnt=0;
    for(int i=1;i<=len;i++)
    {
        cout<<fa[i]<<' ';
        if(fa[i]==i)
        {
            cnt++;
            if(cnt>1)return false;
        }
    }
    cout<<endl;
    return true;
}*/

int main()
{
    int n=0,m=0,res=0;
    cin>>n>>m;
    set_make(n);
    for(int i=1;i<=m;i++)
    {
        cin>>edges[i].a>>edges[i].b>>edges[i].c;
    }
    sort(edges,edges+m+1);
    for(int i=1;i<=m;i++)
    {
        //if(m==1)cout<<edges[1].c; //不需要考虑
        /*if(check(n)==true)
        {
            cout<<res;
            return 0;
        }*/
        if(merge(edges[i].a,edges[i].b)==false)
        {
            //cout<<"DON'T"<<endl;
            continue;
        }
        else
        {
            //cout<<"Add edge between "<<edges[i].a<<' '<<" and "<<edges[i].b<<endl;
            res+=edges[i].c;
            n--;
            //cout<<"Now there are "<<n<<" sets"<<endl;
            if(n==1)
            {
                cout<<res;
                return 0;
            }
        }
    }
    cout<<"orz";
    return 0;
}

3.2 prim

考虑前面对于MST的定义，注意到“选取最小的边”这条要求也可以等价为每个点所连接的边的边权最小。这样，我们可以先确定每个点的答案，再累加后输出。

怎么确定每点的答案呢？根据一些教材的说法，如果没有最短路的基础，理解prim的思想会有些困难，事实上，没有prim的基础，理解最短路的思想也会有些困难。[doge]总之它们写法相近就是了。

我们先设立mins数组，每个元素初始化为一个极大的数（要求的是最小生成树）

然后我们选取一个点x作为起点，将mins[i]置0。

我们从当前的mins中选取值最小的一个位置，并遍历它的每条边，对于每条边的另一个端点，如果它没有被访问过，且当前边的边权小于它的mins，那么显然可以修改它的mins。

这个思想显然是贪心，可以证明这个贪心的正确性。

如果在算法完成后，仍有点的mins等于初始化的最大值，那么显然它没有任何边连接，即整张图不连通，我们认为这张图的MST无解。

习题3.2.1

P3366 【模板】最小生成树

我们发现这个dp数组太大了，大到只能承受约1e2个点，不满足我们的需要。

注意到数组k一维在状态转移方程中并无实质性作用，而且最终答案还要处理成\max_{k=1}^n(dp[i][j][k])，增大隐形常数。所以，我们可以考虑将k一维舍去，只保留dp[i][j]，整理其他式子。

但在循环中，我们还需要保留k的处理，因为仍然有k。所以仍有三层循环。

习题4.2.1

P3371 【模板】单源最短路径（弱化版）

OK，动手！

AC Code：

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e4+5;
const int maxm=4.5e+7;

struct edge
{
    int to;
    int last;
    int val;
};
edge e[maxm];
int head[maxn];
int vis[maxn];
int dist[maxn];
queue<int>q;
int tot=0;

inline void adde(int a,int b,int c)
{
    e[++tot].last=head[a];
    e[tot].to=b;
    e[tot].val=c;
    head[a]=tot;
}

void spfa(int n,int x=1)
{
    memset(dist,0x3f,sizeof(dist));
    q.push(x);
    dist[x]=0;
    vis[x]=1;
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        vis[u]--;
        for(int i=head[u];i!=0;i=e[i].last)
        {
            int v=e[i].to;
            if(dist[v]>dist[u]+e[i].val)
            {
                dist[v]=dist[u]+e[i].val;
                //cnt[i]=cnt[u]+1;
                //if(cnt[i]>=n)return false;
                if(!vis[v])
                {
                    vis[v]++;
                    q.push(v);
                }
            }
        }
    }
    //return true;
}

int main()
{
    int n=0,m=0,s=1;
    cin>>n>>m>>s;
    //build(n,m);
    int a=0,b=0,c=0;
    for(int i=1;i<=m;i++)
    {
        cin>>a>>b>>c;
        adde(a,b,c);
    }
    spfa(n,s);
    for(int i=1;i<=n;i++)
    {
        if(dist[i]==0x3f3f3f3f)
        {
            cout<<2147483647;
            if(i<n)cout<<' ';
            continue;
        }
        cout<<dist[i];
        if(i<n)cout<<' ';
    }
    return 0;
}

其实spfa为什么会被卡的这么死，我也不是很清楚，但是只要没负边权，你就用下面这个算法吧。

4.3 dijkstra

这个有什么用吧，没见过。只是有些题解说要提前判两点连通，可能会用这个？难绷。

习题5.2.1

B3611 【模板】传递闭包

它甚至是入门题库……

AC Code：

#include<bits/stdc++.h>
using namespace std;
const int maxn=105;

int graph[maxn][maxn];
bool dis[maxn][maxn];

int main()
{
    int n=0;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            cin>>graph[i][j];
            dis[i][j]=(graph[i][j]==1?true:false);
        }
    }
    for(int k=1;k<=n;k++)
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                dis[i][j]=dis[i][j]||(dis[i][k]&&dis[k][j]);
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            cout<<dis[i][j];
            if(j<n)cout<<' ';
        }
        if(i<n)cout<<endl;
    }
    return 0;
}

5.3 判负环&&差分约束

因为是环，肯定是一个点跑了一圈发现回到了自己，所以我们采用单源最短路的做法。

诶，你要找负环嘞！关于dijkstra，它死了。关于spfa，它复活了

与拓扑排序的思想类似，如果我们用spfa跑了超过n个点，那肯定也是出现了个环，我们退出来就行了。但是由于spfa并没有固定的vis标记（取队头后vis置零），那我们要头疼的就有很多了。

我们的解决方案是拿空间换编码难度，直接开个cnt数组记录每个点的路过，如果有一个点经过了n次以上，那总不对劲了吧！同理，松弛成功后，我们也应该在cnt基础上转移，而不是简单的++。

再提一句，正权会收敛，最终队列会为空，所以spfa只能判负环。

习题5.3.1

P3385 【模板】负环

你别觉得这个很简单，拿spfa模板改一晚你都不一定能过……

AC Code：

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e3+5;
const int maxm=5e6;

struct edge
{
    int to;
    int last;
    long long val;
};
edge edges[maxm*2];
int head[maxn];
int vis[maxn];
int cnt[maxn];
long long dist[maxn];
queue<int>q;
int tot=0;

inline void adde(int a,int b,int c)
{
    edges[++tot].to=b;
    edges[tot].last=head[a];
    edges[tot].val=c;
    head[a]=tot;
}

bool spfa(int n,int s)
{
    memset(dist,0x3f,sizeof(dist));
    memset(vis,0,sizeof(vis));
    q.push(s);
    dist[s]=0;
    vis[s]=1;
    cnt[s]++;
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(int i=head[u];i!=0;i=edges[i].last)
        {
            int v=edges[i].to;
            if(dist[v]>dist[u]+edges[i].val)
            {
                dist[v]=dist[u]+edges[i].val;
                if(!vis[v])
                {
                    cnt[v]++;
                    if(cnt[v]>=n)return false;
                    q.push(v);
                    vis[v]=1;
                }
            }
        }
    }
    return true;
} 

int main()
{
    int t=0,n=0,m=0,u=0,v=0,w=0;
    bool flag=true;
    cin>>t;
    for(int i=1;i<=t;i++)
    {
        while(!q.empty())
        {
            q.pop();
        }
        memset(head,0,sizeof(head));
        memset(edges,0,sizeof(edges));
        memset(cnt,0,sizeof(cnt));
        tot=0;
        cin>>n>>m;
        for(int i=1;i<=m;i++)
        {
            cin>>u>>v>>w;
            if(w>=0)
            {
                adde(u,v,w);
                adde(v,u,w);
            }
            else
            {
                adde(u,v,w);
            }
        }
        flag=spfa(n,1);
        cout<<(flag==false?"YES":"NO");
        if(i<t)cout<<endl;
    }
    return 0;
}

好，接下来是判负环的最重要应用：差分约束

差分约束，也常叫差分约束系统，指的是对于如下不等式组：

问是否能找到一组整数解，使得所有的不等式都成立，而且可以证明，对于有解的情况，必然有无数组解，因为在一组解上加上任意一个正整数都能使原不等式成立，这是不等式的基本性质。

那么，我们的问题就是怎么判无解。

首先，我们考虑能不能将其转化为一个信息学中有算法的问题，不然这事儿应该左转MO。

注意到我们学单源最短路的时候学的神操作：松弛。它的式子一般是这样的：

诶，不错哦！看来每一条这样的式子都对应了一条边呢！那我们就考虑用跑单源最短路，把这些解搞出来。

我们把一个原不等式建模成由被减数连向减数的一条权值为c的边。那么我们跑出来的dist数组肯定就是一组解！

那我们再联想，spfa刚不说过了吗，无解的情况是有负环，那我们判无解可不可以借助这条性质呢？

答案是可以的。因为就算原不等式组你减我，我减他，他减你这么形成一个环，如果是正环，spfa可以自己消掉，无所畏惧。但是负环的话，几个未知数可以通过这个环不断自减，最后减到-\infty。事实上，在不等式中，减负数是能改变方向的，所以负环不行。

关于为什么会有负边权，为什么dijkstra不行，我只能说差分约束问题的难点在建边，如何把原不等式正确的转化成图的边。这里实在无力证明，从网站上扒张可信的表吧（

• x_a-x_b\ge c

转化成x_b-x_a\le -c，加边为adde(a,b,-c)

• x_a-x_b\le c

转化成x_a-x_b\le c，加边为adde(b,a,c)

• x_a=x_b

转化成x_a-x_b\le 0\&\&x_b-x_a\le 0，加边为adde(b,a,0),adde(a,b,0)

习题5.3.2

P5960 【模板】差分约束

说实话，这个也没怎么用过……

AC Code：

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
const int maxm=5e6;

struct edge
{
    int to;
    int last;
    long long val;
};
edge edges[maxm*2];
int head[maxn];
int vis[maxn];
int cnt[maxn];
long long dist[maxn];
queue<int>q;
int tot=0;

inline void adde(int a,int b,int c)
{
    edges[++tot].to=b;
    edges[tot].last=head[a];
    edges[tot].val=c;
    head[a]=tot;
}

bool spfa(int n,int s)
{
    memset(dist,0x3f,sizeof(dist));
    memset(vis,0,sizeof(vis));
    q.push(s);
    dist[s]=0;
    vis[s]=1;
    cnt[s]++;
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(int i=head[u];i!=0;i=edges[i].last)
        {
            int v=edges[i].to;
            if(dist[v]>dist[u]+edges[i].val)
            {
                dist[v]=dist[u]+edges[i].val;
                if(!vis[v])
                {
                    cnt[v]++;
                    if(cnt[v]>=n+1)return false;
                    q.push(v);
                    vis[v]=1;
                }
            }
        }
    }
    return true;
} 

int main()
{
    int n=0,m=0,u=0,v=0,w=0;
    bool flag=true;
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>u>>v>>w;
        adde(v,u,w);
    }
    for(int i=1;i<=n;i++)
    {
        adde(0,i,0);
    }
    flag=spfa(n,0);
    if(flag==false)
    {
        cout<<"NO";
        return 0;
    }
    for(int i=1;i<=n;i++)
    {
        cout<<dist[i];
        if(i<n)cout<<' ';
    }
    return 0;
}

5.4 割点/割顶/割边/桥

这两个知识点名字是真的多……

割点和割边就是指删掉这个点或边以后，能使原图中的强连通分量增加，就是这么个意思。因为割边感觉像是一座桥，如果砍断，两边就失去了联系（即强连通分量增加），所以又把割边叫桥。割点下面再说。

如何判定呢？我们可以考虑删掉每条点或边，然后暴力tarjan判断。复杂度直接上升到O(n(n+m))或者O(m(n+m))，题目容易超时，那我们要不要再考虑一下直接对tarjan做个优化，维持原复杂度呢？

我们就来研究下割点和割边的性质，先研究割点的：

有一个感性的想法，割点一定是某个SCC的点对外连通的点，这样把它割掉以后这个SCC就没有对外连通的点了，free了，肯定可以使连通块个数增加。而且可以证明如果一个对外连通的点是割点，那么它所在的SCC一定只有一个对外连通的点，反之，这个点割掉了，SCC里的其他点还有路能够连通图的其他部分，那肯定不能增加SCC的数目，就不满足定义了（

上面这句加粗的话还是比较抽象，我们可以更加具化一点嘛？其实就是，对于后面搜到的SCC，它能连通的图中其他的点必然都比它先遍历，怎么衡量这个“先遍历” 呢？诶，用dfn和low吧！

一个点x是割点，当且仅当\exist一个点y是SCC内部的点，y最早能到达的点都比x后遍历，或者刚好能够到x，也就是low[y]\ge dfn[x]。这样，y不经过x，就无法到达SCC外的点，那把x割掉，y就“与世隔绝”了，SCC的数目就增加了。

注意这里不要求x所在的SCC里的所有的点都满足，而是只要一个就够了。就算只能能隔离一个，只要SCC数目增加了，也是割点嘛！

而且我们可以不用把每个点的SCC判出来再判割点，那样会提高复杂度，我们发现在tarjan回溯时就可以确定每个点的low了，那我们就直接在回溯时紧接着low[x]的更新判定low[y]\ge dfn[x]。这样不会增长复杂度，还是tarjan的O(n+m)

但是对根节点（你可以认为是在main里调用tarjan时传入的节点）需要进行特判，它至少要有两个点满足这种情况才能看成割点，为什么呢？我们看一幅无向图：

4 5
1 2
1 4
2 3
2 4
3 4

假如我们从1搜进去，那么根节点就是1，此时，你把1割掉，2，3，4依然能构成一个SCC，SCC的数目由1到1，不满足割点的定义。

那为什么要把割点叫做割顶呢？因为在一个图上，一个SCC基本表现为一个多边形，那点不就是多边形的顶点！所以也可以叫割顶嘛！

好了，接下来把模板题快速过掉！

习题5.4.1

P3388 【模板】割点（割顶）

这下标准明确了，先判掉要不要不可以总司令

如果可以的话，我们来想怎么实现dfs

我们再考虑定义：欧拉路是一笔画，每条边只能走一次，但……点好像没有特殊性质。

但朴素的dfs可是靠点的vis来判断终止的啊！这下真就“停不下来”了！

诶，还有一个办法，既然点没限制，边有限制，那我们就给边打vis吧！

我们定义一个结构体edge，包含边的终点和vis，再把熟悉的vector<int> graph[maxn]换成vector<edge> graph[maxn]，这样不就给边打上花火打上vis了吗！good

然后，我们开始dfs，遍历传入点的每条边，如果这条边还没访问过，那我们就打好vis，以它的另一个端点为起始点进行dfs，在全部边都访问完后，我们就可以将起始点输出了。

你以为结束了？no way！你会发现，打印的路径和答案刚好相反？！怎么回事！

你是dfs啊，你在所有边都搜完后才把点保存输出啊！你试试，按“1起-1终”的规则，结果你的起始点是不是最后打印？要不得啦！

那咋办咧？你开个栈，把输出换成入栈不就行了吗！

在dfs()全部执行完后，再打一个弹一个，OKAY。

理论上有向图和无向图的欧拉dfs()只有建图的区别，你写写下面两道题，确实难点基本上只在处理度数。

习题6.1.1

P7771 【模板】欧拉路径

本题为div.有向图。

这里解释一下，本题的euler()和习题6.1.2的有一些不相同。

这是因为加了一些优化。

讨论区把这种优化称为“当前弧优化”。

具体来说，我们在遍历一个点的每条边时，如果还要一条一条查边的vis，有点费时间，我们可以空间换时间，开一个now数组，然后每给一条边打vis，在递归之前，我们就给起始点的now置为当前边的编号+1，循环时i直接置为now[起始点]，然后也别机械i++了，直接让i+1和now[起始点]打擂台，给i赋最大值。

这样就跳掉了已经打vis的边，连if都不跑了，你就说快不快吧doge。如果不这么写，You will get only \color{#E74C3C}{90pts} \color{#052242}{with} \color{#052242}{testcase10TLE}，写了后，那个点直接掉到<100ms，让我感觉出了个专门卡优化的点，但是我没有证据。

AC Code：

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+7;
const int maxm=2e5+7;

struct edge
{
    int to;
    int vis;

    friend bool operator <(edge a,edge b)
    {
        return a.to<b.to;
    }
};
vector<edge>graph[maxn];
int degree[maxn];
int s=0;
int t=0;
stack<int>ans;
int now[maxn];

inline void adde(int u,int v)
{
    graph[u].push_back({v,0});
    degree[u]++;
    degree[v]--;
}

void euler(int x)
{
    for(int i=now[x];i<graph[x].size();i=max(i+1,now[x]))
    {
        if(!(graph[x][i].vis))
        {
            graph[x][i].vis=1;
            now[x]=i+1;
            euler(graph[x][i].to);
        }
    }
    ans.push(x);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n=0,m=0,u=0,v=0,cnt=0;
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>u>>v;
        adde(u,v);
    }
    for(int i=1;i<=n;i++)
    {
        if(degree[i]==1)
        {
            if(s!=0)
            {
                cout<<"No";
                return 0;
            }
            s=i;
        }
        else if(degree[i]==-1)
        {
            if(t!=0)
            {
                cout<<"No";
                return 0;
            }
            t=i;
        }
        else if(degree[i]==0)
        {
            cnt++;
        }
        else
        {
            cout<<"No";
            return 0;
        }
    }
    for(int i=1;i<=n;i++)
    {
        sort(graph[i].begin(),graph[i].end());
    }
    if(cnt==n)euler(1);
    else euler(s);
    while(!ans.empty())
    {
        int buf=ans.top();
        ans.pop();
        cout<<buf;
        if(!ans.empty())cout<<' ';
    }
    return 0;
}

习题6.1.2

P2731 [USACO3.3]骑马过栅栏 Riding the Fences

本题为div.无向图。

你说优化为什么没有？因为它数据规模小[doge]

AC Code：

#include<bits/stdc++.h>
using namespace std;
const int maxn=505;
const int maxm=1e4+7;

int graph[maxn][maxn];
int degree[maxn];
int anss=0;
int anst=0;
vector<int>ans;

inline void adde(int u,int v)
{
    graph[u][v]++;
}

void euler(int len,int s)
{
    for(int i=1;i<=len;i++)
    {
        if(graph[s][i]==0)continue;
        graph[s][i]--;
        graph[i][s]--;
        euler(len,i);
    }
    ans.push_back(s);
}

int main()
{
    int m=0,u=0,v=0,cnt=0,num=0;
    cin>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>u>>v;
        adde(u,v);
        adde(v,u);
        num=max(num,max(u,v));
        degree[u]++;
        degree[v]++;
    }
    int s=1;
    for(int i=1;i<=num;i++)
    {
        if(degree[i]%2==1)
        {
            cnt++;
            s=i;
            break;
        }
    }
    if(cnt!=0)euler(num,s);
    else
    {
        for(int i=1;i<=num;i++)
        {
            if(degree[i]!=0)
            {
                euler(num,i);
                break;
            }
        }
    }
    for(int i=ans.size()-1;i>=0;i--)
    {
        cout<<ans[i]<<endl;
    }
    return 0;
}

再强调一声，欧拉图要求图要连通！！！

如果图不连通，你应当输出orz——P3366【模板】最小生成树

开个玩笑啊，你别每题都只记得输出orz了[doge]。

6.2 二分图简介

二分图也是个变化多端的知识点，虽然母题模型不多，但是别的奇葩量有一大堆。限于目标要求，本文主要介绍二分图的判定和二分图最大匹配。

首先来了解二分图的定义，如果能把一个图的点划分为两个集合，集合内部的点两两没有边相连，那这就是个二分图。

首先是一个显然的性质，一个图是二分图的充要条件是其不含奇环。因为集合内部没有边，肯定要走偶数次才能回到自己的集合，你可以手画一个。

有了这个性质，我们就可以开始判定了。

还是万能的dfs，怎么把“集合内部没有边”加进去呢

一个普遍的方法是染色，我们把遍历到的节点交替染色，如果搜到的节点颜色重合了，那就染不成了，因为边都是连接两个不同集合，如果有一条边两端颜色相同，那显然不行。

而且，我们还要把“不行”传递上来，所以，如果判断到回溯时产生“不行”的信号，那本层也是返回“不行”，不行就要不行到底，中途可以怎么行？

好，切模板题时间。

习题6.2.1

P1330 封锁阳光大学

你们也喜欢用NOIP2010T1当二分图判定例题，但我已经把它划给并查集了，为了提交数，我们尽量不重题哈。doge

因为二分图并没有要求图是连通的（不连通也可以划到一个集合里嘛），所以我们要以每个点为起点，都搜一遍，把答案累加，才能输出。

这个坑点竟然没有hack，我要造一组。

AC Code：

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e4+5;
const int maxm=1e5+7;

struct edge
{
    int to;
    int last;
};
edge edges[maxm*2];
int head[maxn];
int tot=0;
int vis[maxn];
int ans[3];
int res=0;

inline void adde(int a,int b)
{
    edges[++tot].to=b;
    edges[tot].last=head[a];
    head[a]=tot;
}

bool dfs(int s,int op)
{
    ans[op]++;
    vis[s]=op;
    for(int i=head[s];i!=0;i=edges[i].last)
    {
        int v=edges[i].to;
        if(!vis[v])
        {
            if(dfs(v,3-op)==false)return false;
        }
        else if(vis[v]==op)return false;
    }
    return true;
}

int main()
{
    int n=0,m=0,u=0,v=0;
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>u>>v;
        adde(u,v);
        adde(v,u);
    }
    for(int i=1;i<=n;i++)
    {
        if(!vis[i])
        {
            memset(ans,0,sizeof(ans));
            if(dfs(i,1)==false)
            {
                cout<<"Impossible";
                return 0;
            }
            res+=min(ans[1],ans[2]);
        }
    }
    cout<<res;
    return 0;
}

接下来学习二分图的一个著名问题：最大匹配。当然它还有完美匹配和最大权匹配几个变种，并且匹配的概念也可以推广到一般图上，但我们不管那么多了（

所谓二分图最大匹配，就是问你在二分图的两个部分中间能有多少对点配对。所谓配对，也就是直接的有边相连，只是说由于题目给的逗霸连边，很有可能有多种配对方案，每种配对方案能凑出几个配对，我们称为配对数是几。最大匹配要求的就是配对数最大的一种方案。

关于这个问题有两种算法，但是根据我们的懒惰目标要求，我们只学一种“匈牙利算法”。我绝对不会告诉你另一种算法对网络流的衔接更有帮助

你们可能都听过所谓“Re：最大匹配之网络流の降维打击”但我觉得O(n\sqrt m)的复杂度吸引力不是很大，所以我们讲网络流时你可以自己想想。

接下来我们学习匈牙利算法，它基本上是对一边的点每个点跑一遍dfs()。但这个dfs()有一定的改编，而且递归中的改参数过程异常毒瘤让我想起了treap

我们想想，按照最初的定义，我们该怎么求最大匹配。一个很显然的想法是对于同一部分的每个点，逐个扫所有边，如果选择这条边那一头的端点没事，那就连呗；如果让出这个点去跟别的点配对能够让其他同部分点配对，那就相当于配对数可以增加，对答案有增益，我们当然要这么干。

我们考虑对匹配的那个部分（扫边的）建一个match[maxn]数组，表示另一部分中的每个点应该在这一部分中找哪个点配对，这里我们将两部分的点分开编号（即都是1~n）。

我们人为规定从左部分扫描边，匹配右部分。

然后，因为有dfs()成分，所以我们先写一个dfs()，然后也写个vis。对左部分的每个点，我们跑次dfs()。但是vis我们打的是表示右部分的点。

在dfs()内，对于每个右端点，我们能将它匹配有两个条件：

• 它和传入左端点有边相连

• 它还没被访问过，vis为空

这两个条件必须都满足。这时，我们给这个右端点打上vis，但是还不能最终确定！因为可能牺牲这对配对会有更多的配对！难绷。

那我们再思考一下，什么情况能够确定匹配呢？

• 这个右端点还没有被匹配，我们暂时给它涂上

• 这个右端点已经被匹配过了，但它的原配能找到更好的点

肯定嘛，对方有别的对象了，肯定是匹配方重新找嘛(bushi)

显然这两个条件有一个能满足，我们就可以将传入左端点和这个右端点配对了喜大普奔，发个invitationtrue回去。

如果右部分所有点都遍历完了，传入左端点依然没有配对的点，那就只能扔个false回去了（

这样我们的dfs()就大功告成了！匈牙利算法的主函数只要对左部分的每个点都跑遍dfs()，有一个点成功就rp++就可以了！还是很简单的！（bushi）

顺带一提，我们在每个点dfs()走过的路径叫做增广路，二分图求匹配相关问题的过程，也就是不断找增广路的过程。

匈牙利算法的复杂度为O(nm)，n为两个部分的点数和，m为总边数。

最后还有一个概念：假设选一个点就代表“覆盖”了这个点和所有以这个点为端点的边，我们也很关心最少选几个点，能够覆盖所有的边，这个问题就是最小点覆盖问题。

对于这个问题，我们不加证明地给出\mathrm{k\ddot{o}nig}定理：

最小点覆盖数=最大匹配数

刷题时会用到。

习题6.2.2

P3386 【模板】二分图最大匹配

AC Code：

#include<bits/stdc++.h>
using namespace std;
const int maxm=5e2+5;
const int maxn=5e2+5;
const int maxe=5e4+7;

int graph[maxn][maxm];
int vis[maxn];
int match[maxn];
int cnt;

bool dfs(int n,int len)
{
    for(int i=1;i<=len;i++)
    {
        if(graph[n][i]&&!vis[i])
        {
            vis[i]++;
            if(match[i]==0||dfs(match[i],len))
            {
                match[i]=n;
                return true;
            }
        }
    }
    return false;
}

int hagarian(int left,int right)
{
    int res=0;
    for(int i=1;i<=left;i++)
    {
        memset(vis,0,sizeof(vis));
        if(dfs(i,right))++res;
    }
    return res;
}

int main()
{
    int n=0,m=0,e=0;
    cin>>n>>m>>e;
    for(int i=1;i<=e;i++)
    {
        int a=0,b=0;
        cin>>a>>b;
        graph[a][b]=1;
    }
    if(n==1&&m==1&&e!=0)
    {
        cout<<1;
        return 0;
    }
    int res=hagarian(n,m);
    cout<<res;
    return 0;
}

2024/8/28 20:25:00 初稿！完结撒花！