UVA 10779 Collectors Problem(最大流)

题意：现在有包括了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所能拥有的物品个数，见下图。

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

代码：待补。