P2057 [SHOI2007] 善意的投票 / [JLOI2010] 冠军调查
大意
我们定义一次投票的冲突数为下面两者相加：
-
实际投票不同的好朋友对数。
-
自己实际投票和自己本来意愿不同的人数。
我们的问题就是，每位小朋友应该怎样投票，才能使冲突数最小？
思路
我们建立超级源点 \(S\) 表示投赞成的，超级汇点 \(T\) 表示投反对的。那么我们要求的就是最小割。在初始的边连上之后，在好朋友间连双向边。
代码
#include<bits/stdc++.h>
using namespace std;const int MAXN = 305;
const int MAXM = MAXN * MAXN * 10;
struct node{int u, v, nxt, c;
}e[MAXM];
int h[MAXN], tot, pre[MAXN];
void init(){tot = 0;memset(h, -1, sizeof(h));
}
int n, m, S, T;void add(int u, int v, int c){e[tot] = {u, v, h[u], c};h[u] = tot ++;
}bool bfs(){queue<int> q;q.push(S);memset(pre, -1, sizeof(pre));while(!q.empty()){int u = q.front();q.pop();for(int i = h[u];~i;i = e[i].nxt){int v = e[i].v;if(e[i].c && pre[v] == -1){pre[v] = i;if(v == T) return true;q.push(v);}}}return false;
}int EK(){int res = 0;while(bfs()){int Min = 1e9;for(int i = T;i != S;i = e[pre[i]].u){Min = min(e[pre[i]].c, Min);}for(int i = T;i != S;i = e[pre[i]].u){e[pre[i]].c -= Min;e[pre[i] ^ 1].c += Min;}res += Min;}return res;
}int main(){// freopen("monitor.in", "r", stdin);// freopen("monitor.out", "w", stdout);init();cin >> n >> m;//S YES//T NOS = 0, T = n + 1;for(int i = 1;i <= n;i ++){int op; cin >> op;if(op){add(i, T, 1); add(T, i, 0);}else{add(S, i, 1); add(i, S, 0);}}for(int i = 1;i <= m;i ++){int a, b; cin >> a >> b;add(a, b, 1); add(b, a, 0);add(b, a, 1); add(a, b, 0);}cout << EK() << endl;return 0;
}