cogs_396_魔术球问题_(最小路径覆盖+二分图匹配,网络流24题#4)

描述

---

http://cojs.tk/cogs/problem/problem.php?pid=396

连续从1开始编号的球,按照顺寻一个个放在n个柱子上,(i)放在(j)上面的必要条件是(i+j)是一个完全平方数.问做多能放到几号球.

分析

---

cogs是简化版,我在网上找了个完整版的测试数据,要求输出方案...

求最大放几号球不方便,我们考虑枚举最大的球号,计算最少需要多少柱子.

我们对于满足(j<i)且(i+j)是一个完全平方数的(i,j),从(j)向(i)连一条边.那么我们要用几条路径,将全部点都连成几串.这个路径就相当于是柱子啦.所以这就是一个求最小路径覆盖的问题.

注意!!!是最小路径覆盖!不是最小边覆盖!!!

我们把每个点(i)拆成(i)和(i'),建立二分图,如果(i,j)满足条件,就从(j)向(i')连一条边.

对于一个路径覆盖中的一条路径,除了路径末端的那个点,也就是一个柱子最下面的那个球,其他点都有一个后继,在二分图中我们让这些点和它们的后继匹配.

这样的话,由于路径数=路径末端点的个数=点的总数-非末端点的个数=点的总数-二分图中的匹配数,所以我们做一下二分图匹配就可以了.

由于随着球号的增大,最少需要的柱子数量是单调不降的,所以可以二分.但是二分的话每次都要重新建图跑最大流,如果顺次枚举的话,每次只需要加一些边,然后在原来的残量网络中继续跑就OK了.

至于输出方案,最后跑一遍最大球号对应的最大流,然后在二分图的右侧找容量是1的边(从左边流过来1的流量,那么右边回去的容量就会+1),把每个球上面的球号记下来,然后输出的时候从1开始,只要当前这个球还没有输出,就从这个球开始向上一直输出.

注意:

1.虽然答案最大是1600,但是完全平方数可能不止这么大,例如:(1000+1500=2500=500^2).

#include <bits/stdc++.h>
using namespace std;

const int maxn=1600+5,opposite=1600,maxm=1000000+5,INF=0x3fffffff;
int n,cnt=1,s,t,max_flow,ans;
int head[maxn<<1],q[maxn<<1],lv[maxn<<1],itr[maxn<<1],match[maxn];
bool issquare[maxn<<1],vis[maxn];
struct edge{
    int to,cap,next;
    edge(){}
    edge(int to,int cap,int next):to(to),cap(cap),next(next){}
}g[maxm];
void add_edge(int u,int v,int cap){
    g[++cnt]=edge(v,cap,head[u]); head[u]=cnt;
    g[++cnt]=edge(u,0,head[v]); head[v]=cnt;
}
void bfs(){
    int front=0,tail=1;
    q[front]=s;
    memset(lv,-1,sizeof lv); lv[s]=0;
    while(front<tail){
        int u=q[front++];
        for(int i=head[u];i;i=g[i].next){
            int v=g[i].to;
            if(lv[v]<0&&g[i].cap>0){
                lv[v]=lv[u]+1;
                q[tail++]=v;
            }
        }
    }
}
int dfs(int u,int f){
    if(u==t) return f;
    for(int &i=itr[u];i;i=g[i].next){
        int v=g[i].to;
        if(g[i].cap>0&&lv[u]<lv[v]){
            int d=dfs(v,min(g[i].cap,f));
            if(d>0){
                g[i].cap-=d;
                g[i^1].cap+=d;
                return d;
            }
        }
    }
    return 0;
}
void Dinic(){
    int flow=0,f;
    for(bfs();lv[t]>0;bfs()){
        for(int i=s;i<=t;i++) itr[i]=head[i];
        while((f=dfs(s,INF))>0) flow+=f;
    }
    max_flow+=flow;
}
void solve(){
    max_flow=0;
    for(int i=1;;i++){
        ans=i-1;
        add_edge(s,i,1);
        add_edge(i+opposite,t,1);
        for(int j=1;j<i;j++)if(issquare[i+j]) add_edge(j,i+opposite,1);
        Dinic();
        if(i-max_flow>n) break;
    }
    memset(head,0,sizeof head); cnt=1; max_flow=0;
    for(int i=1;i<=ans;i++){
        add_edge(s,i,1);
        add_edge(i+opposite,t,1);
        for(int j=1;j<i;j++)if(issquare[i+j]) add_edge(j,i+opposite,1);
    }
    Dinic();
}
void print(){
    int p;
    printf("%d
",ans);
    for(int i=opposite+1;i<=ans+opposite;i++)for(int j=head[i];j;j=g[j].next)if(g[j].cap==1){
        match[g[j].to]=i-opposite;
        break;
    }
    for(int i=1;i<=ans;i++)if(!vis[i]){
        p=0;
        for(int j=i;j;j=match[j]){
            printf("%d ",j);
            vis[j]=true;
        }
        printf("
");
    }
}
void init(){
    scanf("%d",&n);
    s=0; t=3200+1;
    for(int i=1;i*i<=3200;i++) issquare[i*i]=true;
}
int main(){
    init();
    solve();
    print();
    return 0;
}

算法实现题 8-4 魔术球问题(习题 8-14)
«问题描述:
假设有 n 根柱子,现要按下述规则在这 n 根柱子中依次放入编号为 1,2,3,1⁄4的球。
(1)每次只能在某根柱子的最上面放球。
(2)在同一根柱子中,任何 2 个相邻球的编号之和为完全平方数。
试设计一个算法,计算出在 n 根柱子上最多能放多少个球。例如,在 4 根柱子上最多可
放 11 个球。
«编程任务:
对于给定的 n,计算在 n 根柱子上最多能放多少个球。
«数据输入:
由文件 input.txt 提供输入数据。文件第 1 行有 1 个正整数 n,表示柱子数。
«结果输出:
程序运行结束时,将 n 根柱子上最多能放的球数以及相应的放置方案输出到文件
output.txt 中。文件的第一行是球数。接下来的 n 行,每行是一根柱子上的球的编号。
输入文件示例
input.txt
4
输出文件示例
output.txt
11
1 8
2 7 9
3 6 10
4 5 11