作者
031502500 林炜鴻
Github連結
項目位址
輸入資料
input_data.txt
這組資料從結果上看沒有unlucky_department
我們先是随機了所有部門的tags和event schedule，
之後又随機了所有學生的tags和free time
之後對每一個學生，周遊所有部門，并設一個參數NegScore反映出學生對每一個部門的喜愛程度
NegScore越小，則表示該學生越喜歡這個部門
在尋找的過程中，不斷将時間沖突的部門用NegScore較小的那一個替換
確定此學生申請的所有部門互不沖突
最後對所有部門的NegScore排序，取最小的不超過5個的部門
模組化過程
問題模組化
我們利用了最小費用最大流算法來解決此問題。
将所有學生和部門都抽象成圖上的點。
流量即為通過部門申請的人次，費用即為所有學生的喜好程度的和。
第二次結對作業
算法實作
當A學生向B部門提出入部申請的時候，就從A向B連一條流量為1的邊。
這條邊容量為1，費用為這個B部門在A學生心目中的名次。
名次越高，費用越低，進而越可能選中這條邊。
之後從源點向每個學生連一條流量為無窮，費用為0的邊。
從每個部門向彙點連一條流量為該部門限定人數，費用為0的邊。
之後在圖上跑一遍費用流。
算法結束之後，如果A學生到B部門的邊上有流量通過，則說明A加入了B部門。
是以隻要周遊一下所有學生和部門之間的連邊，檢查邊上的流量情況，就能獲得所有部門的部員情況以及未能加入任一部門的學生和沒有部員的部門。
代碼規範
- 利用較為詳細的命名方法對變量，函數和對象進行命名。
第二次結對作業 - 對不需要修改的算法和函數進行封裝。
第二次結對作業 - 利用C11新特性來簡化對容器周遊的書寫。
第二次結對作業
結果評估
此算法所能求出的最大人次，并非至少參與一個部門的學生的最大值（即unlucky_student的最小值），而是所有部門部員數總和的最大值。同時在此優化目标下，求出了全局權值最優的一個解。
這個算法的好處在于，能夠簡單地建立模型，實作算法，并且對問題得出一個合理的解。
這個算法的缺陷在于，不能處理一名學生申請的多個部門之間時間上互相沖突的情況。
最後一點感想
這次結隊過程總體來說還是比較順利的。經過上一次的磨合，編碼前的讨論非常快的就完成了。确認好分工之後，就各自完成了自己的部分。浴盆同學代碼能力了得，幾乎沒有什麼bug，讓人十分放心。我對于他代碼裡不懂的部分，也很耐心地解釋給我聽了，帥氣地不行。雖然在編碼過程中有一些編碼風格的差異，但我覺得這并不是短期内能解決的。但是在一番努力和一些工具的幫助下，也總算能比較一緻地規範代碼風格了，最後看着40多小時寫成的上百行的代碼，還是很有成就感的。