[BZOJ2768][JLOI2010]冠军调查/[BZOJ1934/Luogu2057][SHOI2007]Vote 善意的投票(网络流)

发布于 2018-04-06  73 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ2768][JLOI2010]冠军调查/[BZOJ1934/Luogu2057][SHOI2007]Vote 善意的投票(网络流)

Description

一年一度的欧洲足球冠军联赛已经进入了淘汰赛阶段。随着卫冕冠军巴萨罗那的淘汰,英超劲旅切尔西成为了头号热门。新浪体育最近在吉林教育学院进行了一次大规模的调查,调查的内容就是关于切尔西能否在今年问鼎欧洲冠军。新浪体育的记者从各个院系中一共抽取了n位同学作为参与者,大家齐聚一堂,各抒己见。每一位参与者都将发言,阐述自己的看法。参与者的心里都有一个看法,比如FireDancer认为切尔西不可能夺冠,而WaterDancer认为切尔西一定问鼎。但是因为WaterDancer是FireDancer的好朋友,所以可能FireDancer为了迁就自己的好朋友,会在发言中支持切尔西。也就是说每个参与者发言时阐述的看法不一定就是心里所想的。现在告诉你大家心里的想法和参与者的朋友网,希望你能安排每个人的发言内容,使得违心说话的人的总数与发言时立场不同的朋友(对)的总数的和最小。

Tag

网络流

解决思路

为什么会有两个不同的年份的省选题一模一样?连样例都是一样的?很迷。
考虑把转化成最小割模型,那么,一个人如果违背自己的意愿,相当于是与原来所在的源点/汇点断开,连到另一边;而朋友立场不同,则说明两个人被割开。
那么建图,对每一个人向自己本来的意愿那一边连边,然后对每一对朋友连边,求最小割。

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

#define ll long long
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))

const int maxN=310;
const int maxM=(maxN*maxN+maxN)*2;
const int inf=2147483647;

class Edge
{
public:
    int v,flow;
};

int n,m,S,T;
int edgecnt=-1,Head[maxN],Next[maxM];
Edge E[maxM];
int Depth[maxN],Queue[maxN],cur[maxN];

void Add_Edge(int u,int v,int flow);
bool Bfs();
int dfs(int u,int flow);

int main()
{
    ios::sync_with_stdio(false);mem(Head,-1);

    cin>>n>>m;S=n+1;T=n+2;
    for (int i=1;i<=n;i++)
    {
        int opt;cin>>opt;
        if (opt==0) Add_Edge(S,i,1);
        else Add_Edge(i,T,1);
    }
    for (int i=1;i<=m;i++)
    {
        int u,v;cin>>u>>v;
        Add_Edge(u,v,1);Add_Edge(v,u,1);
    }
    int Ans=0;
    while (Bfs())
    {
        for (int i=1;i<=T;i++) cur[i]=Head[i];
        while (int di=dfs(S,inf)) Ans+=di;
    }
    cout<<Ans<<endl;
    return 0;
}

void Add_Edge(int u,int v,int flow)
{
    edgecnt++;Next[edgecnt]=Head[u];Head[u]=edgecnt;E[edgecnt].v=v;E[edgecnt].flow=flow;
    edgecnt++;Next[edgecnt]=Head[v];Head[v]=edgecnt;E[edgecnt].v=u;E[edgecnt].flow=0;
    return;
}

bool Bfs()
{
    mem(Depth,-1);
    int h=1,t=0;Queue[1]=S;Depth[S]=1;
    do
    {
        int u=Queue[++t];
        for (int i=Head[u];i!=-1;i=Next[i])
            if ((E[i].flow>0)&&(Depth[E[i].v]==-1))
                Depth[Queue[++h]=E[i].v]=Depth[u]+1;
    }
    while (h!=t);
    if (Depth[T]==-1) return 0;
    return 1;
}

int dfs(int u,int flow)
{
    if (u==T) return flow;
    for (int &i=cur[u];i!=-1;i=Next[i])
        if ((E[i].flow>0)&&(Depth[E[i].v]==Depth[u]+1))
        {
            int di=dfs(E[i].v,min(flow,E[i].flow));
            if (di)
            {
                E[i].flow-=di;E[i^1].flow+=di;
                return di;
            }
        }
    return 0;
}

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ2768][JLOI2010]冠军调查/[BZOJ1934/Luogu2057][SHOI2007]Vote 善意的投票(网络流)


HNCJ OIer