[洛谷P2057][SHOI2007]善意的投票

古城微笑少年丶 2021-12-22 04:15 177阅读 0赞

**题目大意：**有$n(n\\leqslant300)$个人，每个人可以选择$0$或$1$，每个人最开始有意愿，有$m(m\\leqslant\\dfrac\{n(n-1)\}2)$对好朋友。定义一次的冲突数为好朋友之间发生冲突的总数加上和自己本来意愿发生冲突的人数。

**题解：**最小割，源点向原意愿为$0$的点连边，原意愿为$1$的向汇点连边，好朋友之间连边。但如果转换为最大流，好朋友之间要连双向边（不然一个人换选择了就会挂，其实想想，连单向边的话谁连谁？）

**卡点：**无

**C++ Code：**

#include <algorithm>
    #include <cstdio>
    #define maxn 310
    #define maxm (maxn * maxn / 2 + maxn * 2)
    const int inf = 0x3f3f3f3f;
    
    namespace Network_Flow {
    	int head[maxn], lst[maxn], cnt = 1;
    	struct Edge {
    		int to, nxt, w;
    	} e[maxm << 1];
    	inline void addedge(int a, int b, int c = 1, int d = 0) {
    		e[++cnt] = (Edge) { b, head[a], c }; head[a] = cnt;
    		e[++cnt] = (Edge) { a, head[b], d }; head[b] = cnt;
    	}
    
    	int st, ed, n, MF;
    	int GAP[maxn], d[maxn];
    	int q[maxn], h, t;
    	void init() {
    		GAP[d[q[h = t = 0] = ed] = 1] = 1;
    		for (int i = st; i <= ed; ++i) lst[i] = head[i];
    		while (h <= t) {
    			int u = q[h++];
    			for (int i = head[u], v; i; i = e[i].nxt) {
    				v = e[i].to;
    				if (!d[v]) {
    					++GAP[d[v] = d[u] + 1];
    					q[++t] = v;
    				}
    			}
    		}
    	}
    	int dfs(int u, int low) {
    		if (!low || u == ed) return low;
    		int w, res = 0;
    		for (int &i = lst[u], v; i; i = e[i].nxt) {
    			v = e[i].to;
    			if (d[u] == d[v] + 1) {
    				w = dfs(v, std::min(low, e[i].w));
    				res += w, low -= w;
    				e[i].w -= w, e[i ^ 1].w += w;
    				if (!low) return res;
    			}
    		}
    		if (!--GAP[d[u]]) d[st] = n + 1;
    		++GAP[++d[u]], lst[u] = head[u];
    		return res;
    	}
    	void ISAP(int S, int T) {
    		st = S, ed = T, n = T - S + 1;
    		init();
    		while (d[st] <= n) MF += dfs(st, inf);
    	}
    }
    using Network_Flow::addedge;
    
    int n, m;
    int main() {
    	scanf("%d%d", &n, &m);
    	int st = 0, ed = n + 1;
    	for (int i = 1, x; i <= n; ++i) {
    		scanf("%d", &x);
    		if (x) addedge(st, i);
    		else addedge(i, ed);
    	}
    	for (int i = 0, a, b; i < m; ++i) {
    		scanf("%d%d", &a, &b);
    		addedge(a, b, 1, 1);
    	}
    	Network_Flow::ISAP(st, ed);
    	printf("%d\n", Network_Flow::MF);
    	return 0;
    }

转载于:https://www.cnblogs.com/Memory-of-winter/p/10347046.html