P3425 [POI2005]KOS-Dicing

· · 题解

前置芝士：网络流

比较好的一道网络流题了，比较适合来练习思维和构图能力，还是老生常谈的一句话：图论的题就是构图 + 跑板子
首先最难的一步，画出源点和汇点这里用 st 和 en 表示 好然后我们考虑将起点和每一场比赛连线，容量为 1，这个的意思就是每个比赛最多有一个人获胜，这里用粉色表示，因为粉色好康
然后将每一场比赛和相对应的两个人连线，容量为 1，代表这个人获胜或者是不获胜，这里用绿色表示
然后将所有人和终点连线
那么问题来了，容量为多少呢？
这个值我们不确定对吧，表示的是胜场的场数，所以我们要去枚举，怎么枚举呢 1-n 依次枚举？那岂不直接上天。很容易可以发现这个其中是有单调性的，如果给的容量越大，那么胜场就会相应的变大，所以我们考虑二分答案，好像 二分答案 + 网络流 已经成固定套路了
此题有可能还过不了，可能会 T 掉，所以简单的再观察亿下，可以发现，我们画的是二分图，所以曾广路会很短，所以我们可以缩小退出 dfs 当然如果你用的是 dinic 就当我没说啦，因为是到源点的距离，所以也无所谓啦，我这种只是提醒使用 ISAP 的同学qwq
然后就轻松的解决了这一题啦，代码也就很简单了 

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#define ll long long
using namespace std;
const int N=300010,M=80000010;
struct MS{
    int from,to,next,z;
}e[M];
int elast[N],cur[N],k=1;
void print(int x,int y,int z){cout<<x<<"->"<<y<<"="<<z<<endl;}
void add(int x,int y,int z)
{
    //print(x,y,z);
    e[++k].to=y,e[k].from=x,e[k].z=z,e[k].next=elast[x],elast[x]=k;
    e[++k].to=x,e[k].from=y,e[k].z=0,e[k].next=elast[y],elast[y]=k;
}
struct MSQWQ{
    int x,y;
}a[N];
int n,m;
int ans;
int st,en;
int dis[N],cnt[N];
void bfs(int en)
{
    queue<int>q;
    q.push(en);
    for(int i=0;i<=N-10;i++)cur[i]=elast[i],dis[i]=-1,cnt[i]=0;
    dis[en]=0;
    cnt[0]=1;
    while(!q.empty())
    {
        int now=q.front();q.pop();
        for(int i=elast[now];i;i=e[i].next)
        {
            int to=e[i].to;
            if(dis[to]==-1)
            {
                dis[to]=dis[now]+1;
                cnt[dis[to]]++;
                q.push(to);
            }
        }
    }
}
int dfs(int x,int flow)
{
    if(x==en)return flow;
    int d=0;
    for(int i=cur[x];i;i=e[i].next)
    {
        cur[x]=i;
        int to=e[i].to;
        if(e[i].z>0&&dis[x]==dis[to]+1)
        {
            int tmp=dfs(to,min(e[i].z,flow-d));
            e[i].z-=tmp;
            e[i^1].z+=tmp;
            d+=tmp;
            if(d==flow||dis[st]>=666)return d;
        }
    }
    if(dis[st]>=666)return d;
    cnt[dis[x]]--;
    if(cnt[dis[x]]==0)dis[st]=666;
    dis[x]++;
    cur[x]=elast[x];
    cnt[dis[x]]++;
    return d;
}
int L,R,mid,qans;
int id[N];
bool check(int mid)
{
    k=1;
    memset(elast,0,sizeof(elast));
    for(int i=1;i<=m;i++)add(st,i,1);
    for(int i=1;i<=m;i++)
    {
        id[i]=k+1;
        add(i,m+a[i].x,1);
        add(i,m+a[i].y,1);      
    }
    for(int i=1;i<=n;i++)add(m+i,en,mid);
    ans=0;
    bfs(en);
    while(dis[st]<666)ans+=dfs(st,1e9);
    if(ans>=m)return true;
    return false;
}
int main()
{
    scanf("%d%d",&n,&m);
    st=0,en=n+m+1;
    for(int i=1;i<=m;i++)scanf("%d%d",&a[i].x,&a[i].y);
    L=m/n,R=m;
    while(L<=R)
    {
        mid=(L+R)/2;
        if(check(mid))qans=mid,R=mid-1;
        else L=mid+1;
    }
    printf("%d\n",qans);
    check(qans);
    for(int i=1;i<=m;i++)
    {
        if(e[id[i]].z==0)printf("1\n");
        else printf("0\n");
    }
    return 0;
}