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