題目大意：n個(gè)小朋友投票，定義投票的沖突數(shù)為好友間發(fā)生沖突數(shù)加上所有和自己意愿發(fā)生沖突的人數(shù)，求沖突最少數(shù)
分析：增加源匯點(diǎn)，s向所有同意的連容1的邊，所有反對(duì)的向t連容1的邊，若倆人是好友，則相互連容1邊
對(duì)于經(jīng)過(guò)好友間的流量，表示著沖突，即可用沖突或改變意愿來(lái)替代，那么最小割就成了沖突數(shù)的定義
看到網(wǎng)上的幾個(gè)代碼都進(jìn)行了拆點(diǎn)，我覺(jué)得似乎沒(méi)有必要，直接構(gòu)圖，AC.看來(lái)感覺(jué)是對(duì)的，但我有些疑惑的是為什么要把正反兩條邊都建起來(lái)，后來(lái)想了一下，其實(shí)最小割模型中有個(gè)偏序的關(guān)系，模型的一側(cè)是包含s的一組結(jié)點(diǎn)，右側(cè)是包含t的一組結(jié)點(diǎn)，而SET(S)到SET(T)應(yīng)該是相連的，而如果建成單相邊的話，有可能導(dǎo)致S,T之間沒(méi)有路徑存在。而最小割中恰好又只取S->T的邊，所以無(wú)論關(guān)系是怎樣的，都可以滿足要求，取兩個(gè)朋友之間的一條邊，此題得解。