OI题库

【题目描述】

Alice和Bob正在玩如下的游戏。首先Alice画一个有N个顶点，M条边的有向图。然后Bob试着摧毁它。在一次操作中他可以找到图中的一个点，并且删除它所有的入边或所有的出边。

Alice给每个点定义了两个值：Wi+和Wi-。如果Bob删除了第i个点所有的入边他要给Alice付Wi+元，如果他删除了所有的出边就需要给Alice付Wi元。

找到Bob删除图中所有边需要的最小花费。

【输入格式】

输入数据描述了Alice画下的图。

输入文件的第一行有两个数N,M(1<=N<=100,1<=M<=5000)。第二行有N个整数，描述了N个点的Wi+，同样的第三行是这N个点的Wi-。所有的费用都是正数并且不超过10^6。接下来的M行每行有两个数，代表有向图中相应的一条边。

【输出格式】

输出一行一个整数，即Bob的最小花费。

【样例输入】

3 6

1 2 3

4 2 1

1 2

1 1

3 2

1 2

3 1

2 3

【样例输出】

5

【提示】

样例的一个方案是：删除点1，2所有的入边，删除点2所有的出边。

输出格式和原题有所不同。原题要求输出方案。

【来源】

Northeastern Europe 2003,Northern Subregion (NEERC 2003)

POJ 2125 Destroying the Graph