题解：AT_agc039_b [AGC039B] Graph Partition

wowwowwow · 2024-04-10 21:37:40 · 题解

之前算错复杂度了，感谢 @JuRuoOIer 巨佬的指正。

首先一开始显然用二分图染色判断可行性，如果能染色那么可以划分，其他题解已经说得很明白了（逃）。

那么接下来找最大划分方案。这里提供一种和其他题解不一样做法。

循环每个点作为起点 BFS，具体地说，将点的值记为点所属的集合，起点的值记为 1 ，然后与之相连的点记为 2 中...以此类推，每个点的值为其相邻已知点的 +1，然后找到所有方案（即将不同点作为起点）最大值。

那么为什么这样是对的呢？
我的理解是，这与直接用最短路算法本质类似，因为每条边长度都为 1, BFS 得到的点值就是到起点的最短距离。因为要遍历每条边，因此也是 O(n^3) 的。

代码：

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

const int N = 205;

int n, col[N], t[N], ans;

bool vis[N];

vector<int> g[N];
string str;
queue<int> q;

void color(int x, bool c){
    if(col[x] != -1){
        if(col[x] != c) ans = -1;
        return;
    } 
    if(ans == -1) return;
    col[x] = c;
    for(int v : g[x]){
        color(v, !c);
    } 
}

int BFS(int st){
    for(int i = 1; i <= n; i++) t[i] = 0, vis[i] = 0;
    q.push(st); t[st] = 1; vis[st] = 1;
    while(!q.empty()){
        int u = q.front(); q.pop();
        for(int v : g[u])
            if(!vis[v]){
                vis[v] = 1;
                t[v] = t[u] + 1;
                q.push(v);
            }
    }
    int maxn = 0;
    for(int i = 1; i <= n; i++){
        maxn = max(maxn, t[i]);
    } 
    return maxn;
}

signed main(){
    //二分图染色判断yes/no
    //以每个点为起点，bfs找最大值 
    scanf("%d", &n);
    for(int i = 1; i <= n; i++){
        cin >> str; str = '$' + str;
        for(int j = 1; j <= n; j++){
            if(str[j] == '1') g[i].push_back(j);
        }
    } 
    for(int i = 1; i <= n; i++) col[i] = -1;
    color(1, 0);
    if(ans == -1){
        printf("%d", -1);
        return 0; 
    }
    for(int i = 1; i <= n; i++){
        ans = max(ans, BFS(i) );
    }
    printf("%d", ans);
    return 0;
}