BZOJ 1934/2768: [SHOI2007]善意的投票 – [最小割]


题目传送门(BZOJ)
>原文链接<

题解 :

S一边赞成, T一边反对,

对于睡觉的从S\to i, 边权为1,表示割掉这条边冲突加1,

不睡觉的从i\to T, 边权为1, 意义一样.

处理好盆友的部分, 对于一对好盆友(i, j), 连(i, j, 1), (j, i, 1), 表示若割掉这条边使得(i, j)分属不同块, 冲突加1

求一次最小割即可

代码 :

(以前的代码, 不清真)

#include 
#include 
#include 
#include 
#include 
using namespace std;
const int inf = 0x3f3f3f3f;
#define N 2000000
queueq;
int at[N];
int nxt[N], to[N], val[N], head[N], cnt=1, dep[N];
int s=N-1, t=N-2;
void add_edge(int a, int b, int c) {
    to[++cnt] = b; nxt[cnt] = head[a]; head[a] = cnt; val[cnt] = c;
    to[++cnt] = a; nxt[cnt] = head[b]; head[b] = cnt; val[cnt] = 0;
}
bool bfs() {
    memset(dep, 0, sizeof(dep));
    while(!q.empty())q.pop();
    q.push(s); dep[s]=1;
    while(!q.empty()) {
        int u=q.front();
        q.pop();
        for(int i=head[u];i;i=nxt[i]) {
            if(val[i]&&!dep[to[i]]) {
                dep[to[i]]=dep[u]+1;
                if(to[i]==t)return 1;
                q.push(to[i]);
            }
        }
    }
    return 0;
}
int dfs(int p, int mf) {
    if(p == t)return mf;
    int nf = 0;
    for(int i = head[p];i;i = nxt[i]) {
        if(dep[to[i]] == dep[p]+1&&val[i]) {
            int tmp=dfs(to[i], min(mf-nf, val[i]));
            if(!tmp)dep[to[i]]=0;
            nf += tmp;
            val[i] -= tmp;
            val[i^1] += tmp;
            if(mf==nf)break;
        }
    }
    return nf;
}
void dinic() {
    int ans = 0, tmp;
    while(bfs()) {
        while((tmp = dfs(s, inf)))
            ans += tmp;
    }
    printf("%d\n", ans);
}
int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i ++ ) scanf("%d", &at[i]);
    for(int i = 1; i <= n; i ++ ) {
        if(at[i]==1) add_edge(s, i, 1);
        else add_edge(i, t, 1);
    }
    for(int i = 1; i <= m; i ++ ) {
        int a, b;
        scanf("%d%d", &a, &b);
        add_edge(a, b, 1);
        add_edge(b, a, 1);
    }
    dinic();
}

发表评论

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