Problem 2960. -- 跨平面 -- 衡阳八中OJ离线版-2014-11-04

F.A.Qs	Home	ProblemSet	Status	Ranklist	Contest	Login	Register	捐赠本站

Notice:开心刷题：）

2960: 跨平面

Time Limit: 1 Sec Memory Limit: 256 MB
Submit: 121 Solved: 47
[Submit][Status]

Description

Input

　第一行两个整数n和m，表示点与线段的数目。
　　接下来n行，每行两个整数x和y，表示第i个点的坐标，点从1到n编号。
　　接下来m行，每行四个整数p,q,V1和V2，表示存在一条从第p个点连向第q个点的线段，激活p->q这个方向的费用为V1，另一个方向费用为V2。
　　保证若两条线段相交，则交点是它们的公共端点。

Output

　　输出一行一个正整数，表示最小总激活费用。

Sample Input

4 5
0 0
1 0
0 1
1 1
1 2 0 0
1 3 0 3
2 3 1 0
2 4 2 0
4 3 0 0

Sample Output

HINT

　　对于100%的数据，n≤3000，区域数不超过1000，点坐标绝对值不超过1W，每条边激活费用不超过100。

Source

中国国家队清华集训 2012-2013 第二天鸣谢lydrainbowcat

[Submit][Status]
HOME Back