Pku3164 Command Network

时间限制:30s      空间限制:128MB

题目描述

    MST(最小生成树):对于无向带权图<V,E>,若其导出子图的边权和最小,且原图V中对应的任意两个顶点间有且仅有一条通路,则称此图为原图的MST。
    你的任务很简单,对于给定的有向带权图,求出其“最小生成树”,即指定一个根以后,每个点都是从根出发可达的。
 


输入格式

    输入文件最多包含3组测试数据,对于每组测试数据:
    第一行为两个数n,m,表示有向带权图的顶点数和边数,点编号为1~n。
    接下来n行,每行两个整数X_i,Y_i,表示i个顶点在直角坐标系中的坐标。
    接下来m行,每行两个正整数x,y,表示存在一条由点x指向点y的有向边,边权为两顶点的曼哈顿距离(定义见下)。
 


输出格式

对于每组测试数据,输出一行:
如果不存在“最小生成树”,输出“Poor”;
否则输出最小边权和。
 


样例输入

    3 3
    0 0
    1 0
    2 0
    1 2
    1 3
    2 3
    3 2
    0 0
    1 0
    2 0
    1 2
    3 2
 

样例输出

2
Poor
 

提示

    100%的数据,n≤1000,m≤n*n,0≤X_i,Y_i≤10000。
    可能存在自环。
 
【温馨提示】
对于两个点(a,b),(c,d),它们的曼哈顿距离定义如下:
l=|a-c|+|b-d|


题目来源

鸣谢 Hewr

Menuappsclose