自动搬运

查看原文

来自洛谷，原作者为

	Purslane AFO

搬运于2025-08-24 23:07:54，当前版本为作者最后更新于2025-01-02 20:15:12，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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;
}