题解：P11502 [ROIR 2019 Day 2] 配对

· · 题解

Solution

关键观察：无论配对长啥样，b_t 不变。因为他显然是 a_{*,t} 的中位数。

因此我们已经可以将整张图分成一个二分图。

对于每个点，他实际上可以写成一个 \{0,1,2\}^k 的向量——如果这一维是 0，表示 a_{i,t} < b_t，1 表示 a_{i,t} > b_t，2 表示 a_{i,t}=b_t。

两个点能不能匹配，只和它们的向量之间的关系有关——所以实际上可以用表示向量代替这个点。

这样很容易得到一个点数为 O(3^k)、边数为 O(7^k) 的网络流模型。总复杂度为 O(63^k)（注意这里很难套用网络流求二分图最大匹配的 O(m \sqrt n)，因为边权不全是 1，所以有一步是过不去的。）

考虑把 \{0,1,2\}^k 中的 1 给替换为 0 或 2，这一步的会产生 O(4^k) 条边，左右部点之间的连边只有 O(2^k) 条。这样做到了 O(36^k)（有点类似 P10717）。

但是，我实现了第一种，发现他过了，有没有老哥在评论区教一下复杂度分析啊 /kel

#include<bits/stdc++.h>
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=2e5+10;
int n,k,a[MAXN][10],b[10],cnt[MAXN];
namespace F {
    const int MAXV=5000+10,MAXE=2e6+10,INF=1000000000;
    int s,t,dis[MAXV],hd[MAXV],cur[MAXV],tot=1;
    struct Edge {int to,nxt,f;}edge[MAXE];
    map<pair<int,int>,int> mp;
    void add_edge(int u,int v,int w) {
        edge[++tot]={v,hd[u],w},hd[u]=tot;
        edge[++tot]={u,hd[v],0},hd[v]=tot;
        mp[{u,v}]=tot;
        return ;
    }
    int bfs(void) {
        memset(dis,-1,sizeof(dis));
        queue<int> q;
        dis[s]=0,q.push(s);
        while(!q.empty()) {
            int u=q.front();
            q.pop();
            cur[u]=hd[u];
            for(int i=hd[u];i;i=edge[i].nxt) {
                int to=edge[i].to,f=edge[i].f;
                if(!f||dis[to]!=-1) continue ;
                dis[to]=dis[u]+1,q.push(to);
            }
        }
        return dis[t]!=-1;
    }
    int dinic(int u,int mx) {
        if(u==t) return mx;
        int ans=0;
        for(int i=cur[u];i;i=edge[i].nxt,cur[u]=i) {
            int to=edge[i].to,f=edge[i].f;
            if(!f||dis[to]!=dis[u]+1) continue ;
            int tmp=dinic(to,min(mx,f));
            if(tmp) {
                edge[i].f-=tmp,edge[i^1].f+=tmp,ans+=tmp,mx-=tmp;
                if(!mx) break ;
            }
            else dis[to]=-1;
        }
        return ans;
    }
    int max_flow(void) {
        int ans=0,tmp=0;
        while(bfs()) while(tmp=dinic(s,INF)) ans+=tmp;
        return ans; 
    }
}
vector<int> v[MAXN];
set<int> st,psl[MAXN];
int gain(int id) {
    int mul=0;
    vector<int> vc;
    ffor(i,1,k) {
        int op=-1;
        if(a[id][i]<b[i]) op=0;
        else if(a[id][i]==b[i]) op=1;
        else op=2;
        mul=mul*3+op,vc.push_back(op);
    }
    return v[mul]=vc,st.insert(mul),psl[mul].insert(id),mul;
}
int main() {
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>k;
    ffor(i,1,n) ffor(j,1,k) cin>>a[i][j],a[i][j]*=2;
    ffor(i,1,k) {
        vector<int> v;
        ffor(j,1,n) v.push_back(a[j][i]);
        v.push_back(-INT_MAX);
        sort(v.begin(),v.end());
        if(v[n/2]==v[n/2+1]) b[i]=v[n/2];
        else b[i]=v[n/2]+1;
    }
    F::s=0,F::t=pow(3,k)+1;
    ffor(i,1,n) cnt[gain(i)]++;
    for(auto id:st) if(v[id][0]==0) F::add_edge(F::s,id+1,cnt[id]); else F::add_edge(id+1,F::t,cnt[id]);
    for(auto id1:st) for(auto id2:st) if(v[id1][0]==0&&v[id2][0]!=0) {
        int flg=1;
        ffor(j,0,k-1) if(v[id1][j]==0&&v[id2][j]==0||v[id1][j]==2&&v[id2][j]==2) flg=0;
        if(flg) F::add_edge(id1+1,id2+1,F::INF);
    }
    if(F::max_flow()==n/2) cout<<"YES\n";
    else return cout<<"NO\n",0;
    for(auto id1:st) for(auto id2:st) if(v[id1][0]==0&&v[id2][0]!=0) {
        int flg=1;
        ffor(j,0,k-1) if(v[id1][j]==0&&v[id2][j]==0||v[id1][j]==2&&v[id2][j]==2) flg=0;
        if(flg) {
            int cnt=F::edge[F::mp[{id1+1,id2+1}]].f;
            ffor(tc,1,cnt) cout<<min(*psl[id1].begin(),*psl[id2].begin())<<' '<<max(*psl[id1].begin(),*psl[id2].begin())<<'\n',psl[id1].erase(psl[id1].begin()),psl[id2].erase(psl[id2].begin());
        }
    }
    return 0;
}