arc161f 题解

· · 题解

题目要求判定一张图是否有一个严格子图的密度大于等于 d，可以考虑先判定是否有大于的情况。

这是一个经典问题，列出式子 \dfrac e v>d，得到 e>vd，我们需要判定 e-vd 是否大于零。

这个式子可以看作每一条边有 1 的贡献，每一个点有 d 的代价，选了一条边必须要选连接的两个点，这是一个最大权闭合子图问题。图除了 S 和 T 共有两层，靠近 S 的是边，靠近 T 的是点。三类边为 (S,e,1),(e,v,\inf),(v,T,d)。

跑一次最大流看看是不是满流。如果不是那就直接输出 No，否则继续判断是否有严格非空子图的密度恰好为 d。

一个密度恰好等于 d 的联通子图对应到最小割模型中会形成一个子图，若联通子图大小为 x，则最小割模型子图将包含 x 个 v 和 dx 个 e，并且 e 连向的两个 v 都在子图内。这将构成一个强连通块，原因是找不到割边。一个非空的大小小于 n(d+1) 的强连通块将对应着一个密度恰好等于 d 的非空联通子图。

为了方便写代码，可以直接判定强连通块的个数，因为出度为 0 的强连通块一定能满足我们的要求。

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
const int N = 1e5 + 5, M = 1e6 + 5, inf = 1e9;
int T, n, d;
int s, t, etot, val[M];
int de[N], cur[N];
int dfsnum, dfn[N], low[N], top, sta[N], colnum, col[N];
vector<pair<int, int>> e1[N];
queue<int> q;
void addedge(int u, int v, int w){
    e1[u].emplace_back(v, ++etot);
    val[etot] = w;
    e1[v].emplace_back(u, ++etot);
    val[etot] = 0;
}
bool bfs(){
    for (int i = 1; i <= n * (d + 1) + 2; i++){
        de[i] = -1;
        cur[i] = 0;
    }
    q.push(s);
    de[s] = 0;
    while (!q.empty()){
        int u = q.front();
        q.pop();
        for (pair<int, int> p : e1[u]){
            int v = p.first, id = p.second;
            if (val[id] && de[v] == -1){
                de[v] = de[u] + 1;
                q.push(v);
            }
        }
    }
    return de[t] != -1;
}
int dfs(int u, int in){
    if (u == t) return in;
    int out = 0;
    for (int &i = cur[u]; i < (int)e1[u].size(); i++){
        int v = e1[u][i].first, id = e1[u][i].second;
        if (val[id] && de[v] == de[u] + 1){
            int res = dfs(v, min(val[id], in));
            in -= res;
            out += res;
            val[id] -= res;
            val[id & 1 ? id + 1 : id - 1] += res;
            if (!in) break;
        }
    }
    if (!out) de[u] = -1;
    return out;
}
void tarjan(int u){
    dfn[u] = low[u] = ++dfsnum;
    sta[++top] = u;
    for (pair<int, int> p : e1[u]){
        int v = p.first, id = p.second;
        if (!val[id]) continue;
        if (!dfn[v]){
            tarjan(v);
            low[u] = min(low[v], low[u]);
        }else if (!col[v]) low[u] = min(dfn[v], low[u]);
    }
    if (dfn[u] == low[u]){
        colnum++;
        do{
            col[sta[top]] = colnum;
        }while (sta[top--] != u);
    }
}
int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//  freopen("in.txt", "r", stdin);
//  freopen("out2.txt", "w", stdout);
    cin >> T;
    while (T--){
        etot = 0;
        cin >> n >> d;
        s = n * (d + 1) + 1, t = s + 1;
        for (int i = 1; i <= t; i++)
            e1[i].clear();
        for (int i = 1; i <= n * d; i++){
            int u, v;
            cin >> u >> v;
            addedge(s, i + n, 1);
            addedge(i + n, u, inf);
            addedge(i + n, v, inf);
        }
        for (int i = 1; i <= n; i++)
            addedge(i, t, d);
        int flow = 0;
        while (bfs())
            flow += dfs(s, inf);
        if (flow < n * d){
            cout << "No" << endl;
            continue;
        }
        dfsnum = colnum = top = 0;
        for (int i = 1; i <= n * (d + 1) + 2; i++)
            dfn[i] = col[i] = 0;
        tarjan(s);
        for (int i = 1; i <= n * (d + 1) + 2; i++)
            if (!dfn[i])
                tarjan(i);
        cout << (colnum - 2 == 1 ? "Yes" : "No") << endl;
    }
    return 0;
}

后记：所以为什么要把 F 放在 E 后面？