posts - 64, comments - 4, trackbacks - 0, articles - 0

题意:电脑装机,要买 N 个配件,现有两家公司A 、B分别有这些配件,但价格不同,现在要求买完配件所用最少的价钱,同时若两配件来自不同的公司,考虑兼容性,可能要花而外的钱买转换器。

分析:最小割转换到最大流,n个配件,n个顶点,源点连向各顶点的边表示A公司的配件,边权表示A公司的该配件的价钱;各顶点连向汇点的边表示B公司的配件,边权表示B公司的该配件的价格。当两配件来自不同公司有兼容性问题时,对应的顶点连双向边,边权为转换器的价格。构图完成,很显然,此图的最小割便是所求,因而可用求最大流即可。

收获:因为此题数据顶点和边的数量都很大,朴素的最大流勉强能应付,但用dinic求最大流,那速度可是相当的快,几倍的差别,甚至是TLE 和 AC的差别。所以好好用好魅力无穷的Dinic吧~~~


cpp代码:


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理