[理工] 資演 交大109 (4)(9)(12)

看板Grad-ProbAsk作者 (貓貓只求黑琴ㄍㄟˋ婚 )時間5年前 (2021/01/03 12:49), 5年前編輯推噓8(8推 0噓 28→)
留言36則, 6人參與, 5年前最新討論串1/1
想請問大家幾題QQ 4. https://i.imgur.com/he9Gp5b.jpg
這題答案是CE 想請問CDE選項 CD）題目說minimum degree是t 代表應該每個node最少有t個child，為什麼有可能會小於t 個child呢？若minimum degree是t 每個node最少應該有t-1個key? E）不知道要怎麼推QQ 9. https://i.imgur.com/VxF6hZE.jpg
這題答案是E 題目的意思應該是把數列從小排到大看有幾個可以滿足 a_i1+a_i2+....+a_i(j-1)<=6a_ij 這樣的話應該都可以滿足？ 1+2+2+2+3+5<=6*6 為什麼答案是5個呢？ 還是有什麼地方我誤會了嗎QQ 12. https://i.imgur.com/tKdskEY.jpg
| 這題不知道怎麼算出X QQ 謝謝大家> < -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.32.191.76 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1609649378.A.51E.html ※ 編輯: try66889 (114.32.191.76 臺灣), 01/03/2021 12:50:50
推
01/03 13:55, 5年前 , 1F
第4題, root不在限制範圍 然後最後一個選項去看clr
01/03 13:55, 1F
→
01/03 13:55, 5年前 , 2F
s, 題目的是移項後的結果 第9題, 順序不能自己改,
01/03 13:55, 2F
→
01/03 13:55, 5年前 , 3F
只能選或不選, 最後一題, 當dp做湊個答案吧, 或是
01/03 13:55, 3F
→
01/03 13:55, 5年前 , 4F
按照題目講的當作min cost max flow 問題用Ford fu
01/03 13:55, 4F
→
01/03 13:55, 5年前 , 5F
lkerson做也行，但應該會做很久
01/03 13:55, 5F
感謝k大 > < 前面兩題了解惹!想再請問k大最後一題fulkerson畫出來是這樣嗎@@? 因為畫出後還試很久X算不出<=24 還是其實是我畫錯了? 謝謝 > < https://i.imgur.com/fqUxu2g.jpg
※ 編輯: try66889 (114.32.191.76 臺灣), 01/03/2021 14:18:07 ※ 編輯: try66889 (114.32.191.76 臺灣), 01/03/2021 14:18:46
推
01/03 15:29, 5年前 , 6F
請問有大大可以分享109的交大考古嗎～
01/03 15:29, 6F
a大我題目和解答放google雲端你試試看~ https://reurl.cc/v1yekj
推
01/03 15:36, 5年前 , 7F
01/03 15:36, 7F
→
01/03 15:36, 5年前 , 8F
這個方法其實我也不太會..
01/03 15:36, 8F
→
01/03 15:38, 5年前 , 9F
建議直接試試各種不同的assign方式找出最小，考試
01/03 15:38, 9F
→
01/03 15:38, 5年前 , 10F
中比較有可能只能這樣做
01/03 15:38, 10F
了解~感謝k大!，我再研究看看fulkerson~ 不好意思想再請問k大這題的DP是怎麼做的呢QQ 因為我做很多遍最小是找到22 QQ 取b1 a2 b3 a4 本身cost外再加上C12，C34 QWQ
推
01/03 16:15, 5年前 , 11F
最後一題我算X是22啦，題目有點不太理解意思，但我
01/03 16:15, 11F
→
01/03 16:15, 5年前 , 12F
算是B1B2B3A1，總cost22
01/03 16:15, 12F
j大我和你一樣最小找到22 QQ ※ 編輯: try66889 (114.32.191.76 臺灣), 01/03/2021 16:29:04 ※ 編輯: try66889 (114.32.191.76 臺灣), 01/03/2021 16:31:07
推
01/03 16:50, 5年前 , 13F
我是覺得考場第一時間遇到這種題目要是沒想到怎麼
01/03 16:50, 13F
→
01/03 16:50, 5年前 , 14F
解就只能湊一湊了QQ
01/03 16:50, 14F
→
01/03 16:51, 5年前 , 15F
我是直接全a全b加，然後跳號不考慮，從C最小的開始
01/03 16:51, 15F
→
01/03 16:51, 5年前 , 16F
湊
01/03 16:51, 16F
對阿QQ 考試遇到沒想到應該只能先硬湊QQ 不過我這題湊兩三天惹自己湊不出來XD
→
01/03 19:32, 5年前 , 17F
最後一題，
01/03 19:32, 17F
→
01/03 19:32, 5年前 , 18F
01/03 19:32, 18F
→
01/03 19:37, 5年前 , 19F
中間的邊容量 : 各modules間的通訊成本(雙向都要)，
01/03 19:37, 19F
→
01/03 19:37, 5年前 , 20F
然後自己對自己為無限大
01/03 19:37, 20F
→
01/03 20:23, 5年前 , 21F
flow有些沒更新，不影響結果，修正一下
01/03 20:23, 21F
→
01/03 20:23, 5年前 , 22F
01/03 20:23, 22F
感謝c大QQ 原來圖要這樣畫QQ 不過想請問cost=0的cij不用在圖上畫出來嗎OAO? cost=0是像m1->m1'容量無限大嗎@@? 然後為什麼p1->m3 那邊的流量不能從m3->m3'->m2->m2'->m1->m4'->p2這樣走呢? 最後是因為m4'->p2沒有流滿所以取b1b2b3a4嗎? 不好意思問題有點多> < 再次感謝
→
01/03 20:25, 5年前 , 23F
原po你的13在a,24在b不是最小吧 你好像少算c23的cost
01/03 20:25, 23F
→
01/03 20:25, 5年前 , 24F
這題最小應該是123a, 4b
01/03 20:25, 24F
→
01/03 20:25, 5年前 , 25F
123b, 4a講錯
01/03 20:25, 25F
感謝n大!我以為a對b一個對一個計算communication值就可以惹!原來每個都要計算> < ※ 編輯: try66889 (114.32.191.76 臺灣), 01/03/2021 20:48:24
→
01/03 21:01, 5年前 , 26F
每種cut代表一種分配法，因為各個modules最後都只會
01/03 21:01, 26F
→
01/03 21:01, 5年前 , 27F
屬於p1或p2其中一個cut，所以為了強迫m_i和m_i'(同
01/03 21:01, 27F
→
01/03 21:01, 5年前 , 28F
個modules)只會被同時分到同個cut,它們之間的容量才
01/03 21:01, 28F
→
01/03 21:01, 5年前 , 29F
要設成無限，並不是cost=0的關係
01/03 21:01, 29F
→
01/03 21:03, 5年前 , 30F
然後m1->m4'之間沒邊怎麼流？
01/03 21:03, 30F
推
01/03 21:06, 5年前 , 31F
B1+B2+B3+A4+C2,4+C3,4
01/03 21:06, 31F
→
01/03 21:13, 5年前 , 32F
不過後來想想m_i跟m_i'捏成同一點結果應該會一樣
01/03 21:13, 32F
了解惹!!OWO! 感謝大家 > < ※ 編輯: try66889 (114.32.191.76 臺灣), 01/03/2021 21:24:32 ※ 編輯: try66889 (114.32.191.76 臺灣), 01/03/2021 21:24:54
推
01/03 23:09, 5年前 , 33F
可是為什麼最後一題那個答案有給A啊？看不懂
01/03 23:09, 33F
X=24，24 (mod10) =4 ~ ※ 編輯: try66889 (114.32.191.76 臺灣), 01/03/2021 23:41:29
推
01/03 23:46, 5年前 , 34F
可是算出來X不是22嗎@@
01/03 23:46, 34F
→
01/03 23:47, 5年前 , 35F
沒事沒事
01/03 23:47, 35F
→
01/03 23:47, 5年前 , 36F
我看到上面的了
01/03 23:47, 36F
好XD ※ 編輯: try66889 (114.32.191.76 臺灣), 01/03/2021 23:49:13 ※ 編輯: try66889 (114.32.191.76 臺灣), 01/04/2021 17:43:51
‣ 更多 try66889 的文章
文章代碼(AID): #1VyKpYKU (Grad-ProbAsk)