[BZOJ1532][POI2005]Kos-Dicing 二分+最大流



其他方法根本想不出->网络流!
求的是赢得最多的人赢的次数的最小值,满足二分性质,问题转化为check(mid).
我们建立源点s朝每个选手连容量为mid的边,进行比赛的两个选手朝比赛连容量为1的边,比赛朝汇点连容量为1的边,如果流量等于m说明mid可行.

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 40233
#define M 102333
using namespace std;
int n,m,s,t;
int head[N],to[M],next[M],f[M],tot=1;
inline void add(int x,int y,int z)
{
    to[++tot]=y;next[tot]=head[x];head[x]=tot;f[tot]=z;
    to[++tot]=x;next[tot]=head[y];head[y]=tot;f[tot]=0;
}
int dis[N],q[N],l=1,r;
bool bfs()
{
    memset(dis,-1,sizeof dis);
    l=1,r=0;
    q[++r]=s,dis[s]=0;
    int x,y;
    while(l<=r)
    {
        x=q[l++];
        for(int i=head[x];i;i=next[i])if(dis[y=to[i]]==-1&&f[i])
        {
            dis[y]=dis[x]+1;
            if(y==t)return 1;
            q[++r]=y;
        }
    }
    return 0;
}
int dinic(int x,int flow)
{
    if(x==t)return flow;
    int a,temp=flow;
    for(int i=head[x];i;i=next[i])if(f[i]&&dis[to[i]]==dis[x]+1)
    {
        a=dinic(to[i],min(temp,f[i]));
        if(!a)dis[to[i]]=-1;
        temp-=a,f[i]-=a,f[i^1]+=a;
        if(!temp)return flow;
    }
    return flow-temp;
}
int maxflow()
{
    int re=0;
    while(bfs())re+=dinic(s,0x3f3f3f3f);
    return re;
}
int A[M],B[M];
bool check(int mid)
{
    memset(head,0,sizeof head);
    memset(next,0,sizeof next);
    tot=1;
    for(int i=1;i<=m;i++)
    {
        add(A[i],i+n,1);
        add(B[i],i+n,1);
        add(i+n,t,1);
    }
    for(int i=1;i<=n;i++)add(s,i,mid);
    return maxflow()==m;
}
int main()
{
    cin>>n>>m;
    s=0,t=n+m+1;
    for(int x,y,i=1;i<=m;i++)
    {
        scanf("%d%d",&A[i],&B[i]);
    }
    int ll=1,rr=m+2,mid,ans;
    while(ll<rr)
    {
        mid=(ll+rr)>>1;
        if(check(mid))ans=rr=mid;
        else ll=mid+1;
    }
    cout<<ans;
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注