题目
中文题目,不解释:
分析
这道题BZOJ上也只有几个人过…奇怪了
下面是正解
- 原问题为一个二分图边染色问题。首先考虑最好情况。最理想情况的分配为:设一个点的度为。那么若为的倍数,那么与相连的边恰好平均分配给个公司,每个公司个;如果不是的倍数,那么要尽量分的均匀,即。分出来应该为。可以证明上述分配方案一定能达到。证明过程就是归纳构造的过程。我们先构造出号公司所选边,然后转化成个公司的子问题。根据假设,可以确定每个点属于公司的边数只有一种或两种可能。于是建图,原来的边保留,容量为。原点到国每个点连以需要分配给号公司的边数为容量的边。如果该点度数不能被整除,那么多连一条容量为的边。求最大流。可以证明任意一个最大流一定能对应到公司的分配方案。然后删去满流边,递归成个公司的问题。
- 题解和标程出处 传送门
…已经证明分配方案一定可以达到,那么这就是一道结论题了…下面是我的代码
#include
templateinline void read(T &num) {
char ch; while((ch=getchar())'9');
for(num=0;ch>='0'&&ch
服务器托管,北京服务器托管,服务器租用 http://www.fwqtg.net
机房租用,北京机房租用,IDC机房托管, http://www.e1idc.net