头像

Mrhh

西南科技大学


访客:14620

离线:7小时前


活动打卡代码 AcWing 379. 捉迷藏

Mrhh
12天前

Analysis

  • 这K个藏身点的任意两个之间都没有路径相连

    对于这k个点, 我们显然可以发现, 对于该图的最小可相交路径覆盖的路径条数, 由于这些路径将所有点覆盖了, 所以我们对于这些路径, 每条路径选出一个点(注意是让你选出最多的点(都选路径的起点), 如下图), 这些点互不相通(因为图是dag), 即最大点数. 那么ans = dag的最小可相交路径覆盖的路径条数.

7.png

Accepted Code

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 210, M = 30010;

int n, m;
bool d[N][N], st[N];
int match[N];

bool find(int x)
{
    for (int i = 1; i <= n; i ++ )
        if (d[x][i] && !st[i])
        {
            st[i] = true;
            int t = match[i];
            if (t == 0 || find(t))
            {
                match[i] = x;
                return true;
            }
        }

    return false;
}

int main()
{
    scanf("%d%d", &n, &m);
    while (m -- ) // 建图时不需要实现拆点  直接把入边顶点拉过去就行 类似网格图的建图方式
    {
        int a, b;
        scanf("%d%d", &a, &b);
        d[a][b] = true;
    }

    // 传递闭包
    for (int k = 1; k <= n; k ++ )
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= n; j ++ )
                d[i][j] |= d[i][k] & d[k][j];

    int res = 0;
    for (int i = 1; i <= n; i ++ )
    {
        memset(st, 0, sizeof st);
        if (find(i)) res ++ ;
    }

    printf("%d\n", n - res);

    return 0;
}


活动打卡代码 AcWing 378. 骑士放置

Mrhh
13天前

Analysis

  • 问棋盘上最多能放多少个不能互相攻击的骑士(能攻击就是两点之间有边)

    就是从图中选出最多的点集, 使得点与点之间两两无边. – 最大独立集问题

  • 对于网格图, 将点分成奇点和偶点, 我们分析题目, 对于每个点(x, y)的跳动, 它只能是x + 奇数(-1, 1) + y + 偶数(-2, 2), 奇数 + 偶数 = 奇数, 就是说一个点跳动之后, 其奇偶性必然会变化. 也就是边的两个点必然属于两个不同的点集, 该图为二分图. 求二分图的最大独立集 = 总点数 - 最大匹配(最小点覆盖)

Accepted Code

#include <iostream>
#include <cstring>

using namespace std;

typedef pair<int, int> pii;

const int N = 110;

int n, m, k;
bool g[N][N], vis[N][N];
pii match[N][N];

int dx[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
int dy[8] = {1, 2, 2, 1, -1, -2, -2, -1};

bool find (int x, int y)
{
    for(int i = 0 ; i < 8 ; i ++ )
    {
        int tx = x + dx[i];
        int ty = y + dy[i];

        if(tx < 1 || tx > n || ty < 1 || ty > m) continue;
        if(g[tx][ty] || vis[tx][ty]) continue;

        vis[tx][ty] = 1;
        pii t = match[tx][ty];
        if(!t.first || find(t.first, t.second))
        {
            match[tx][ty] = {x, y};
            return true;
        }
    }

    return false;
}

int main ()
{
    cin >> n >> m >> k;
    for(int i = 0 ; i < k ; i ++ )
    {
        int a, b;
        cin >> a >> b;
        g[a][b] = 1;
    }

    int res = 0;
    for(int i = 1 ; i <= n ; i ++ )
        for(int j = 1 ; j <= m ; j ++ )
            if(!g[i][j] && (i + j) % 2)
            {
                memset(vis, 0, sizeof vis); // 每波找都是新的开始, 在过程中才知道该点能不能被匹配
                if(find(i, j)) res ++ ;
            }

    cout << n * m - k - res << endl;

    return 0;
}



Mrhh
13天前

二分图一般都是无向图问题, 但是因为我们只需要依次枚举一个点集中的点来分配对象,所以往往我们在代码实现时, 存边只存单向边。

要看一个图是不是二分图(染色法: 对于网格图奇点和偶点, 染色是不同的, 我们只需要看边是否都只在两个点集之间的), 我们主要看图的边的两个顶点是否都能被归为两种不同性质的点集, 而边只能在两个点集之间.

注: 二分图不一定有匹配, 下图就是一个二分图但是其无匹配

2.png


1.png

染色法判断二分图

匈牙利算法(前提是图为二分图, 求的是二分图的最大匹配) – 模板见基础课打卡

该算法的vis数组的理解很重要 见基础课打卡代码详解
(两点之间有边, 能互通, 就有可能形成一组匹配)

注: 下面的概念非二分图特有, 图都有

匹配/匹配边: 与其他边没有公共节点的一条边, 我们称这条边为一个匹配/匹配边.
匹配点: 匹配边上的点
非匹配点: 不在匹配边上的点
非匹配边: 图中两点之间的边不是匹配边的边
最大匹配(匹配边数量的最大值): 最多连多少条边, 使得所有的边无公共点
增广路(径): 一边的非匹配点到另一边的非匹配点的一条非匹配边和匹配边交替经过的路径. (只要有一条增广路径就能多一组匹配, 最大匹配 $\Leftrightarrow$ 不存在增广路径)

最小点覆盖问题

定义: 给我们一个图(任意), 我们从中选出最少的点, 使得图中的每一条边至少有一个顶点被选.

二分图的最小点覆盖问题

二分图的最小点覆盖 = 二分图的最大匹配数
如下图, 最大匹配为3(3条匹配边), 最小点覆盖(3个点)
3.png
例题

最大独立集问题(NPH问题)

定义: 从图中选出最多的点, 使得选出的点集中任意两点之间没有边.

  • 最大团

    原图的最大独立集就是补图(原图有的边去掉, 没的边加上)的最大团

二分图中的最大独立集问题

最大独立集 = 二分图的总点数 - 最大匹配
例题

最小路径点覆盖问题(最小路径覆盖问题)

分类:
1. 最小不相交路径覆盖: 对于一个dag来说, 用最少的互不相交(路径无公共点)的路径, 遍历所有的点.
2. 最小可相交路径覆盖: 对于一个有向图来说, 用最少的路径, 遍历所有的点.
4.png

二分图算法求解最小不相交路径覆盖问题

  • 拆点: 对于每个顶点, 我们建一个相对它的新点, 如图所示 (我们可以联想到, 那么我们求一般图的其他问题, 是否能将其拆点转化为二分图在求呢???)

    5.png

然后我们将i -> j的一条边转化为i -> j’的一条边, 这样的话, 这个图必然是一个二分图(边都不在内部).
结论: 最少路径 = 点数(注意是原图的点数, 非二分图的点数) - 二分图的最大匹配.
证明:
6.png

二分图算法求解最小可相交路径覆盖问题

  • 求原图的传递闭包
  • 对传递闭包求一遍最小不相交路径覆盖 = 原图的最小可相交路径覆盖
    例题


活动打卡代码 AcWing 376. 机器任务

Mrhh
13天前

Analysis

我们将机器a的所有模式放到一个点集中, 将所有机器b的所有模式放到另一个点集中, 将一个任务看作是一条ai - bi的一条边, 完成该任务, 就是选择这条边的一个顶点. 由于点集内部是不可能存在边的(一个任务只能用A/B的一种模式), 边都在两个点集的点之间, 该图为二分图. 开始的时候, 由于两个机器都处于0模式, 所以在输入任务的时候, 如果是a[0], b[0]能完成该任务的话, 我们就continue. 最终问题就转化为了, 我们在二分图中选出最少的点, 能覆盖所有的边(完成所有的任务). 最小点覆盖问题 + 二分图 = 最大匹配.

Accepted Code

#include <iostream>
#include <cstring>

using namespace std;

const int N = 110;

int n, m, k;
bool g[N][N], vis[N]; // 是否匹配到了
int match[N]; // 匹配到的对象是哪个点

bool find (int u)
{
    for(int i = 0 ; i < m ; i ++ )
    {
        if(g[u][i] && !vis[i])
        {
            vis[i] = 1; // 在找match[i]它是否有可替换的新对象时, 不能是它原来的对象, 我们用vis数组来判重
            if(!match[i] || find(match[i]))
            {
                match[i] = u;
                return true;
            }
        }
    }

    return false;
}

int main ()
{
    while(cin >> n, n)
    {
        memset(g, 0, sizeof g);
        memset(match, 0, sizeof match);

        cin >> m >> k;
        while(k -- )
        {
            int t, a, b;
            cin >> t >> a >> b;
            if(!a || !b) continue;
            g[a][b] = 1;
        }

        int res = 0;
        for(int i = 0 ; i < n ; i ++ )
        {
            memset(vis, 0, sizeof vis);
            if(find(i)) res ++ ;
        }

        cout << res << endl;
    }

    return 0;
}


活动打卡代码 AcWing 372. 棋盘覆盖

Mrhh
13天前

Analysis

  • 我们可以将骨牌看作是一条边, 那么问题就转化为了, 在图中最多找出多少条边, 使得两两之间无公共点. – 最大匹配问题
  • 我们可以通过染色法对网格图染色(拓展其出边顶点染色必定能将所有能走到的点染色且出边顶点的颜色互不相同), 我们会发现其是一个二分图.
  • 最后我们求二分图的最大匹配 – 匈牙利算法
  • 二分图中的两个不同点集: 对于网格图我们会发现, 染同一颜色的点的横纵坐标之和的奇偶性是相同的, 即奇点, 偶点.

Accepted Code

#include <iostream>
#include <cstring>

using namespace std;

typedef pair<int, int> pii;

const int N = 110;

int n, t;
pii match[N][N];
bool vis[N][N], g[N][N];

bool find (int x, int y)
{
    int dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1};
    for(int i = 0 ; i < 4 ; i ++ )  // 只能匹配这四个方向的, 二分图
    {
        int tx = x + dx[i];
        int ty = y + dy[i];

        if(tx <= 0 || tx > n || ty <= 0 || ty > n) continue;
        if(g[tx][ty] || vis[tx][ty]) continue;

        vis[tx][ty] = 1;
        auto t = match[tx][ty];
        if(t.first == -1 || find(t.first, t.second)) // tx,ty的匹配对象还有其他的选择, 那么x,y也可以匹配tx,ty
        {
            match[tx][ty] = {x, y};
            return true;
        }
    }

    return false;
}

int main ()
{
    cin >> n >> t;
    while(t -- )
    {
        int a, b;
        cin >> a >> b;
        g[a][b] = 1;
    }

    memset(match, -1, sizeof match);

    int res = 0;
    for(int i = 1 ; i <= n ; i ++ )
        for(int j = 1 ; j <= n ; j ++ )
            if(((i + j) & 1) && !g[i][j])
            {
                memset(vis, 0, sizeof vis);
                if(find(i, j)) res ++ ;
            }

    cout << res << endl;

    return 0;
}


活动打卡代码 AcWing 257. 关押罪犯

Mrhh
14天前

Analysis

  • 警察局会将本年内监狱中的所有冲突事件按影响力从大到小排成一个列表
指的是两个监狱的所有事件中的最大值最小, 求最小值就是左端点, 右区间

Solution

ans的范围[0, 1e9], 那么就是说对于不同的分配方案, 都会有一个最大值在区间里, 我们求区间最小值.
check函数: 我们能否将所有仇恨值大于mid的两个点分别分到两个不同的监狱, 使得图为二分图. 这样在同一监狱的仇恨值的最大值都是小于等于mid(mid在最大值区间里, mid必须在范围内部)的(因为大于mid的两个点都被分开了嘛~)

这个图分成两部分, 1. 分在两个监狱的关系, 2. 分在同一监狱的关系, 我们不能允许第一部分出现内部关系, 即如图:
2.png

二分图 $\Leftrightarrow$ mid在内部

Time Complexity

二分图: $O(log(1e9) * (n+m))$

$\rm binary\quad search\quad answer + staining\quad to\quad check$

Accepted Code

/*
如果mid等于0, 那么也就是说check(0)将所有边的两个端点分别放到两个监狱里, 判断是否为二分图, 是的话, r = 0 = l, puts("0");
*/

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 20010, M = 200010;

int n, m;
int h[N], e[M], w[M], ne[M], idx;
int color[N];

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

bool dfs(int u, int c, int mid)
{
    color[u] = c;
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (w[i] <= mid) continue; // 只判断大于mid的图是不是二分图
        if (color[j])
        {
            if (color[j] == c) return false;
        }
        else if (!dfs(j, 3 - c, mid)) return false;
    }

    return true;
}

bool check(int mid)
{
    memset(color, 0, sizeof color);
    for (int i = 1; i <= n; i ++ )
        if (!color[i])
            if (!dfs(i, 1, mid))
                return false;
    return true;
}

int main()
{
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h);

    while (m -- )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c), add(b, a, c);
    }

    int l = 0, r = 1e9;
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }

    printf("%d\n", r);

    return 0;
}

$\rm Union\quad Find$

Accepted Code




活动打卡代码 AcWing 1185. 单词游戏

Mrhh
14天前

Analysis

对于每个单词, 我们可以将其看作一个有向边. $\rm eg. acm \Leftrightarrow a \rightarrow m$
那么问题就转变为了判断有向图是否存在欧拉路径. 从一个点出发走遍所有的边.

Accepted Code

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 30;

int n;
int din[N], dout[N], p[N];
bool st[N];

int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main()
{
    char str[1010];

    int T;
    scanf("%d", &T);
    while (T -- )
    {
        scanf("%d", &n);
        memset(din, 0, sizeof din);
        memset(dout, 0, sizeof dout);
        memset(st, 0, sizeof st);
        for (int i = 0; i < 26; i ++ ) p[i] = i;

        for (int i = 0; i < n; i ++ )
        {
            scanf("%s", str);
            int len = strlen(str);
            int a = str[0] - 'a', b = str[len - 1] - 'a';
            st[a] = st[b] = true;
            dout[a] ++, din[b] ++ ;
            p[find(b)] = find(a);
        }

        // 出度 == 入度 起点终点特判
        int start = 0, end = 0;
        bool success = true;
        for (int i = 0; i < 26; i ++ )
            if (din[i] != dout[i])
            {
                if (din[i] == dout[i] + 1) end ++ ;
                else if (din[i] + 1 == dout[i]) start ++ ;
                else
                {
                    success = false;
                    break;
                }
            }

        if (success && !(!start && !end || start == 1 && end == 1)) success = false; // 1. 度数全为偶数(欧拉回路), 2. 起点终点只有一个(欧拉路径)

        // 边连通性
        int rep = -1;
        for (int i = 0; i < 26; i ++ )
            if (st[i])
            {
                if (rep == -1) rep = find(i);
                else if (rep != find(i))
                {
                    success = false;
                    break;
                }
            }

        if (success) puts("Ordering is possible.");
        else puts("The door cannot be opened.");
    }

    return 0;
}


活动打卡代码 AcWing 1124. 骑马修栅栏

Mrhh
14天前

Analysis

  • 我们如果把输出的路径看成是一个500进制的数,那么当存在多组解的情况下,输出500进制表示法中最小的一个
这句话的意思其实就是假如一条路径是这样的:
1 -> 2 -> 3 -> ... -> 500那么其对应的500进制数就是1234...(500), 
要这个数最小其实就是让路径编号序列满足字典序最小
对于以下的两个序列:
121 212
正逆序后者都大于前者, 所以说明序列的正逆序的大小没有关系, 正序大, 逆序小(❌)
  • 所有栅栏都是连通的(也就是你可以从任意一个栅栏到达另外的所有栅栏)。
所有边连通不一定所有点连通

Accepted Code

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 510;

int n = 500, m;
int g[N][N];
int ans[1100], cnt;
int d[N];

void dfs(int u)
{
    for (int i = 1; i <= n; i ++ ) // 按照点的编号升序来搜就能得到字典序最小的序列
        if (g[u][i]) // 编号越小越先搜
        {
            g[u][i] --, g[i][u] -- ;
            dfs(i);
        }
    ans[ ++ cnt] = u;
}

int main()
{
    cin >> m;
    while (m -- )
    {
        int a, b;
        cin >> a >> b;
        g[a][b] ++, g[b][a] ++ ;
        d[a] ++, d[b] ++ ;
    }

    int start = 1;
    for (int i = 1; i <= n; i ++ )
        if (d[i] % 2) // 无欧拉回路: (你可以从任意一个栅栏到达**另外**的所有栅栏)
        {
            start = i;
            break;
        }

    dfs(start);

    for (int i = cnt; i; i -- ) printf("%d\n", ans[i]); // ans: 1≤F≤1024

    return 0;
}


分享 欧拉路径

Mrhh
14天前

边连通
回路$∈$路径

无向图的欧拉路径

我们可以发现, 一个图对于起点和终点来说, 如果两个点不同, 我们走到了终点, 如果不是最后一条边的话, 我们就需要走出去, 最后一条边就不用出去了, 所以我们可以看出终点的度数一定为奇数, 起点同理, 如果起点终点相同的话, 即回路, 即度数为偶数., 对于其他点来说走过了, 就要走出来, 所以入度为偶数.

有向图的欧拉路径

同上思考方式.

结论

2.png

算法细节

例题 朴素模板求欧拉路径的最小字典序方案

例题 判断有向图是否存在欧拉路径



活动打卡代码 AcWing 1184. 欧拉回路

Mrhh
14天前
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010, M = 400010;

int type;
int n, m;
int h[N], e[M], ne[M], idx;
bool used[M];
int ans[M], cnt;
int din[N], dout[N];

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

void dfs(int u)
{
    /*
     * &i:改变i的值就相当于说是改变了h[u]的值, 实现删边(每条边只会被用到一次)
     * 同时i = h[u]实现向下搜索    
     */
    for (int &i = h[u]; ~i;)
    {
        // cout << i << endl;
        /*
        对于样例1,
        加了引用(保证了每条边只遍历一次)
        4
        5 // 反向边pass
        3
        2 // 反向边pass
        1
        0 // 反向边pass
        -1
        -1
        -1
        --------------------------------
        不加引用
        4
        5 // 反向边pass
        3
        2 // 反向边pass
        1
        4 **** 这条边实际上已经走过了但是这个地方还是要判断一遍, 就不是每条边都只遍历一次了, 时间复杂度自然也就不是线性的了
        0 // 反向边pass
        -1
        -1
        0
        0
        */

        if (used[i])
        {
            i = ne[i]; // i = h[u], 删边 1 -> 4/0, 遍历了4之后, h[1] = 0, 实现删边
            continue;
        }

        // cout << i << endl; // 反向边pass 点路径

        used[i] = true;
        if (type == 1) used[i ^ 1] = true; // 反向边也不能走了, 一条边只能走一遍

        int t;

        if (type == 1) // 无向边一条边占两个空, 编号是边数的两倍
        {
            t = i / 2 + 1;
            if (i & 1) t = -t;
        }
        else t = i + 1; // 有向边有多边就有多少编号

        int j = e[i];
        i = ne[i]; // 删边
        dfs(j);

        // cout << i << endl;

        ans[ ++ cnt] = t; // 回溯的时候在来加边
    }
}

int main()
{
    scanf("%d", &type);
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h);

    for (int i = 0; i < m; i ++ )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b);
        if (type == 1) add(b, a);
        din[b] ++ , dout[a] ++ ;
    }

    if (type == 1)
    {
        for (int i = 1; i <= n; i ++ )
            if (din[i] + dout[i] & 1)  // 无向图的度数: 我们只需要将该点的入度和出度加在一起就是无向图的度数
            {
                puts("NO"); // 欧拉回路-奇数pass
                return 0;
            }
    }
    else
    {
        for (int i = 1; i <= n; i ++ )
            if (din[i] != dout[i]) // 欧拉回路-入度不等于出度pass
            {
                puts("NO");
                return 0;
            }
    }

    for (int i = 1; i <= n; i ++ ) // 点可以有没有出边的点, 只需要所有边连通
        if (h[i] != -1)
        {
            // cout << i << endl;
            dfs(i); // 所有的边连通才有欧拉路径
            break;
        }

    if (cnt < m) // 有孤立边
    {
        puts("NO");
        return 0;
    }

    puts("YES");
    for (int i = cnt; i; i -- ) printf("%d ", ans[i]);

    return 0;
}