题解P1559 运动员最佳匹配问题

简要题意

给出 \(n\) 个白色顶点，\(n\) 个黑色顶点。白色顶点 \(i\) 和黑色顶点 \(j\) 之间的边的权为 \(P_{i,j}\cdot Q_{j,i}\)，求二分图最大权匹配。

思路

二分图最大权匹配，可以使用网络流（具体来说，是费用流）求解。如果学过最大流求二分图最大匹配，那么这篇题解是很容易看懂的。

首先，建立一个超级源点 \(S\) 和超级汇点 \(T\)。对于白色顶点 \(i\)，连边 \((S,i,1,0)\)。对于黑色顶点 \(j\)，连边 \((j,T,1,0)\)。

然后对于白色顶点 \(i\) 和黑色顶点 \(j\)，连边 \((i,j,1,P_{i,j}\cdot Q_{j,i})\)。

由于求的是最大权匹配，我们需要以 \(S\) 为源点，\(T\) 为汇点，跑 最大费用最大流，所求得的代价就是答案。

由于边数 \(m = n^2\)，所以整体时间复杂度是 \(O(n^3)\) 的。

代码

#include <bits/stdc++.h>

using namespace std;

namespace MCMF{

    #define int long long

	struct edge{

		int nxt,to,cap,cost;

	} g[100005];

	int head[100005],ec=-1;

	void add(int from,int to,int cap,int cost){

		g[++ec].nxt=head[from];

		g[ec].to=to;

		g[ec].cap=cap;

		g[ec].cost=cost;

		head[from]=ec;

	}

	void add_edge(int from,int to,int cap,int cost){

		add(from,to,cap,cost);

		add(to,from,0,-cost);

	}

	queue<int> q;

	bool vis[100005];

	int flow[100005];

	int dis[100005];

	int pre[100005];

	int last[100005];

	bool spfa(int s,int t){

		memset(dis,0x8f,sizeof(dis));

		memset(flow,0x7f,sizeof(flow));

		memset(vis,0,sizeof(vis));

		q.push(s);

		vis[s]=1;

		dis[s]=0;

		pre[t]=-1;

		while(!q.empty()){

			int u=q.front();

			q.pop();

			vis[u]=0;

			for(int i=head[u];i!=-1;i=g[i].nxt){

				int v=g[i].to;

				if(g[i].cap>0 && dis[v]<dis[u]+g[i].cost){

					dis[v]=dis[u]+g[i].cost;

					pre[v]=u;

					last[v]=i;

					flow[v]=min(flow[u],g[i].cap);

					if(!vis[v]){

						vis[v]=1;

						q.push(v);

					}

				}

			}

		}

		return pre[t]!=-1;

	}

	pair<int,int> MCMF(int s,int t){

		int maxflow=0,mincost=0;

		while(spfa(s,t)){

			int now=t;

			maxflow+=flow[t];

			mincost+=flow[t]*dis[t];

			while(now!=s){

				g[last[now]].cap-=flow[t];

				g[last[now]^1].cap+=flow[t];

				now=pre[now];

			}

		}

		return make_pair(maxflow,mincost);

	}

	#undef int

}

int a[105][105][2];

signed main(){

	memset(MCMF::head,-1,sizeof(MCMF::head));

	MCMF::ec=-1;

	int n,m,s,t;

	cin>>n;

	s=0,t=n<<1|1;

	for(int sex=0;sex<=1;sex++){

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

			for(int j=1;j<=n;j++){

				cin>>a[i][j][sex];

			}

		}

	}

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

		MCMF::add_edge(s,i,1,0);

		MCMF::add_edge(i+n,t,1,0);

		for(int j=1;j<=n;j++){

			MCMF::add_edge(i,j+n,1,a[i][j][0]*a[j][i][1]);

		}

	}

	cout<<MCMF::MCMF(s,t).second<<'\n';

	return 0;

}

巴特西

题解P1559 运动员最佳匹配问题

简要题意

思路

代码

最新文章

热门文章