【洛谷2057】 [SHOI2007]善意的投票（最小割）

传送门

Solution

比较巧妙啊！

考虑这个只有同意和不统一两种，所以直接令\(s\)表示选，\(t\)表示不选，然后在朋友直接建双向边就好了。

代码实现

#include<bits/stdc++.h>

using namespace std;

const int N=500010,Inf=1e9+10;

int front[N],cnt,s,t,n,m;

struct node

{

    int to,nxt,w;

}e[1500010];

queue<int>Q;

int dep[N];

inline int gi()

{

	int sum=0,f=1;char ch=getchar();

	while(ch>'9' || ch<'0'){if(ch=='-')f=-1;ch=getchar();}

	while(ch>='0' && ch<='9'){sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}

	return f*sum;

}

void Add(int u,int v,int w)

{

    e[cnt]=(node){v,front[u],w};front[u]=cnt++;

    e[cnt]=(node){u,front[v],0};front[v]=cnt++;

}

bool bfs()

{

    memset(dep,0,sizeof(dep));

    Q.push(s);dep[s]=1;

    while(!Q.empty())

    {

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

        for(int i=front[u];i!=-1;i=e[i].nxt)

        {

            int v=e[i].to;

            if(!dep[v] && e[i].w)

            {

                dep[v]=dep[u]+1;Q.push(v);

            }

        }

    }

    return dep[t];

}

int dfs(int u,int flow)

{

    if(u==t || !flow)return flow;

    for(int i=front[u];i!=-1;i=e[i].nxt)

    {

        int v=e[i].to;

        if(dep[v]==dep[u]+1 && e[i].w)

        {

            int di=dfs(v,min(flow,e[i].w));

            if(di)

            {

                e[i].w-=di;e[i^1].w+=di;

                return di;

            }

            else dep[v]=0;

        }

    }

    return 0;

}

int dinic()

{

    int flow=0;

    while(bfs())

    {

        while(int d=dfs(s,Inf))flow+=d;

    }

    return flow;

}

int main()

{

#ifndef ONLINE_JUDGE

	freopen("in.in","r",stdin);

#endif

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

	n=gi();m=gi();t=n+1;

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

	{

		int x=gi();

		if(x)Add(s,i,1);

		else Add(i,t,1);

	}

	while(m--)

	{

		int u=gi(),v=gi();

		Add(u,v,1);Add(v,u,1);

	}

	printf("%d\n",dinic());

	return 0;

}

巴特西

【洛谷2057】 [SHOI2007]善意的投票（最小割）

传送门

Solution

代码实现

最新文章

热门文章