loj 6003「网络流 24 题」魔术球

题目链接:https://loj.ac/problem/6003

题意:略。

思路:Seng Xian的题解

转换思路,不好求有 n 个柱子时可放的球数量,我们求可放 n 个球时的最小柱子数量,注意到同一个柱子上球的标号递增,所以可以转化为最小路径覆盖问题。
枚举答案 T,在图中建立节点1,2,...,T。如果对于i<ji+j 为一个完全平方数,连接一条有向边 (i,j)。该图是有向无环图,求最小路径覆盖。如果刚好满足最小路径覆盖数等于 n,那么 T 是一个可行解,在所有可行解中找到最大的 T,即为最优解。可以顺序枚举 T 的值,当最小路径覆盖数刚好大于 n 时终止,T−1就是最优解。
最小路径覆盖数随球的数量递增不递减,满足单调性,所以可以顺序枚举答案(或二分答案),对于特定的答案求出最小路径覆盖数,一个可行解就是最小路径覆盖数等于 n 的答案,求出最大的可行解就是最优解。本问题更适合枚举答案而不是二分答案,因为如果顺序枚举答案,每次只需要在残量网络上增加新的节点和边,再增广一次即可。如果二分答案,就需要每次重新建图,大大增加了时间复杂度。

总结:有些时候要转换思路,寻求问题容易求解的形式,转化为判定性问题,而判定问题有时更适合枚举答案,在原图上加点。

#include <bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=1e5+10;
template<typename T>
inline T read(T&x){
    x=0;int _f=0;char ch=getchar();
    while(ch<'0'||ch>'9')_f|=(ch=='-'),ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x=_f?-x:x;
}
struct Edge{
    int from,to,cap,flow;
    Edge(int u,int v,int c,int f):from(u),to(v),cap(c),flow(f){}
};
struct Dinic{
    int n,m,s,t;
    vector<Edge>edges;
    vector<int>G[maxn];
    bool vis[maxn];
    int d[maxn];
    int cur[maxn];

    void init(int n){
        this->n=n;
        for (int i=0;i<n;i++) G[i].clear();
        edges.clear();
    }

    void AddEdge(int from,int to,int cap){
        edges.push_back(Edge(from,to,cap,0));
        edges.push_back(Edge(to,from,0,0));
        m=edges.size();
        G[from].push_back(m-2);
        G[to].push_back(m-1);
    }

    bool BFS(){
        memset(d,0,sizeof(d));
        memset(vis,0,sizeof(vis));
        queue<int>Q;
        Q.push(s);
        d[s]=0;
        vis[s]=1;
        while (!Q.empty()){
            int x=Q.front();Q.pop();
            for (int i=0;i<(int)G[x].size();i++){
                Edge& e=edges[G[x][i]];
                if (!vis[e.to] && e.cap>e.flow){
                    vis[e.to]=1;
                    d[e.to]=d[x]+1;
                    Q.push(e.to);
                }
            }
        }
        return vis[t];
    }

    int DFS(int x,int a){
        if (x==t || a==0) return a;
        int flow=0,f;
        for (int& i=cur[x];i<(int)G[x].size();i++){
            Edge& e=edges[G[x][i]];
            if (d[x]+1==d[e.to] && (f=DFS(e.to,min(a,e.cap-e.flow)))>0){
                e.flow+=f;
                edges[G[x][i]^1].flow-=f;
                flow+=f;
                a-=f;
                if (a==0) break;
            }
        }
        return flow;
    }

    int Maxflow(int s,int t){
        this->s=s;this->t=t;
        int flow=0;
        while (BFS()){
            memset(cur,0,sizeof(cur));
            flow+=DFS(s,INF);
        }
        return flow;
    }

    void print(int x){
        vis[x]=true;
        for (int i=0;i<(int)G[x].size();i++) {
            Edge& e=edges[G[x][i]];
            if (!vis[e.to] && e.to!=t && e.flow==1) {
                printf(" %d",e.to-5000);
                print(e.to-5000);
            }
        }
    }
    void printpath(int num){
        memset(vis,false,sizeof(vis));
        for (int i=1;i<=num;i++) {
            if (!vis[i]){
                printf("%d", i);
                print(i);
                printf("\n");
            }
        }
    }
}A;
int n;
int main(){
    read(n);
    A.init(10001);
    int s=0,ans=0,t=10000;
    for (;;){
        ans++,s++;
        for (int i=1;i<s;i++){
            if ((int)sqrt(i+s)==sqrt(i+s)) A.AddEdge(i,5000+s,1);
        }
        A.AddEdge(0,s,1);
        A.AddEdge(s+5000,t,1);
        int f=A.Maxflow(0,t);
        ans-=f;
        if (ans>n) break;
    }
    printf("%d\n",s-1);
    A.printpath(s-1);
    return 0;
}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注