775 . 大地主小 Q
TopCoder
Tags
Description
身為大地主的小 Q，有 $n$（$1\le n\le 2000$）座座標為 $(x_i,y_i)$ 的農田（$1\le x_i,y_i\le 10^ 6$）。某天小 Q 心血來潮想為他廣大的農田設置一套水利系統。已知小 Q 可以建造取水站、水管等兩種設施：
- 取水站：在第 $i$ 座農田上設置取水站將會花費 $c_i$ 元（$1\le c_i\le 10^ 9$），可以供給該農田本身以及其他與該農田以水管相連的農田水源。
- 水管：已知水管只能為水平或鉛直的方向，因此建造由農田 $i$ 連至農田 $j$ 的水管會需要長度為 $| x_i-x_j| + |y_i-y_j|$ 單位長的水管，且每單位長的造價為 $k_i+k_j$（$1\le k_i,k_j\le 10^ 9$）
已知每個農田都要有水源，且兩條水管的路徑之間彼此可以交叉重疊，一條水管只能用於連接兩座農田。
由於大地主小 Q 實在是擁有太多農地了，因此小 Q 想請你幫他寫一支程式來求出最少要花多少錢設計此套水利系統，以及取水站與水管的位置。
若有多種可以花最少錢設計的水利系統，輸出任意一種系統配置即可。
Input Format
第一行輸入只有一個正整數 $n$（$1\le n\le 2000$），代表農田的數目。
在接下來的 $n$ 行中，每行有兩個以空白分開的數字 $x_i,y_i$（$1\le x_i,y_i \le 10^ 6$）代表第 $i$ 座農田的座標。
輸入的再下一行包含 $n$ 個以空白分開的正整數 $c_i$（$1\le c_i \le 10^ 9$）代表在第 $i$ 座農田建造取水站的花費。
最後一行包含 $n$ 個以空白分開的正整數 $k_i$（$1\le k_i \le 10^ 9$），用於計算在建造與第 $i$ 座農田相連的水管時的係數。
Output Format
輸出的第一行為一個正整數，代表建造此水利系統的最小花費。
下一行請輸出一個正整數 $v$，代表總共需建造 $v$ 個取水站。
再下一行請輸出 $v$ 個以空白分隔的整數，代表建造取水站的農田編號 $v_i$，可以以任意順序輸出。
下一行請輸出一個正整數 $e$，代表總共建造的水管數 $e$。
最後請輸出 $e$ 行以空格分開的數對 $a, b$（$1\le a,b \le n, a\ne b$）表示連接農地 $a,b$ 的水管，這些數對也可以用任意順序輸出。
若有多個可以達到最小花費的水利設施配置，則輸出任意一組解答即可。
Sample Input 1
4 5
1 1
1 4
3 6 3
4 5 6
Sample Output 1
3
1 3 2
0
Sample Input 2
2 1
1 2
3 3
23 2 23
3 2 3
Sample Output 2
1
2
2
2 1
2 3
Hints
Problem Source
Codeforces
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~1 | 範例測資 | 0 |
| 2 | 0~21 | 無額外限制 | 100 |