SHOI2007 善意的投票

wjh15101051's space

卧薪尝胆，厚积薄发。

SHOI2007 善意的投票

Date: Thu Aug 30 00:55:08 CST 2018

In Category: NoCategory

Description：

$n$ 个人，每个人对某个事有看法，有些人是好朋友，每个人可能并不会回答自己内心真实想法，给每个人定方案使得好朋友之间发生冲突的总数加上所有和自己本来意愿发生冲突的人数最小。

$1\le n \le 300$

Solution：

网络流，同意的和源点连边，否决的和汇点连边，好朋友之间连双向边，最小割就是答案。

在最终的图中和源点相连的就是同意，和汇点相连的就是否决。

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 310

#define INF 0x3f3f3f3f

int s,t;

struct edge

{

    int to,nxt,f;

}e[MAXN * 2 + MAXN * MAXN * 2];

int edgenum = 0;

int lin[MAXN];

void add(int a,int b,int f)

{

    e[edgenum].to = b;e[edgenum].f = f;e[edgenum].nxt = lin[a];lin[a] = edgenum;++edgenum;

    e[edgenum].to = a;e[edgenum].f = 0;e[edgenum].nxt = lin[b];lin[b] = edgenum;++edgenum;

    return;

}

int ch[MAXN];

bool check()

{

    queue<int> q;

    q.push(s);

    memset(ch,-1,sizeof(ch));

    ch[s] = 0;

    while(!q.empty())

    {

        int k = q.front();q.pop();

        for(int i = lin[k];i != -1;i = e[i].nxt)

        {

            if(ch[e[i].to] == -1 && e[i].f)

            {

                ch[e[i].to] = ch[k] + 1;

                q.push(e[i].to);

            }

        }

    }

    return (ch[t] != -1);

}

int flow(int k,int f)

{

    if(k == t)return f;

    int r = 0;

    for(int i = lin[k];i != -1 && f > r;i = e[i].nxt)

    {

        if(ch[e[i].to] == ch[k] + 1 && e[i].f)

        {

            int l = flow(e[i].to,min(f - r,e[i].f));

            e[i].f -= l;r += l;e[i ^ 1].f += l;

        }

    }

    if(r == 0)ch[k] = -1;

    return r;

}

int dinic()

{

    int ans = 0,r;

    while(check())while(r = flow(s,INF))ans += r;

    return ans;

}

int main()

{

    memset(lin,-1,sizeof(lin));

    scanf("%d%d",&n,&m);

    int k;

    s = n + 1;t = s + 1;

    for(int i = 1;i <= n;++i)

    {

        scanf("%d",&k);

        if(k == 0)add(s,i,1);

        else add(i,t,1);

    }

    int a,b;

    for(int i = 1;i <= m;++i)

    {

        scanf("%d%d",&a,&b);

        add(a,b,1);add(b,a,1);

    }

    cout << dinic() << endl;

    return 0;

}

In tag: 图论-dinic

wjh15101051