39 . 又是城市規劃
TopCoder
Tags
Description
競技程式的世界裡有很多城市需要規劃，有的城市要規劃成一些方格，有的城市要是一張正則平面圖，做過無數道城市規劃題目的你，覺得競程選手根本是城市規劃師。
正如題目名稱所說，你又要規劃一個城市了！王董最近買了一片新的土地，要在上面建造一個城市，幸運的是，他早就把城市設計好了：這座城市有 $N$ 個區域和 $M$ 條道路，每條道路都雙向連接兩座城市，王董需要做的就只是先請道路建設公司來把道路都蓋好，之後人們就會自己搬入各個區域。
道路建設公司提供限時優惠方案，如果請他們在第 $s_i$ 天到第 $t_i$ 天之間（包含 $s_i,t_i$）建造第 $i$ 條道路，那麼費用全免，否則建造一條道路要花 1 塊錢。一條道路需要花費一整天的時間建造，且同一天只能建造一條道路。
雖然王董其實有錢在沒有優惠的情況下請道路建設公司建造所有道路，但錢畢竟還是能省則省，才能做更多好玩的事情，因此，他想知道至少要花多少錢建造道路，才能使得整座城市的 $N$ 個區域連通，也就是從任一個區域都能直接或間接地透過有建造的道路，到達其他任何一個城市。與此同時，他還想知道在最小化花費的錢的情況下，要使用優惠方案建造的道路有哪些。
Input Format
第一行有兩個整數 $N$、$M$，代表王董規劃的區域和道路數量。
接下來有 $M$ 行，其中第 $i$ 行有四個整數 $u_i,v_i,s_i,t_i$，代表第 $i$ 條道路連接第 $u_i$ 及第 $v_i$ 個區域，且在第 $s_i$ 天到第 $t_i$ 天之間建造的話免費。
- $2 \leq N \leq 400$
- $N - 1 \leq M \leq 1000$
- $1 \leq u_i,v_i \leq N$
- $u_i \neq v_i$
- $1 \leq s_i \leq t_i \leq 10^ 9$
- 如果建造了所有道路，整座城市一定連通
Output Format
第一行輸出一個整數 $x$，代表王董至少需要花多少錢建造道路，才能讓整座城市連通。
第二行輸出一個長度為 $M$ 的 01 字串，其中第 $i$ 個字元是 1 代表第 $i$ 條道路要用優惠方案建造，是 0 則代表不用。
Sample Input 1
1 2 1 1
2 3 2 2
3 4 3 3
1 3 1 1
2 4 3 3
1 4 4 4
4 5 2 2
Sample Output 1
1010011
Sample Input 2
5 2 1 2
1 4 1 1
1 5 3 3
3 4 1 2
3 1 1 2
5 3 2 3
4 2 2 2
2 1 1 2
2 3 2 2
5 2 1 2
Sample Output 2
1110000000
Hints
Problem Source
IOICamp 2024 Day4 pF
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~1 | 範例測資 | 0 |
| 2 | 2~8 | $\forall 1 \leq i \leq M,\ s_i=t_i=i$ | 1 |
| 3 | 9~27 | $M=N-1$，$\forall 1 \leq i < M,\ u_i=i,\ v_i=i+1$ | 9 |
| 4 | 28~35 | $N \leq 50, M \leq 100$ | 40 |
| 5 | 28~46 | $N \leq 200, M \leq 1000$ | 30 |
| 6 | 2~70 | 無額外限制 | 20 |