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

摘要:
链接:P2765门户解决方案:首先,将模型转换为:依次将数字1转换为$k$。如果数字$v$可以放在$u$之后,则可以通过连接边$(u,v)$来计算具有最小路径覆盖的最大$k$。显而易见的一点是,$k$显然与$n$正相关,因此我们可以划分/枚举$k$的值以进行求解,并判断每次是否满足要求。但对于这个问题,枚举显然比二分法更有效,每次添加一个新点来查询是否有一条扩增道路。如果有扩大道路,

Link:

P2765 传送门

Solution:

首先将模型转化为:依次放数1到$k$,如果数$v$能放在$u$后,则连边$(u,v)$

求在最少路径覆盖数不大于$n$时的最大的$k$

显而易见的一点是$k$明显是和$n$正相关的

这样我们就可以 二分/枚举 $k$的值来进行求解,每次判断是否符合要求

但对于此题而言,枚举明显比二分效率更高,每次新加入一个点查询是否有增广路即可

如果有增广路则代表可以接在之前的点后,那么能接就尽量接,否则新开一条路径

这样做的证明:如果$v$能接在$u$之后却不接不会使答案变好,因为$nxt[u]$和$nxt[v]$可以交换位置

这样跑下来发现和贪心的结果完全相同:每次能接时随便接在一个数后即可

说明下述情况不会出现:$(a,c)(b,c)(a,d)$,同时选择将$c$接在$a$后,并不会证明

Code:

#include <bits/stdc++.h>

using namespace std;
const int MAXN=2e4+10;
struct edge{int nxt,to;}e[MAXN<<2];
int n,cur,res,vis[MAXN],mat[MAXN],head[MAXN],st[MAXN],nxt[MAXN],tot;

void add_edge(int from,int to)
{
    e[++tot]={head[from],to};head[from]=tot;
    e[++tot]={head[to],from};head[to]=tot;
}

int dfs(int x)
{
    for(int i=head[x];i;i=e[i].nxt)
        if(!vis[e[i].to])
        {
            vis[e[i].to]=1;
            if(!mat[e[i].to]||dfs(mat[e[i].to]))
            {mat[e[i].to]=x;nxt[e[i].to>>1]=x>>1;return true;}
        }
    return false;
}

int main()
{
    scanf("%d",&n);
    while(cur<=n)
    {
        res++;
        for(int i=sqrt(res)+1;i*i<2*res;i++)
            add_edge((i*i-res)<<1,res<<1|1);
        memset(vis,0,sizeof(vis));
        if(!dfs(res<<1|1)) st[++cur]=res;
    }
    printf("%d
",res-1);
    for(int i=1;i<=n;i++)
    {
        for(int j=st[i];j;j=nxt[j])
            printf("%d ",j);
        puts("");
    }
    return 0;
}

免责声明:文章转载自《[网络流24题] 魔术球问题》仅用于学习参考。如对内容有疑问,请及时联系本站处理。

上篇[ARC 066] Tutorial[网络流24题] 试题库问题下篇

宿迁高防,2C2G15M,22元/月;香港BGP,2C5G5M,25元/月 雨云优惠码:MjYwNzM=

随便看看

移动三国己然鼎立,普​通开发者如何选择开发​平台? 狼人:

Nokia和Microsoft 终于搞基成功,业内人事普遍都看好两家厂商的“软硬结合”。这一结局直接把Windows Phone 7 这一新兴手机移动操作系统送到与如日中天的 iPhone 与 Android 在同一位置上,变成了三国之势。究竟两家公司的合作是 " No - Win " 还是 "Win - Kia " 这里不做讨论,只能引用我们瓷器国的某些专...

Linux环境(五)--主机信息与日志

主机信息正如我们可以确定用户信息一样,程序也可以确定其运行的计算机的信息。uname命令提供了这些信息。uname同时也作为一个系统调用来在一个C程序中提供同样的信息,我们可以使用man 2 uname来查看详细的信息。许 多情况都需要主机信息。我们也许希望依据在网络中一个程序所运行的机器的名字来自定义其行为,也就是说,是一个学生的机器还是一个管理员的机器。...

Linux下游戏大作赏析(一)

本文原出自著名博客站点WHDb.com,此译文由jlinux.cn的tunpishuang完成。一、Spring比起2007,你更期待2008的排行吗?那看看Spring (也称TA Spring或者横扫千军:Spring)。TA Spring可以毫无障碍的玩横扫千军中所有的场景。可以支持5000个一样的单位同时作战,只受你电脑能力的限制。你可以在3D高清晰...

c++虛表以及data member的布局 真实的活 博客园

c++虛表以及data member的布局 - 真实的活 - 博客园 c++虛表以及data member的布局 前段時間在看Inside c++ object model的时候,写测试程序看看有虚函数的类的对象在内存中是怎样布局的,发现在g++实现的时候,每个如此的对象都会有一个vtPtr,即虚表指针,而且是存在于对象的开始地址,然后才是其它数据成员,...

Linux下socket实现网页抓取 Unicorn 博客频道 CSDN.NET

Linux下socket实现网页抓取 - Unicorn - 博客频道 - CSDN.NET Linux下socket实现网页抓取 分类:C/C++学习点滴DO spiders DOlinux编程2007-10-06 21:33951人阅读评论(0)收藏举报 主要用来和WinSock进行下比较: --WinSock--需要初始化:if( (Ret =...

undefined reference to

关于“undefined reference to”错误这两天在Linux下用Eclipse编数据结构,还有试用CPPUNIT,总是遇到一个错误,就是“undefined reference to [function name]”。找了很久,终于发现是在写makefile的疏忽所致。出错的时候是这样的:1 main:main.o Array.o2 g++ m...