本文共 2797 字，大约阅读时间需要 9 分钟。

题目链接

题意

n个店铺，从m个市场进货，k种货物。给定市场k种货物存量，店铺k种货物需求，运输花费，问是否能满足要求，最小花费是多少

思路

费用流没得跑，就看如何建图

我一开始是一次性建图，出现以下几个问题

• 点编号太难了，一一对应很费脑子
• 边太多了，MCMF超时

看别的博客知道了要拆成k张图，对k种货物一一处理。因为我们需要满足所有需求，也就是必须满流，所以可以独立得拆成k张图，拆了之后发现建图简单了一个量级，按部就班建图就可以了

数据

来源POJ讨论区，感谢前辈们提供数据

input

1 3 3

1 1 1

0 1 1

1 2 2

1 0 1

1 2 3

1 1 1

2 1 1

1 1 1

3

2

20

2 4 3

0 2 3

2 3 4

1 0 2

1 0 3

0 2 4

2 3 0

2 3 1 2

1 2 3 1

1 1 2 3

2 1 3 1

2 2 3 1

2 3 4 1

2 2 1

1 1 1 1

1 2 2 100

2 4 5

2 1 2 2 2

1 1 1 2 1

2 2 2 2 2

2 1 2 1 1

2 2 2 2 1

1 2 2 2 1

1 1 6 7

5 5 2 9

4 6 6 9

9 1 9 1

7 4 1 7

4 4 7 3

5 4 7 7

9 1 3 8

8 8 2 7

1 4 7 1

1 2 3

1 1 2

2 2 1

2 1 1

7 4

4 1

7 3

0 0 0

output:

4

-1

27

4

38

15

代码

#include
   
    #include
    
     #include
     
      #include