UVA 10779 Collectors Problem(最大流)

清疚 2022-01-12 15:23 503阅读 0赞

题意:现在有包括了Bob在内的N个小朋友,M种游戏卡片,Bob可以和其他人交换卡片,除了Bob,每个人的交换原则都是只给出自己拥有大于1的卡片,接受自己没有的卡片。的问他最后有多少不同的卡片。 N<=10; M<=25;

分析:用n-1个点表示除Bob之外的人,用m个点表示每个物品,再添加源点s和汇点t。从s向每个物品连边,容量为Bob拥有该物品的数量,表示Bob原始物品拥有情况。如果Bob以外的某个人i拥有至少两个物品j,就从i向物品j连边,容量为i所拥有的物品j的数量-1(i自己要留一个)表示i这个人把物品j转化成其他物品的上限;如果i没有物品j,从物品j向i连边,容量为1,表示i最多接收一个物品j,最后从每个物品向t连边,容量为1,显而易见,这张图的最大流就是Bob所能拥有的物品个数,见下图。

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RpYW53ZWkwODIy_size_16_color_FFFFFF_t_70

总结:交换问题也可以用网络流解决,这题把每个人当成中继点,流入流出表示交换关系。这道题把流变成了交换,是个不错的模型。

代码:待补。

发表评论

表情:
评论列表 (有 0 条评论,503人围观)

还没有评论,来说两句吧...

相关阅读

    相关 uva 11269——Setting Problems

    题意:一共有n个问题,每个问题都有相应的s和g段,必须先解决s,然后才能解决g,两个人解决问题,问怎么解决使得总耗时最小。 思路:贪心。按照A.s\+max(A.g

    相关 UVA 10779 Collectors Problem()

    题意:现在有包括了Bob在内的N个小朋友,M种游戏卡片,Bob可以和其他人交换卡片,除了Bob,每个人的交换原则都是只给出自己拥有大于1的卡片,接受自己没有的卡片。的问他最后

    相关 uva753()

    题意:有若干个电器设备需要不同的适配器才能接上电源,现在你要让尽可能多的电气设备接上电源。首先你手中有n个适配器和适配器的型号,再告诉你有m个电器和他们分别对应的适配器的型号

    相关 uva 11045()

    题意:(XXL, XL, L, M , S, or XS)每个尺码有若干件,需要分发给m个志愿者。告诉你每个志愿者有两个合适的尺码。问你是否每个志愿者都能找到合适的衣服? 思