AGC039B 题解

因为一条边只能在 \(V_i,V_i+1\) 之间，如果把 \(V_1,V_3,\cdots\) 看作一部分，\(V_2,V_4,\cdots\) 看作一部分，这就是个二分图。

考虑一个二分图怎么“展开”成最多的集合。

考虑答案上界。上界是点对最短路的最大值加一。

如果集合个数超过上界，那么一定存在一条边跨越多个集合。

猜测对于所有情况，上界都可以被构造。

我们发现这是简单的，因为只要沿着最短路构造就行了，设最大值为 \(dis(x,y)\)，那么只要令 \(V_i=\{u|dis(x,u)=i-1\}\) 即可。

证明：因为最短路的性质，不存在边 \((u,v)\) 使得 \(|d_u-d_v|>1\)。然后考虑有没有在同集合内的边：因为如果边在集合内，那么沿着最短路树向上找，一定出现奇环，和二分图的性质矛盾。

所以答案即为上界。

于是判定二分图后 \(O(n^3)\) Floyd 或者 \(O(nm)\) bfs 求最短路即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 205;
vector<int> e[N];
int col[N], g[N][N]; bool vis[N];
int n;
bool ok = 1;

void dfs(int x, int fa)
{
    for(int i : e[x])
    {
        if(i == fa) continue;
        if(vis[i])
        {
            if(col[i] != col[x] ^ 1)
                ok = 0;
            continue;
        }
        else
        {
            vis[i] = 1, col[i] = col[x] ^ 1;
            dfs(i, x);
        }
    }
}

int d[N][N];

signed main()
{
    ios::sync_with_stdio(0);cin.tie(0);
    cin >> n;
    memset(d, 0x3f, sizeof d);
    for(int i = 1; i <= n; i ++)
    {
        string s; cin >> s;
        for(int j = 0; j < n; j ++)
            if(s[j] == '1')
                e[i].push_back(j + 1), g[i][j + 1] = 1, d[i][j + 1] = 1;
    }
    for(int i = 1; i <= n; i ++) d[i][i] = 0;
    for(int i = 1; i <= n; i ++)
        if(!vis[i]) vis[i] = 1, dfs(i, 0);
    if(!ok) return cout << -1, 0;
    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]);
    int ans = 0;
    for(int i = 1; i <= n; i ++)
    for(int j = 1; j <= n; j ++)
        ans = max(ans, d[i][j]);
    cout << ans + 1;

    return 0;
}

当然，判二分图也可以扩展域并查集或者带权并查集。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 205;
vector<int> e[N];
int n;

int fa[N << 1];
int find(int x) {return x == fa[x] ? x : fa[x] = find(fa[x]);}
void merge(int x, int y) {fa[find(x)] = find(y);}
int d[N][N];

signed main()
{
    ios::sync_with_stdio(0);cin.tie(0);
    cin >> n;
    for(int i = 1; i <= n * 2; i ++) fa[i] = i;
    memset(d, 0x3f, sizeof d);
    for(int i = 1; i <= n; i ++)
    {
        d[i][i] = 0;
        string s; cin >> s;
        for(int j = 0; j < n; j ++)
            if(s[j] == '1')
            {
                e[i].push_back(j + 1);
                d[i][j + 1] = 1;
                merge(i, j + 1 + n);
                merge(i + n, j + 1);
            }
    }
    for(int i = 1; i <= n; i ++)
        if(find(i) == find(i + n)) return cout << -1, 0;
    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]);
    int ans = 0;
    for(int i = 1; i <= n; i ++)
    for(int j = 1; j <= n; j ++)
        ans = max(ans, d[i][j]);
    cout << ans + 1;

    return 0;
}

甚至，不需要判二分图，最后枚举每条边，不满足题目要求说明不是二分图。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 205;
vector<int> e[N];
int n;

int d[N][N], g[N][N];

signed main()
{
    ios::sync_with_stdio(0);cin.tie(0);
    cin >> n;
    memset(d, 0x3f, sizeof d);
    for(int i = 1; i <= n; i ++)
    {
        d[i][i] = 0;
        string s; cin >> s;
        for(int j = 0; j < n; j ++)
            if(s[j] == '1')
            {
                e[i].push_back(j + 1);
                d[i][j + 1] = 1;
                g[i][j + 1] = 1;
            }
    }
    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]);
    for(int i = 1; i <= n; i ++)
    for(int j = 1; j <= n; j ++)
    for(int k = 1; k <= n; k ++)
        if(g[j][k] && d[i][j] == d[i][k])
            return cout << -1, 0;
    int ans = 0;
    for(int i = 1; i <= n; i ++)
    for(int j = 1; j <= n; j ++)
        ans = max(ans, d[i][j]);
    cout << ans + 1;

    return 0;
}