首页 > [ZJOI2009]狼和羊的故事
开通博客写题解
头像 昊子为汁
发表于 2024-10-05 15:48:58
该问题是一个最小割问题：如何放最少的篱笆使得羊狼领域分开。 建图：我们将相邻的土地都连上权值为1的无向边。再将额外增加一个源点和一个汇点，将所有狼的领地和源点相连、羊的领地和汇点相连，边权为一个大数即可。 建完图后跑一遍dinic就可以了。 注意：加边加的是无向边不要重复加边。 #include & 展开全文
去ta的博客 赞 (2) 回复(0) 收起
查看本题
查看本题讨论

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”