constructions专题

hdu 3917 Road constructions

题意:有m个公司,k条路,每个公司修条路都要向政府交一定的税,同时政府也要向该公司付修路费,还有如果a和b公司是合作关系,那么你选了a修路,就必须要选b。(如果a负责修A-B,b负责修B-C,那么就定义a和b为合作的关系),问政府最大收益为多少。最大权闭合图:建立超级源点和每个公司相连,权值为该公司修路的税费。每个公司和其合作的公司相连,权值为inf。每个公司和汇点相连,权值为它对应的修