洛谷P2765魔术球问题 最小路径覆盖

看到这一题第一眼想到：这不是二分最大流吗，后来发现还有一种更快的方法。

首先如果知道要放多少个球求最少的柱子，很显然是一道最小点路径覆盖的题，将一个点拆成u,v两个点，u和S相连，v和T相连，之后的有向边i,就用ui和vj相连即可。

但是这题首先不知道有多少个球，所以考虑依次加入点以及和这个点相关的边，然后在残余网络上跑新的最大流，如果可以跑出流量来意味着这个点成功在现有的柱子上按排上了，如果跑不出来说明按排不上，需要重新开一根柱子放这个点。

直到跑到答案k的时候，柱子数超过了n，要的答案就是k - 1，至于方案，只要在最后的残余网络图上面搜索一下每个点的前驱即可。

#include <map>

#include <set>

#include <ctime>

#include <cmath>

#include <queue>

#include <stack>

#include <vector>

#include <string>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <sstream>

#include <iostream>

#include <algorithm>

#include <functional>

using namespace std;

#define For(i, x, y) for(int i=x;i<=y;i++)

#define _For(i, x, y) for(int i=x;i>=y;i--)

#define Mem(f, x) memset(f,x,sizeof(f))

#define Sca(x) scanf("%d", &x)

#define Sca2(x,y) scanf("%d%d",&x,&y)

#define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)

#define Scl(x) scanf("%lld",&x);

#define Pri(x) printf("%d\n", x)

#define Prl(x) printf("%lld\n",x);

#define CLR(u) for(int i=0;i<=N;i++)u[i].clear();

#define LL long long

#define ULL unsigned long long

#define mp make_pair

#define PII pair<int,int>

#define PIL pair<int,long long>

#define PLL pair<long long,long long>

#define pb push_back

#define fi first

#define se second

typedef vector<int> VI;

int read(){int x = ,f = ;char c = getchar();while (c<'' || c>''){if (c == '-') f = -;c = getchar();}

while (c >= ''&&c <= ''){x = x *  + c - '';c = getchar();}return x*f;}

const double eps = 1e-;

const int maxn = ;

const int maxm = ;

const int INF = 0x3f3f3f3f;

const int mod = 1e9 + ;

int N,M,K;

int a[maxn];

struct Edge{

    int to,next,cap,flow;

    Edge(){}

    Edge(int to,int next,int cap,int flow):to(to),next(next),cap(cap),flow(flow){}

}edge[maxm * ];

int head[maxn * ],dis[maxn * ],pre[maxn * ],nxt[maxn * ],vis[maxn * ];

int n,s,tot,t;

void init(int N,int S,int T){

    n = N;s = S;t = T;

    for(int i =  ; i <= n ; i ++) head[i] = -;

    tot = ;

}

void add(int u,int v,int w){

    edge[tot] = Edge(v,head[u],w,);

    head[u] = tot++;

    edge[tot] = Edge(u,head[v],,);

    head[v] = tot++;

}

bool BFS(){

    for(int i =  ; i <= n; i ++) dis[i] = -;

    queue<int>Q;

    dis[s] = ; Q.push(s);

    while(!Q.empty()){

        int u = Q.front(); Q.pop();

        for(int i = head[u]; ~i ; i = edge[i].next){

            int v = edge[i].to;

            if(~dis[v] || edge[i].cap <= edge[i].flow) continue;

            dis[v] = dis[u] + ;

            Q.push(v);

        }

    }

    return ~dis[t];

}

int dfs(int u,int a){

    if(u == t || !a) return a;

    int flow = ;

    for(int &i = pre[u]; ~i ; i = edge[i].next){

        int v = edge[i].to;

        if(dis[u] +  != dis[v]) continue;

        int f = dfs(v,min(a,edge[i].cap - edge[i].flow));

        if(!f) continue;

        a -= f; flow += f;

        edge[i].flow += f;

        edge[i ^ ].flow -= f;

    }

    return flow;

}

int maxflow(){

    int flow = ;

    while(BFS()){

        for(int i =  ; i <= n ;  i ++) pre[i] = head[i];

        flow += dfs(s,INF);

    }

    return flow;

}

void search(int t){

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

        for(int j = head[i]; ~j ; j = edge[j].next){

            int v = edge[j].to;

            if(v == s) continue;

            if(edge[j].flow){

                nxt[i] = v - maxn;

                vis[v - maxn] = ;

            }

        }

    }

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

        if(!vis[i]){

            for(int j = i; j; j = nxt[j]){

                printf("%d ",j);

            }

            puts("");

        }

    }

}

int main(){

    Sca(N);

    for(int i = ; i <= ; i ++) a[i] = i * i;

    int S = ,T = ;

    init(,S,T);

    int num = ,k;

    int cnt = ;

    for(k = ;num <= N; k ++){

        while(k + k > a[cnt + ]) cnt++;

        add(S,k,);

        add(k + maxn,T,);

        for(int i = cnt ; i >= ; i --){

            if(a[i] - k <= ) break;

            add(a[i] - k,k + maxn,);

        }

        if(!maxflow()) num++;

    }

    k-=; num--;

    Pri(k);

    search(k);

    return ;

}