【BZOJ1532】[POI2005]Kos-Dicing

2015.08.17 20:18 Mon | 36次阅读 | 旧日oi | 固定链接 | 源码

Description

Dicing 是一个两人玩的游戏,这个游戏在Byteotia非常流行. 甚至人们专门成立了这个游戏的一个俱乐部. 俱乐部的人时常在一起玩这个游戏然后评选出玩得最好的人.现在有一个非常不走运的家伙,他想成为那个玩的最好的人,他现在知道了所有比赛的安排,他想知道,在最好的情况下,他最少只需要赢几场就可以赢得冠军,即他想知道比赛以后赢的最多的那个家伙最少会赢多少场.

Input

第一行两个整数n 和 m, 1 <= n <= 10 000, 0 <= m <= 10 000; n 表示一共有多少个参赛者, m 表示有多少场比赛. 选手从1 到 n编号. 接下来m 行每行两个整数表示该场比赛的两个选手,两个选手可能比赛多场.

题解

看到这种题一般都会想到网络流……
源点和比赛连流量为1的边,比赛和两个选手连容量1的边,二分选手和汇点连的边的权值,求出能满流的最小权值。
正确性显然。

我的程序

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
#define N 10005
struct edge
{
    int to,next,flow;
}e[N*10],_e[N*10];
int h[N<<1],tp;
void ae(int u,int v,int w)
{
    e[tp].to=v;e[tp].next=h[u];
    e[tp].flow=w;h[u]=tp++;
}
void add(int u,int v,int w)
{
    ae(u,v,w);ae(v,u,0);
}
int n,m,S,T;
queue<int> q;
int dis[N<<1],rk[N];
#define inf 0x3f3f3f3f
bool bfs()
{
    while(!q.empty()) q.pop();q.push(S);
    memset(dis,0,sizeof(dis));dis[S]=1;
    while(!q.empty())
    {
        int u=q.front();q.pop();
        for(int v,i=h[u];i!=-1;i=e[i].next)
        if(e[i].flow&&!dis[v=e[i].to])
        {
            dis[v]=dis[u]+1;
            if(v==T) return 1;
            q.push(v);
        }
    }
    return 0;
}
int dfs(int u,int limit)
{
    if(u==T) return limit;
    int cost=0,tmp;
    for(int v,i=h[u];i!=-1;i=e[i].next)
    if(e[i].flow&&dis[v=e[i].to]==dis[u]+1)
    {
        tmp=dfs(v,min(limit-cost,e[i].flow));
        if(tmp)
        {
            e[i].flow-=tmp;e[i^1].flow+=tmp;
            cost+=tmp;if(cost==limit) break;
        }
        else dis[v]=-1;
    }
    return cost;
}
int dinic()
{
    int ret=0;
    while(bfs()) ret+=dfs(S,inf);
    return ret;
}
int main()
{
    cin>>n>>m;
    S=0;T=n+m+1;
    memset(h,-1,sizeof(h));
    for(int u,v,i=1;i<=m;i++)
    {
        scanf("%d%d",&u,&v);
        add(S,i,1);add(i,m+u,1);add(i,m+v,1);
    }
    for(int i=1;i<=n;i++)
    {
        rk[i]=tp;
        add(m+i,T,inf);
    }
    memcpy(_e,e,sizeof(e));
    int l=1,r=m,mid,ans=0;
    while(l<=r)
    {
        mid=(l+r)>>1;
        memcpy(e,_e,sizeof(e));
        for(int i=1;i<=n;i++) 
        e[rk[i]].flow=mid,e[rk[i]^1].flow=0;
        if(dinic()==m) ans=mid,r=mid-1;
        else l=mid+1;
    }
    cout<<ans<<endl;
}```