P2057善意的投票

发表于 更新于 分类于 本文字数： 345 阅读时长 ≈ 1 分钟

对于同意午睡的，源点到该点权值为1，该点到源点权值为0.

而对于好朋友，则两点建立双向边，权值均为1

对于多对好朋友冲突，我们贪心地取最少的那一边使得总冲突数最少，对于此即为最小割最大流。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
const int N=5e5+86;

struct egdes{
    int to,nxt,w;
}e[N*2];int hd[N*2],cur[N*2],tot=1,st,en;
vi lv;
void add(int x,int y,int w){
    e[++tot]=(egdes){y,hd[x],w};
    hd[x]=tot;
}

int bfs(){
    lv.assign(N,0);
    memcpy(cur,hd,sizeof(hd));
    queue<int> q;
    q.push(st);
    lv[st]=1;
    while(!q.empty()){
        int p=q.front();
        q.pop();
        for(int eg=hd[p];eg;eg=e[eg].nxt){
            int to=e[eg].to,vol=e[eg].w;
            if(vol&&!lv[to]){
                lv[to]=lv[p]+1;
                q.push(to);
            }
        }
    }
    return lv[en];
}

int dfs(int ss,int flow){
    if(ss==en)
    return flow;
    int r=flow;
    for(int eg=cur[ss];eg&&r;eg=e[eg].nxt){
        cur[ss]=eg;
        int to=e[eg].to,vol=e[eg].w;
        if(vol&&lv[to]==lv[ss]+1){
            int c=dfs(to,min(r,vol));
            r-=c;
            e[eg].w-=c;
            e[eg^1].w+=c;
        }
    }
    return flow-r;
}
int nn,mm;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>nn>>mm;
    st=nn+11,en=st+1;
    f(i,1,nn){
        int x;
        cin>>x;
        if(x){
            add(st,i,1);
            add(i,st,0);
            add(i,en,0);
            add(en,i,0);
        }
        else {
            add(st,i,0);
            add(i,st,0);
            add(i,en,1);
            add(en,i,0);
        }
    }
    f(i,1,mm){
        int x,y;
        cin>>x>>y;
        add(x,y,1);
        add(y,x,1);
    }
    LL ans=0;
    while(bfs()){
        ans+=dfs(st,3e8);
    }
    cout<<ans;
    return 0;
}