[POI2005]KOS-Dicing （最大流+二分）lg3425

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题面https://www.luogu.org/problemnew/show/P3425

题面说赢的最多的人最少赢几场，肯定是向二分的方向思考

建立源点向每一场比赛连容量为1的边，从每场比赛向参赛两个人各连一条容量为1的边，表示一场比赛有一个人赢

二分一个最多的人赢的场数，从每个人向汇点连容量为mid的边，若最大流等于场数，说明符合题意，可以减小最多的人赢的场数，反之缩小

因为要输出方案，可以记录下满足条件的最小答案，然后以这个答案再跑一次，从比赛流向个人的边如果容量为0（也就是在增广时被流过了）说明他赢了这场比赛

#include<bits/stdc++.h>

#include<queue>

using namespace std;

#define INF 0x3f3f3f3f

inline int read(){

    int w=,f=;

    char ch=getchar();

    while(ch<''||ch>''){

        if(ch=='-') f=-;

        ch=getchar();

    }

    while(ch>=''&&ch<=''){

        w=(w<<)+(w<<)+ch-;

        ch=getchar();

    }

    return w*f;

}

int n,m,cnt=-,head[],cur[],depth[],S,T,u[],v[],ans,x[],y[];

const int p=;

bool vis[];

struct Edge{

    int from,to,next,flow;

}edge[];

inline void addedge(int u,int v,int w){

    cnt++;

    edge[cnt].from=u;

    edge[cnt].to=v;

    edge[cnt].flow=w;

    edge[cnt].next=head[u];

    head[u]=cnt;

}

inline void ins(int u,int v,int w){

    addedge(u,v,w);addedge(v,u,);

}

queue<int> q;

inline bool bfs(int st,int ed){

    memset(depth,,sizeof(depth));

    int u,v,i,j,k;q.push(st);depth[st]=;

    for(i=S;i<=T;i++)cur[i]=head[i];

    while(!q.empty()){

        u=q.front();q.pop();

        for(i=head[u];i!=-;i=edge[i].next){

            v=edge[i].to;

            if(!depth[v]&&edge[i].flow){

                depth[v]=depth[u]+;q.push(v);

            }

        }

    }

    return depth[ed];

}

inline int dfs(int u,int ed,int limit){

    if(!limit||u==ed) return limit;

    int v,i,j,k;int flow=,f;

    for(i=cur[u];i!=-;i=edge[i].next){

        v=edge[i].to;cur[u]=i;

        if(depth[v]==depth[u]+&&(f=dfs(v,ed,min(limit,edge[i].flow)))){

            limit-=f;flow+=f;

            edge[i].flow-=f;edge[i^].flow+=f;

            if(!limit) break;

        }

    }

    return flow;

}

inline void Dinic(){

    while(bfs(S,T)){

        ans+=dfs(S,T,INF);

    }

}

inline bool check(int mid){

    cnt=-;memset(head,-,sizeof(head));

    int i,j,k;

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

        ins(S,i,);

        ins(i,x[i]+p,);

        ins(i,y[i]+p,);

    }

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

        ins(i+p,T,mid);

    }

    ans=;Dinic();

    return ans==m;

}

int main(){

    n=read();m=read();int i,j,k;int ans1;

    memset(head,-,sizeof(head));S=;T=;

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

        x[i]=read();y[i]=read();

    }

    int l=,r=m+;

    while(l<=r){

        int mid=(l+r)>>;

        if(check(mid)) r=mid-,ans1=mid;

        else l=mid+;

    }

    cout<<ans1<<endl;

    check(ans1);

    for(int u=;u<=m;u++){

        for(i=head[u];i!=-;i=edge[i].next){

            int v=edge[i].to;v-=p;if(v< or edge[i].flow) continue;

            if(v==x[u]) vis[u]=true;

        }

    }

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

        printf("%d\n",vis[i]);

    }

    return ;

}