关于二分图建边

gghack_Nythix @ 2025-01-10 16:14:39

by __zhanghuanrui__ @ 2025-01-10 16:27:23

@gghack_Nythix 这要看你的二分图是什么性质，如果是普通的二分图是双向边的

by zhouyuhang @ 2025-01-10 16:28:01

这完全取决于你的二分图有什么用。

如果你的题目需要显式建出二分图进行后续操作，那就要看题目中的要求。

如果你想要在二分图上做匹配，这取决于你所有使用的算法：

• 如果你使用匈牙利算法，至少我的实现是不用建双向边的。
• 如果你使用 Dinic 跑最大流，由于要退流，因此初始时必须要建反向边。

by gghack_Nythix @ 2025-01-10 16:57:23

@zhanghuanrui 能更详细的说明一下吗？

by gghack_Nythix @ 2025-01-10 16:58:01

@zhouyuhang 但是有些题目使用匈牙利算法还只能建单向边是什么情况。

by zhouyuhang @ 2025-01-10 17:01:56

@gghack_Nythix 不存在只能建单向边这种说法吧，只是匈牙利建单向边就够了。

by gghack_Nythix @ 2025-01-10 17:02:09

例如 P6062：

# include <bits/stdc++.h>
# define pb emplace_back
# define ins insert
using namespace std;
const int N = 60;
vector <int> g[N];
int n , m , cnt , bel[N][N][2] , vis[N] , match[N] , ans , cnt2;
char a[N][N];
bool pp (int now) {
    for (auto x : g[now]) {
        if (!vis[x]) {
            vis[x] = 1;
            if (!match[x] || pp (match[x]) ) {match[x] = now; return 1;}
        }
    }
    return 0;
}
signed main () {
    ios::sync_with_stdio(false) , cin.tie(0) , cout.tie(0);
    cin >> n >> m;
    for (int i = 1;i <= n;++i) for (int j = 1;j <= m;++j) cin >> a[i][j];
    for (int i = 1;i <= n;++i) {for (int j = 1;j <= m;++j) if (a[i][j] == '*') bel[i][j][0] = a[i][j - 1] == '*' ? bel[i][j - 1][0] : ++cnt ;} 
    for (int i = 1;i <= n;++i) {for (int j = 1;j <= m;++j) if (a[i][j] == '*') bel[i][j][1] = a[i - 1][j] == '*' ? bel[i - 1][j][1] : ++cnt2;}
    for (int i = 1;i <= n;++i) for (int j = 1;j <= m;++j) g[bel[i][j][0]].pb (bel[i][j][1]);
    for (int i = 1;i <= cnt;++i) memset (vis , 0 ,sizeof vis) , ans += pp (i);
    return cout << ans << "\n" , 0;
}

建双向边76pts。

# include <bits/stdc++.h>
# define pb emplace_back
# define ins insert
using namespace std;
const int N = 500;
vector <int> g[N + 1000];
int n , m , cnt , bel[N][N][2] , vis[N] , match[N] , ans , cnt2;
char a[N][N];
bool pp (int now) {
    for (auto x : g[now]) {
        if (!vis[x]) {
            vis[x] = 1;
            if (!match[x] || pp (match[x]) ) {match[x] = now; return 1;}
        }
    }
    return 0;
}
signed main () {
    ios::sync_with_stdio(false) , cin.tie(0) , cout.tie(0);
    cin >> n >> m;
    for (int i = 1;i <= n;++i) for (int j = 1;j <= m;++j) cin >> a[i][j];
    for (int i = 1;i <= n;++i) {for (int j = 1;j <= m;++j) if (a[i][j] == '*') bel[i][j][0] = a[i][j - 1] == '*' ? bel[i][j - 1][0] : ++cnt ;} 
    for (int i = 1;i <= n;++i) {for (int j = 1;j <= m;++j) if (a[i][j] == '*') bel[i][j][1] = a[i - 1][j] == '*' ? bel[i - 1][j][1] : ++cnt2;}
    for (int i = 1;i <= n;++i) for (int j = 1;j <= m;++j) if (a[i][j] == '*') g[bel[i][j][0]].pb (bel[i][j][1] + cnt) , g[bel[i][j][1] + cnt].pb (bel[i][j][0]);
    for (int i = 1;i <= cnt;++i) memset (vis , 0 ,sizeof vis) , ans += pp (i);
    return cout << ans << "\n" , 0;
}

建单向边+给节点分成两部分100pts。

by gghack_Nythix @ 2025-01-10 17:03:09

建的边说反了

by gghack_Nythix @ 2025-01-10 17:03:58

@zhouyuhang 就是说有时候某种建边的写法是没法过题的，我疑惑的是这一点。

by zhouyuhang @ 2025-01-10 17:05:34

我有点事，等会再看看，但是你这个很大概率是你自己哪写挂了，正确的匈牙利实现不会因为你多连边出现问题

by gghack_Nythix @ 2025-01-10 17:07:03

@zhouyuhang 好的。