题解：CF847J Students Initiation

SFlyer · 2024-11-28 17:29:17 · 题解

考虑这个限制有点难刻画，那么我们就上网络流。因为是恰好一个人给另一个人，说明流的大小一定是 m。二分一下，设答案是 k，建图（上标是流量）：

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int N = 2e4+4;
const int inf = 2e9;

struct edge {
    int to,cap,rev;
};

int lvl[N],vis[N];
vector<edge> g[N];

void ae(int u,int v,int w){
    g[u].push_back({v,w,g[v].size()});
    g[v].push_back({u,0,g[u].size()-1});
}

void bfs(int s){
    memset(lvl,-1,sizeof lvl);
    queue<int> q;
    q.push(s),lvl[s]=0;
    while (!q.empty()){
        int u=q.front();
        q.pop();
        for (auto v : g[u]){
            if (v.cap>0 && lvl[v.to]<0){
                lvl[v.to]=lvl[u]+1;
                q.push(v.to);
            }
        }
    }
}

int dfs(int v,int t,int f){
    if (v==t) return f;
    for (int &i=vis[v]; i<g[v].size(); i++){
        edge &e=g[v][i];
        if (e.cap>0 && lvl[v]<lvl[e.to]){
            int d=dfs(e.to,t,min(f,e.cap));
            if (d>0){
                e.cap-=d,g[e.to][e.rev].cap+=d;
                return d;
            }
        }
    }
    return 0;
}

int mf(int s,int t){
    int ans=0;
    while (1){
        bfs(s);
        if (lvl[t]<0) return ans;
        memset(vis,0,sizeof vis);
        int f;
        while ((f=dfs(s,t,inf))>0) ans+=f;
    }
} 

int cnt;

void init(){
    cnt=0;
    for (int i=0; i<N; i++) g[i].clear();
}

int n,m,u[N],v[N],id[N];

bool chk(int mid){
    init();
    int S=0,T=n+1;
    cnt=n+1;
    for (int i=1; i<=n; i++){
        ae(i,T,mid);
    }
    for (int i=1; i<=m; i++){
        int in=(++cnt);
        id[i]=in;
        ae(in,u[i],1);
        ae(in,v[i],1);
        ae(S,in,1);
    }
    int ans=mf(S,T);
    if (ans==m) return 1;
    return 0;
}

void pr(){
    for (int i=1; i<=m; i++){
        auto e=g[id[i]][0];
        if (e.cap) cout<<v[i]<<" "<<u[i]<<"\n";
        else cout<<u[i]<<" "<<v[i]<<"\n";
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin>>n>>m;
    for (int i=1; i<=m; i++){
        cin>>u[i]>>v[i];
    }
    int l=-1,r=m+1;
    while (l+1<r){
        int mid=l+r>>1;
        if (chk(mid)){
            r=mid;
        }
        else l=mid;
    }
    cout<<r<<"\n";
    chk(r);
    pr();
    return 0;
}