ACM_Someone like you

摘要： 1 做得還算麻利~ 2 /*最大閉合子圖 3 題意：建通訊站。每個通訊站有一定耗費，兩個特定的通訊站之間建立通訊以后 4 會有一定收益，問怎樣建立通訊站可以使得收益最大 。 5 ——最大權閉合子圖->最小割 6 ——url：http://acm.hdu.edu.cn/showproblem.php?pid=3879 7 思路： 8 首先考慮將圖轉化。 9 即一條通訊線路有一定收益wi（即為正點權），但需要建立兩個通訊站， 10 這兩個通訊站有一定造價pi(即為負點權)。 11 將通訊線路也變成點，點權為收益，連兩條有向只向兩個通訊站。 12 原來的通訊站點權不變。則star... 閱讀全文

摘要： 1 /* 2 hdu 3917 Road constructions 最大權閉合圖 3 題意：n個城市 m個工程公司修路 每個公司要交稅收 有k個路段 分別花銷cost 4 當如果選擇了某個公司，該公司負責的所有的路都要選，還有如果1->2的路由公司A負責， 5 2->3的路由公司B負責，那么如果選了公司A就必須選公司B， 求最大的收益 6 建圖：稅收為正權值、cost為負權值 start連所有公司m end連所有公司m 7 規則要求聯系的公司之間為INF eg addedge(a,b,INF);該處解決方法建結構體詳見具體代碼 8 ... 閱讀全文