[NEERC 2003][POJ2125]有向图破坏

Grade Open Time Friday, 19 September 2014, 10:08 am
Discount 0.8 Time Discount Friday, 26 September 2014, 10:08 am
Allow late Yes Close Time Friday, 26 September 2014, 10:08 am
Input file destroyingthegraph.in Output file destroyingthegraph.out

【题目描述】

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