luogu P2765 魔术球问题

题目中没有说球的上限是多少，只告诉了柱子，那么我们就应该以柱子为界去增加球，考虑将每两个能组成完全平方数的点连边，就形成了一个DAG(有向无环图)，由于是DAG，可以转换为最小覆盖问题，即最多有n条路径(柱子数)，求其能覆盖的最大点数，最小覆盖路径 = 节点数 - 最大匹配数，可以将其拆成二分图跑匈牙利/最大流，由Hall定理，|S| <= |T|，此处的|S|就等于节点数-最大匹配数，而|T|等于最小覆盖路径，就是柱子数n(n个路径必有n个节点)，在满足条件的情况下增加球的数量即可。

在求最小覆盖路径时，可以用匈牙利/dinic,首先都要先拆分成二分图，每个点拆成一个入点一个出点，用dinic时，就要再设一个源点一个汇点，进行多次增广路，每一次的flow就是其增加节点后增加的匹配数，而用匈牙利时可以不实际拆图，对每个节点都跑一次匈牙利即可。

#include<bits/stdc++.h>

using namespace std;

#define lowbit(x) ((x)&(-x))

typedef long long LL;

const int maxm = 1e5+;

const int INF = 0x3f3f3f3f;

struct edge{

    int u, v, nex;//, cap, flow, nex;

} edges[maxm];

int head[maxm], cur[maxm], cnt, level[maxm], pre[maxm];

bool vis[maxm];

void init() {

    memset(head, -, sizeof(head));memset(pre, -, sizeof(pre));

}

void addedge(int u, int v, int cap) {

    edges[cnt] = edge{u, v, head[u]};//cap, 0, head[u]};

    head[u] = cnt++;

}

bool dfs(int u) {

    for(int i = head[u]; i != -; i = edges[i].nex) {

        int v = edges[i].v;

        if(!vis[v]) {

            vis[v] = true;

            if(pre[v] == -|| dfs(pre[v])) {

                pre[v] = u;

                return true;

            }

        }

    }

    return false;

}

void run_case() {

    init();

    int n; cin >> n;

    int flow = , num = ;

    while(num - flow <= n) {

        num++;

        for(int i = sqrt(num)+; i*i<(num<<); ++i) {

            //和dinic一样 由新加的点向原点连，保证能更新答案，因为从新点跑匈牙利

            addedge(num, i*i-num,);

        }

        flow += dfs(num); memset(vis, , sizeof(vis));

    }

    cout << --num;

    for(int i = ; i <= num; ++i) {

        if(!vis[i]) {

            cout << "\n";

            for(int u = i; u!=-; u = pre[u]) {

                vis[u] = true;

                cout << u << " ";

            }

        }

    }

}

int main() {

    ios::sync_with_stdio(false), cin.tie();

    run_case();

    //cout.flush();

    return ;

}

匈牙利

#include<bits/stdc++.h>

using namespace std;

#define lowbit(x) ((x)&(-x))

typedef long long LL;

const int maxm = 1e5+;

const int INF = 0x3f3f3f3f;

struct edge{

    int u, v, cap, flow, nex;

} edges[maxm];

int head[maxm], cur[maxm], cnt, level[maxm], pre[maxm];

bool vis[maxm];

void init() {

    memset(head, -, sizeof(head));

}

void addedge(int u, int v, int cap) {

    edges[cnt] = edge{u, v, cap, , head[u]};

    head[u] = cnt++;

}

void bfs(int s) {

    memset(level, -, sizeof(level));

    queue<int> q;

    level[s] = ;

    q.push(s);

    while(!q.empty()) {

        int u = q.front();

        q.pop();

        for(int i = head[u]; i != -; i = edges[i].nex) {

            edge& now = edges[i];

            if(now.cap > now.flow && level[now.v] < ) {

                level[now.v] = level[u] + ;

                q.push(now.v);

            }

        }

    }

}

int dfs(int u, int t, int f) {

    if(u == t) return f;

    for(int& i = cur[u]; i != -; i = edges[i].nex) {

        edge& now = edges[i];

        if(now.cap > now.flow && level[u] < level[now.v]) {

            int d = dfs(now.v, t, min(f, now.cap - now.flow));

            if(d > ) {

                now.flow += d;

                edges[i^].flow -= d;

                pre[u>>] = now.v>>;

                return d;

            }

        }

    }

    return ;

}

int dinic(int s, int t) {

    int maxflow = ;

    for(;;) {

        bfs(s);

        if(level[t] < ) break;

        memcpy(cur, head, sizeof(head));

        int f;

        while((f = dfs(s, t, INF)) > )

            maxflow += f;

    }

    return maxflow;

}

void run_case() {

    init();

    int n; cin >> n;

    int s = , t = 1e5;

    int flow = , num = ;

    while(num - flow <= n) {

        num++;

        addedge(s, num<<, ), addedge(num<<, s, );

        addedge((num<<)|, t, ), addedge(t, (num<<)|, );

        for(int i = sqrt(num)+; i*i<(num<<); ++i) {

            //是将原有的球的入点向新加的球的出点连边，保证能增加流

            addedge((i*i-num)<<, (num<<)|, ), addedge((num<<)|, (i*i-num)<<, );

        }

        flow += dinic(s, t);

    }

    cout << --num;

    for(int i = ; i <= num; ++i) {

        if(!vis[i]) {

            cout << "\n";

            for(int u = i; u&&u!=t>>; u = pre[u]) {

                vis[u] = true;

                cout << u << " ";

            }

        }

    }

}

int main() {

    ios::sync_with_stdio(false), cin.tie();

    run_case();

    //cout.flush();

    return ;

}

Dinic

巴特西

luogu P2765 魔术球问题

最新文章

热门文章