正文 

当前位置： 首页 > IT > java教程

网络流24题-魔术球问题(代码片段)

q1143316492 q1143316492     2022-12-19     198

关键词：

网络流24题- 魔术球问题

魔术球问题链接

Description 
    假设有n根柱子，现要按下述规则在这n根柱子中依次放入编号为1，2，3，...的球。
    （1）每次只能在某根柱子的最上面放球。
    （2）在同一根柱子中，任何2个相邻球的编号之和为完全平方数。
    试设计一个算法，计算出在n根柱子上最多能放多少个球。例如，在4 根柱子上最多可
    放11 个球。
    编程任务：
    对于给定的n，计算在n根柱子上最多能放多少个球。
Input 
    4
Output 
    11
    1 8
    2 7 9
    3 6 10
    4 5 11
    
    
    
    
    
我们把x, y 满足(x < y && x + y是完全平方数)连一条边，我们要用尽量少的柱子放尽可能多的边。即用最少的路径覆盖尽可能多的点。问题就转化成了求有向图的最小路径覆盖。那么我们要求的就是如果1~n的数进行连边，求得的最小路径覆盖大于我们的柱子数。那么我们的答案就是对1~n-1的点求最小路径覆盖。并求出最小路径覆盖的路径
首先是一发及其暴力的枚举dinic，打个表，提前算出55个答案是在数字几的dinic的图中得出了，这个代码暴力TLE但是如果打出了表那么复杂度就是一次dinic的

#include <bits/stdc++.h>

using namespace std;

int k;

struct Dinic 

    static const int MAXN = 30005 + 7;
    static const int MAXM = 1e7 + 7;
    static const int INF = 0x3f3f3f3f;

    int n, m, s, t;

    int first[MAXN], cur[MAXN], dist[MAXN], sign;

    struct Node 
        int to, flow, next;
     edge[MAXM];

    inline void init(int start, int vertex, int ss, int tt) 
        n = vertex, s = ss, t = tt;
        for(int i = start; i <= n; i++ ) 
            first[i] = -1;
        
        sign = 0;
    

    inline void addEdge(int u, int v, int flow) 
        edge[sign].to = v, edge[sign].flow = flow, edge[sign].next = first[u];
        first[u] = sign++;
    

    inline void add_edge(int u, int v, int flow) 
        addEdge(u, v, flow);
        addEdge(v, u, 0);
    

    int match[MAXN] = 0, vis[MAXN] = 0;

    void show_graph() 
        for(int i = 1; i <= k; i++ ) 
            for(int j = first[i]; ~j; j = edge[j].next) 
                int to = edge[j].to, w = edge[j].flow;
                if(to != s && edge[j ^ 1].flow) 
                    //printf("%d ", to - k);
                    match[i] = to - k;
                
            
        
//        for(int i = 1; i <= k; i++ ) 
//            printf("[%d %d]
", i, match[i]);
//        
        for(int i = 1; i <= k; i++ ) 
            int now = i;
            if(vis[i]) 
                continue;
            
            while(1) 
                printf("%d", now);
                vis[now] = 1;
                now = match[now];
                if(now == 0) 
                    puts("");
                    break;
                 else 
                    printf(" ");
                
            
        
    

    inline int dinic() 
        int max_flow = 0;
        while(bfs(s, t)) 
            for(int i = 0; i <= n; i++ ) 
                cur[i] = first[i];
            
            max_flow += dfs(s, INF);
        
        return max_flow;
    

    bool bfs(int s, int t) 
        memset(dist, -1, sizeof(dist));
        queue<int>que;
        que.push(s), dist[s] = 0;
        while(!que.empty()) 
            int now = que.front();
            que.pop();
            if(now == t) 
                return 1;
            
            for(int i = first[now]; ~i; i = edge[i].next) 
                int to = edge[i].to, flow = edge[i].flow;
                if(dist[to] == -1 && flow > 0) 
                    dist[to] = dist[now] + 1;
                    que.push(to);
                
            
        
        return 0;
    

    int dfs(int now, int max_flow) 
        if(now == t) 
            return max_flow;
        
        int ans = 0, next_flow = 0;
        for(int &i = cur[now]; ~i; i = edge[i].next) 
            int to = edge[i].to, flow = edge[i].flow;
            if(dist[to] == dist[now] + 1 && flow > 0) 
                next_flow = dfs(to, min(max_flow - ans, flow));
                ans += next_flow;
                edge[i].flow -= next_flow;
                edge[i ^ 1].flow += next_flow;
                if(ans == max_flow) 
                    return max_flow;
                

            
        
        if(ans == 0) 
            return dist[now] = 0;
        
        return ans;
    

 cwl;

int main() 
    int n;
    scanf("%d", &n);
    for(k = 1; k; k++ ) 
        cwl.init(0, 2 * k + 1, 0, 2 * k + 1);
        for(int i = 1; i <= k; i++ ) 
            cwl.add_edge(0, i, 1);
            cwl.add_edge(i + k, 2 * k + 1, 1);
        
        for(int i = 1; i <= k; i++ ) 
            for(int j = i + 1; j <= k; j++ ) 
                int val = i + j;
                int sqr = sqrt(val);
                if(sqr * sqr == val) 
                    cwl.add_edge(i, j + k, 1);
                
            
        
        int ans = cwl.dinic();
        if(k - ans > n) 
            printf("%d
", k - 1);
            k--;
            cwl.init(0, 2 * k + 1, 0, 2 * k + 1);
            for(int i = 1; i <= k; i++ ) 
                cwl.add_edge(0, i, 1);
                cwl.add_edge(i + k, 2 * k + 1, 1);
            
            for(int i = 1; i <= k; i++ ) 
                for(int j = i + 1; j <= k; j++ ) 
                    int val = i + j;
                    int sqr = (int)sqrt(val);
                    if(sqr * sqr == val) 
                        cwl.add_edge(i, j + k, 1);
                    
                
            
            ans = cwl.dinic();
            cwl.show_graph();
            break;
        
    

    return 0;

然后是用打的表之间知道答案一次dinic求答案，24MS。
#include <bits/stdc++.h>

using namespace std;

int k;

int ans[] = 0, 1,3,7,11,17,23,31,39,49,59,71,83,97,111,127,143,161,179,199,219,241,263,287,311,337,363,391,419,449,479,511,543,577,611,647,683,721,759,799,839,881,923,967,1011,1057,1103,1151,1199,1249,1299,1351,1403,1457,1511,1567;

struct Dinic 

    static const int MAXN = 30005 + 7;
    static const int MAXM = 1e7 + 7;
    static const int INF = 0x3f3f3f3f;

    int n, m, s, t;

    int first[MAXN], cur[MAXN], dist[MAXN], sign;

    struct Node 
        int to, flow, next;
     edge[MAXM];

    inline void init(int start, int vertex, int ss, int tt) 
        n = vertex, s = ss, t = tt;
        for(int i = start; i <= n; i++ ) 
            first[i] = -1;
        
        sign = 0;
    

    inline void addEdge(int u, int v, int flow) 
        edge[sign].to = v, edge[sign].flow = flow, edge[sign].next = first[u];
        first[u] = sign++;
    

    inline void add_edge(int u, int v, int flow) 
        addEdge(u, v, flow);
        addEdge(v, u, 0);
    

    int match[MAXN] = 0, vis[MAXN] = 0;

    void show_graph() 
        for(int i = 1; i <= k; i++ ) 
            for(int j = first[i]; ~j; j = edge[j].next) 
                int to = edge[j].to, w = edge[j].flow;
                if(to != s && edge[j ^ 1].flow) 
                    //printf("%d ", to - k);
                    match[i] = to - k;
                
            
        
//        for(int i = 1; i <= k; i++ ) 
//            printf("[%d %d]
", i, match[i]);
//        
        for(int i = 1; i <= k; i++ ) 
            int now = i;
            if(vis[i]) 
                continue;
            
            while(1) 
                printf("%d", now);
                vis[now] = 1;
                now = match[now];
                if(now == 0) 
                    puts("");
                    break;
                 else 
                    printf(" ");
                
            
        
    

    inline int dinic() 
        int max_flow = 0;
        while(bfs(s, t)) 
            for(int i = 0; i <= n; i++ ) 
                cur[i] = first[i];
            
            max_flow += dfs(s, INF);
        
        return max_flow;
    

    bool bfs(int s, int t) 
        memset(dist, -1, sizeof(dist));
        queue<int>que;
        que.push(s), dist[s] = 0;
        while(!que.empty()) 
            int now = que.front();
            que.pop();
            if(now == t) 
                return 1;
            
            for(int i = first[now]; ~i; i = edge[i].next) 
                int to = edge[i].to, flow = edge[i].flow;
                if(dist[to] == -1 && flow > 0) 
                    dist[to] = dist[now] + 1;
                    que.push(to);
                
            
        
        return 0;
    

    int dfs(int now, int max_flow) 
        if(now == t) 
            return max_flow;
        
        int ans = 0, next_flow = 0;
        for(int &i = cur[now]; ~i; i = edge[i].next) 
            int to = edge[i].to, flow = edge[i].flow;
            if(dist[to] == dist[now] + 1 && flow > 0) 
                next_flow = dfs(to, min(max_flow - ans, flow));
                ans += next_flow;
                edge[i].flow -= next_flow;
                edge[i ^ 1].flow += next_flow;
                if(ans == max_flow) 
                    return max_flow;
                

            
        
        if(ans == 0) 
            return dist[now] = 0;
        
        return ans;
    

 cwl;

int get_value(int n) 
    printf("%d
", n);
    k = n;
    cwl.init(0, 2 * k + 1, 0, 2 * k + 1);
    for(int i = 1; i <= k; i++ ) 
        cwl.add_edge(0, i, 1);
        cwl.add_edge(i + k, 2 * k + 1, 1);
    
    for(int i = 1; i <= k; i++ ) 
        for(int j = i + 1; j <= k; j++ ) 
            int val = i + j;
            int sqr = sqrt(val);
            if(sqr * sqr == val) 
                cwl.add_edge(i, j + k, 1);
            
        
    
    int ans = cwl.dinic();
    cwl.show_graph();


int main() 
    int n;
    scanf("%d", &n);
    get_value(ans[n]);
    return 0;

[网络流24题]魔术球问题(代码片段)

...，所以不如直接顺序枚举答案，这样可以利用上次的残量网络，降低了复杂度。对于新枚举到的球，有两种选择：1.放到已经有球的柱子上2 查看详情

「网络流24题」魔术球问题(代码片段)

传送门：>Here<题意：有N根柱子，并且有连续编号的小球依次放入。要求后来的小球只能放在某根柱子最上面的小球上面，并且必须满足这两个小球的编号之和为完全平方数。求最多能放几个小球？思路分析真是好题~由于N的... 查看详情

洛谷2765：[网络流24题]魔术球问题——题解(代码片段)

https://www.luogu.org/problemnew/show/P2765#sub假设有n根柱子，现要按下述规则在这n根柱子中依次放入编号为1，2，3，...的球。（1）每次只能在某根柱子的最上面放球。（2）在同一根柱子中，任何2个相邻球的编号之和为完全平方数。试... 查看详情

p2765魔术球问题（网络流24题）(代码片段)

题目描述?问题描述：假设有n根柱子，现要按下述规则在这n根柱子中依次放入编号为1，2，3，...的球。（1）每次只能在某根柱子的最上面放球。（2）在同一根柱子中，任何2个相邻球的编号之和为完全平方数。试设计一个算法，... 查看详情

网络流24题魔术球问题（最大流）

【网络流24题】魔术球问题（最大流）题面Cogs题解是不是像极了最小路径覆盖？因此，我们枚举放到哪一个球（也可以二分）然后类似于最小路径覆盖的连边因为一根柱子对应一个路径的覆盖所以，提前预处理所有可行的连边（... 查看详情

网络流24题魔术球问题

P1226-【网络流24题】魔术球问题Description假设有n根柱子，现要按下述规则在这n根柱子中依次放入编号为1，2，3，4......的球。（1）每次只能在某根柱子的最上面放球。（2）在同一根柱子中，任何2个相邻球的编号之和为完全平方... 查看详情

[网络流24题]魔术球问题

问题描述： 假设有n根柱子，现要按下述规则在这n根柱子中依次放入编号为1，2，3，4......的球。 （1）每次只能在某根柱子的最上面放球。 （2）在同一根柱子中，任何2个相邻球的编号之和为完全平方数。 试设计... 查看详情

[网络流24题]魔术球问题

Description假设有$n$根柱子，现要按下述规则在这$n$根柱子中依次放入编号为$1,2,3,...$的球。$1.$每次只能在某根柱子的最上面放球。$2.$在同一根柱子中，任何$2$个相邻球的编号之和为完全平方数。求在$n$根柱子上最多能放多少个球... 查看详情

网络流24题魔术球问题

Description假设有n根柱子，现要按下述规则在这n根柱子中依次放入编号为1，2，3，4......的球。（1）每次只能在某根柱子的最上面放球。（2）在同一根柱子中，任何2个相邻球的编号之和为完全平方数。试设计一个算法，计算出在n... 查看详情

网络流24题魔术球问题（最小不相交路径覆盖）

【网络流24题】魔术球问题2014年3月7日3,5344Description假设有n根柱子，现要按下述规则在这n根柱子中依次放入编号为1，2，3，4的球。（1）每次只能在某根柱子的最上面放球。（2）在同一根柱子中，任何2个相邻球的编号之和为完... 查看详情

网络流24题----04软件补丁问题魔术球问题

问题描述： 假设有n根柱子，现要按下述规则在这n根柱子中依次放入编号为1，2，3，4......的球。 （1）每次只能在某根柱子的最上面放球。 （2）在同一根柱子中，任何2个相邻球的编号之和为完全平方数。 试设计... 查看详情

网络流24题——魔术球问题luogu2765

题目描述：这里这道题是网络流问题中第一个难点，也是一个很重要的问题如果直接建图感觉无从下手，因为如果不知道放几个球我就无法得知该如何建图（这是很显然的，比如我知道$1+48=49=7^2$，可是我都不知道是否能放到第48... 查看详情

网络流24题魔术球

LOJ6003【网络流24题】魔术球题面【题目描述】假设有n根柱子，现要按下述规则在这n根柱子中依次放入编号为1,2,3,4,?的球。每次只能在某根柱子的最上面放球。在同一根柱子中，任何2个相邻球的编号之和为完全平方数。试设计一... 查看详情

网络流24题(代码片段)

...问题模型转化模型1飞行员配对方案问题二分图最大匹配网络最大流 2太空飞行计划问题最大权闭合图网络最小割 3最小路径覆盖问题有向无环图最小路径覆盖网络最大流     4魔术球问题有向无环图最小... 查看详情

luogup2765魔术球问题网络流24最小路径问题(代码片段)

#include<iostream>#include<cstdio>#include<cstring>#include<cmath>#defineN500000usingnamespacestd;intn,m,S,T,tmp1,tmp2,tot;intidx,head[N],cur[N],q[N],ans1[N],ans2[N];inte[N],ne 查看详情

网络流24题（wll24）(代码片段)

Howtobuildamap?byCiaxin大体概括网络流和线性规划24题中23道的模型与建图思路，以下所有的题目的思路均会向图论方向靠近。目录目录Howtobuildamap?目录#飞行员配对方案问题#太空飞行计划问题#最小路径覆盖问题#魔术球问题#圆桌问题#... 查看详情

[loj#6003]「网络流24题」魔术球二分图最小路径覆盖，网络流

#6003.「网络流24题」魔术球内存限制：256MiB时间限制：1000ms标准输入输出题目类型：传统评测方式：SpecialJudge上传者：匿名提交提交记录统计讨论测试数据 题目描述假设有 nnn 根柱子，现要按下述规则在这 nnn ... 查看详情

「网络流24题」4.魔术球(代码片段)

等价于最小路径覆盖 #include<bits/stdc++.h>usingnamespacestd;constintINF=0x3f3f3f3f;constintmaxn=50004;intn,m,S,T,head[maxn],nxt[maxn],mark[maxn],dep[maxn],cnt=0,ans;structnodeintto,next,w;e[1000004];inlinevoidadd(intu,intv,intw)e[cnt].to=v;e[cnt].next=head[u];e[cnt].w=w;head[u]=c... 查看详情