魔术球问题

给n个柱子,要依次放入1,2,3,……的球,要求每根柱子相邻的球的和为完全平方数,问最多能放几个球。
可以理解为 你最多可以有多少个球把他们分成n组。同样使用最小边覆盖=点数-最大匹配
先拆成二分图,在和为平方数的点之间加边,源点往x连,汇点往y连。不断加入新点,跑新的最大流(新的是多出来的,所以要用sum加起来),然后判断总数-maxflow>n时跳出。


#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
const ll MAXN = 20005;
const ll maxm = 200005;
struct Edge{
    ll from, to, cap, flow;
    Edge(){
    }
    Edge(ll from, ll to, ll cap, ll flow):from(from), to(to), cap(cap), flow(flow){}    
};
struct Edge1
{
    ll from, to; ll dist;       //起点,终点,距离
    Edge1(ll from, ll to, ll dist):from(from), to(to), dist(dist) {}
};
struct Dinic{
    ll n, m, s, t;
    vector<Edge>edges;
    vector<ll>G[MAXN];
    ll d[MAXN];
    ll cur[MAXN];
    ll vis[MAXN];
    void init(ll n, ll s, ll t)
    {
        this->n = n;this->s = s;this->t = t;
        edges.clear();
        for(ll i = 0;i <= n;++i) G[i].clear();
    }
    
    void add_edge(ll from, ll to, ll 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(vis, 0, sizeof(vis));
        queue<ll>Q;
        Q.push(s);
        d[s] = 0;
        vis[s] = true;
        while(!Q.empty())
        {
            ll x = Q.front();
            Q.pop();
            for(ll i = 0;i < G[x].size();++i)
            {
                Edge& e = edges[G[x][i]];
                if(!vis[e.to] && e.cap > e.flow)
                {
                    vis[e.to] = true;
                    d[e.to] = d[x] + 1;
                    Q.push(e.to);
                }
            }       
        }
        return vis[t];
    }
    ll dfs(ll x,ll a)
    {
        if(x == t || a == 0)return a;
        ll flow = 0, f;
        for(ll& i = cur[x];i < 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;
    }
    ll maxflow()
    {
        ll flow = 0;
        while(bfs())
        {
            memset(cur, 0, sizeof(cur));
            flow += dfs(s,inf);
        }
        return flow;
    }
}gao;//刘汝佳网络流dinic板子
int fa[10005];
int find(int x)
{
    if(fa[x]!=x){
        return fa[x]=find(fa[x]);
    }
    return x;
}
void uni(int x,int y)
{
    int x1=find(x);
    int y1=find(y);
    if(x1!=y1){
        fa[y1]=x1;
    }
}
int sqr[1005];
int main()
{
    int n,m;
    scanf("%d",&n);
    gao.init(20002,20001,20002);
    for(int i=1;i<=1000;i++){
        sqr[i]=i*i;
    }
    for(int i=1;i<=10000;i++){
        fa[i]=i;
    }
    int num=1;
    int sum=0;
    while(1){
        gao.add_edge(20001,num,1);
        gao.add_edge(num+10000,20002,1);
        int tmp=lower_bound(sqr+1,sqr+1001,num)-sqr;
        for(int i=2*tmp;i>=1;i--){
            int k=sqr[i]-num;
            if(k<num&&k>0)gao.add_edge(k,10000+num,1);
        }
        sum+=gao.maxflow();
        if(num-sum>n)break;
        num++;
    }
    num--;
    printf("%d\n",num);
    for(int i=0;i<gao.edges.size();i++){
        Edge k=gao.edges[i];
        if(k.from<=10000&&k.from>0&&k.to<=20000&&k.to>10000&&k.flow==1){
            uni(k.from,k.to-10000);
        }
    }
    for(int i=1;i<=num;i++){
        if(find(i)==i){
            for(int j=1;j<=num;j++){
                if(find(j)==i){
                    printf("%d ",j);
                }
            }
            printf("\n");
        }
    }
}

 

发表评论

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