洛谷P2057 【SHOI2007】善意的投票

这道题是最小割的一个经典应用：划分集合。

题目的意思就是就是将所有的小朋友分为两个集合：同意睡觉和不同意睡觉的。不同的集合之间的边都要断开。

我们设\(S\)为投票结果为不想睡觉的小朋友(颜色为0)的集合；\(T\)为投票结果为想睡觉的小朋友(颜色为1)的集合。然后对于一个小朋友\(i\)，设他的“颜色”为x，那么我们就连两条边\((S,i,[x!=0]),(i,T,[x!=1])\)。第一条边表示该小朋友属于\(S\)集合，第二条边表示该小朋友属于\(T\)集合。

因为投与自己意愿相反的票会产生冲突，所以需要给定流量。

然后对于一对好朋友\(i,j\)，我们连\((i,j,1)\)的双向边。

实际操作中，流量为0的边自然可以不连。

答案就是最小割。这是因为，如果\(S\)和\(T\)之间还有流量，说明还有至少一对有冲突的好朋友存在。从这个角度来想，那么答案和最小割等价的。

如果要问最后小朋友们投的是那些票，那就看最小割割的是哪些边。如果割的是\((i,j)\)，表示保留冲突。如果割的是\((s,i)\)或\((i,T)\)，表示\(i\)投了意愿相反的票。

代码：

#include
    
     #define ll long long#define N 305using namespace std;inline int Get() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}while('0'<=ch&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;}int n,m;int S,T;struct load {    int to,next;    int flow;}s[N*N<<2];int h[N],cnt=1;void add(int i,int j,int flow) {    s[++cnt]=(load) {j,h[i],flow};h[i]=cnt;    s[++cnt]=(load) {i,h[j],0};h[j]=cnt;}int dis[N],gap[N];int dfs(int v,int maxf) {    if(v==T) return maxf;    int ret=0;    for(int i=h[v];i;i=s[i].next) {        int to=s[i].to;        if(s[i].flow&&dis[to]+1==dis[v]) {            int dlt=dfs(to,min(maxf-ret,s[i].flow));            s[i].flow-=dlt;            s[i^1].flow+=dlt;            ret+=dlt;            if(ret==maxf||dis[S]>=n+2) return ret;        }    }    if(!(--gap[dis[v]])) dis[S]=n+2;    gap[++dis[v]]++;    return ret;}int sap() {    memset(gap,0,sizeof(gap));    memset(dis,0,sizeof(dis));    gap[0]=n+2;    int ans=0;    while(dis[S]