[BZOJ 2768] 冠军调查

Link：https://www.lydsy.com/JudgeOnline/problem.php?id=2768

Solution：

一道比较基础的最大流的题目

一般看到将点分为两类的题目就要往网络流方向想吧

建图：

源点向每个初始立场为1的人连权值为1的边。

每个初始立场为0的人向汇点连权值为1的边。

好朋友之间互相连权值为1的边。

最小割即是答案。

要满足要求且总和最小，就不能让任何一对(1,0)关系成立，这便对应着最小割模型

割与源/汇点的边对应“说谎”，割二分图内部的边对应“立场不同”

Code：

//by NewErA

#include <bits/stdc++.h>

using namespace std;

#define FF first

#define SS second

#define PB push_back

#define MP make_pair

#define bged(v) (v).begin(),(v).end()

#define foreach(it,s) for(__typeof((s).begin()) it=(s).begin();it!=(s).end();it++)

typedef long long ll;

typedef pair<int,int> P;

typedef pair<pair<int,int>,int> PP;

const int INF=<<;

const int MOD=1e9+;

//My IO system

struct fastio

{

    char s[];

    int it,len;

    fastio(){it=len=;}

    inline char get()

    {

        if(it<len)return s[it++];it=;

        len=fread(s,,,stdin);

        if(len==)return EOF;else return s[it++];

    }

    bool notend()

    {

        char c=get();

        while(c==' '||c=='\n')c=get();

        if(it>)it--;

        return c!=EOF;

    }

}_buff;

#define Read1(x) x=getnum()

#define Read2(x,y) Read1(x),Read1(y)

#define Read3(x,y,z) Read2(x,y),Read1(z)

#define Write1(x) putnum(x),putchar('\n')

#define Write2(x,y) Write1(x),Write1(y)

#define Write3(x,y,z) Write2(x,y),Write1(z)

inline ll getnum()

{

    ll r=;bool ng=;char c;c=_buff.get();

    while(c!='-'&&(c<''||c>''))c=_buff.get();

    if(c=='-')ng=,c=_buff.get();

    while(c>=''&&c<='')r=r*+c-'',c=_buff.get();

    return ng?-r:r;

}

template<class T> inline void putnum(T x)

{

    if(x<)putchar('-'),x=-x;

    register short a[]={},sz=;

    while(x)a[sz++]=x%,x/=;

    if(sz==)putchar('');

    for(int i=sz-;i>=;i--)putchar(''+a[i]);

}

const int MAXN=;

int n,m,s,t,level[MAXN],iter[MAXN],dat[MAXN];

struct edge

{

    int to,cap,rev;

};

vector<edge> a[MAXN];

void add_edge(int to,int from,int cap)

{

    a[to].push_back(edge{from,cap,a[from].size()});

    a[from].push_back(edge{to,cap,a[to].size()-});

}

void bfs()

{

    memset(level,-,sizeof(level));

    queue<int> Q;Q.push(s);level[s]=;

    while(!Q.empty())

    {

        int cur=Q.front();Q.pop();

        for(int i=;i<a[cur].size();i++)

        {

            edge e=a[cur][i];

            if(e.cap && level[e.to]==-)

            {

                level[e.to]=level[cur]+;

                Q.push(e.to);

            }

        }

    }

}

int dfs(int v,int f)

{

    if(v==t) return f;

    int ret=;

    for(int &i=iter[v];i<a[v].size();i++)

    {

        edge &e=a[v][i];

        if(level[e.to]==level[v]+ && e.cap)

        {

            int d=dfs(e.to,min(f,e.cap));

            f-=d;ret+=d;

            e.cap-=d;a[e.to][e.rev].cap+=d;

            if(!f) break;

        }

    }

    return ret;

}

int main()

{

    Read2(n,m);s=n+,t=s+;

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

    {

        Read1(dat[i]);

        if(dat[i]) add_edge(i,t,);

        else add_edge(s,i,);

    }

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

    {

        int x,y;Read2(x,y);

        if(dat[x]!=dat[y]) add_edge(x,y,);

    }

    ll res=;

    while(true)

    {

        memset(iter,,sizeof(iter));

        bfs();int f=;

        if(level[t]<) break;

        res+=dfs(s,INF);

    }

    cout << res;

    return ;

}

Review：

很多时候碰到这样类似的二元关系就要往网络流方向想

割的边容量即为计入答案的数值