BZOJ 1934: [Shoi2007]Vote 善意的投票

//真是让人难过呢。。。

Solution

我们需要达到的状态即是本意睡觉的一部分和本意不睡觉的一部分通过一些改变不再有冲突
考虑每一个人如果改变了主意的影响 对答案贡献就是1(改变原意愿) + 他的朋友边数
按此想法连边建图即可 显然结果就是满足两边(本意睡觉的一部分和本意不睡觉的一部分)无连边的情况 最小割即可

Code:

#include <queue>
#include <cstdio> 
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 301;
const int M = 200001;
int dep[N]; queue <int > q; 
int n, m, s, t, ce, head[N];
struct edge {
    int to, nex, val;
} e[M];
inline void add(int u, int v, int w) {
    e[++ ce].to = v, e[ce].nex = head[u], head[u] = ce, e[ce].val = w;
    e[++ ce].to = u, e[ce].nex = head[v], head[v] = ce, e[ce].val = 0;
}

inline bool bfs() {
    memset(dep, 0, sizeof dep);
    dep[s] = 1; q.push(s);
    while(! q.empty()) {
        int x = q.front(); q.pop();
        for(int i = head[x]; i != -1; i = e[i].nex) 
            if(e[i].val && ! dep[e[i].to]) dep[e[i].to] = dep[x] + 1, q.push(e[i].to);
    } return dep[t];
} 
inline int dfs(int x, int flow) {
    if(x == t) return flow; if(dep[x] >= dep[t]) return 0;
    for(int i = head[x]; i != -1; i = e[i].nex) {
        if(e[i].val && dep[e[i].to] == dep[x] + 1) {
            int tmp = dfs(e[i].to, min(e[i].val, flow)); if(! tmp) continue;
            e[i].val -= tmp; e[i ^ 1].val += tmp; return tmp;
        }
    } return 0;
} 
inline int dinic() {
    int ans = 0;
    while(bfs()) ans += dfs(s, 2147483645);
    return ans;
}
inline int read() {
    int x = 0; bool w = 0; char ch = getchar();
    while(ch < '0' || ch > '9') {if(ch == '-') w = 1; ch = getchar();}
    while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
    return w ? - x : x;
}
int main() {
    n = read(), m = read(); 
    s = n + 1, t = n + 2; ce = 1; 
    memset(head, -1, sizeof head); 
    for(int i = 1; i <= n; ++ i) {
        int x = read();
        add(s, i, x); add(i, t, x ^ 1);
    }
    for(int i = 1; i <= m; ++ i) {
        int u = read(), v = read();
        add(u, v, 1); add(v, u, 1);
    } printf("%d", dinic());
    return 0;
}
点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注