[SDOI2017] 新生舞会 - 二分图最大权匹配,分数规划,二分答案

有一个二分图，每个部都有 \(n\) 个点，每条边有两个参数 \(a_e, b_e\)，求一种匹配，使得 \(\sum a_i / \sum b_i\) 最大

Solution

显然的分数规划，考虑二分一个答案 \(mid\)，那么设每条边的权值为 \(c_i = a_i - kb_i\)

然后跑二分图最大权匹配，如果跑出来答案大于 \(0\) 就表明 OK，可以将答案调大，否则调小。

KM 在稠密的时候比 MCMF 跑的快点，对这题的话其实都能过吧

#include <bits/stdc++.h>

using namespace std;

#define reset(x) memset(x,0,sizeof x)

#define reset3f(x) memset(x,0x3f,sizeof x)

#define int long long

#define ll long long

// Input: g[v][u] (v in II, u in I)

// Method: solve(n1,n2)

// Output: ans, mat[u] (u in I)

namespace km {

const double inf=1e+9;

const int MX=405;

int n,m;

int py[MX],vy[MX],pre[MX];

double slk[MX],g[MX][MX],kx[MX],ky[MX],ans;

int mat[MX];

void clear() {

    n=m=0;

    reset(py); reset(vy); reset(pre);

    reset(slk); reset(g); reset(kx); reset(ky);

}

void KM(){

	int i,j,k,x,p=0;

	double d,t;

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

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

			kx[i]=max(kx[i],g[i][j]);

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

		memset(vy,0,sizeof(int)*(n+1));

		for(j=0;j<=n;j++) slk[j]=inf;

		memset(pre,0,sizeof(int)*(n+1));

		for(py[k=0]=i;py[k];k=p){

			d=inf;vy[k]=1;x=py[k];

			for(j=1;j<=n;j++)if(!vy[j]){

				if((t=kx[x]+ky[j]-g[x][j])<slk[j])slk[j]=t,pre[j]=k;

				if(slk[j]<d)d=slk[j],p=j;

			}

			for(j=0;j<=n;j++)

                if(vy[j])kx[py[j]]-=d,ky[j]+=d;

                else slk[j]-=d;

		}

		for(;k;k=pre[k])py[k]=py[pre[k]];

	}

}

void solve(int n1,int n2){

	n=max(n1,n2);

	KM();

	ans=0;

	for(int i=1;i<=n;i++)ans+=kx[i]+ky[i];

	for(int i=1;i<=n1;i++)mat[i]=(g[py[i]][i]?py[i]:0);

}

}

int n;

double a[105][105],b[105][105];

signed main() {

    cin>>n;

    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) cin>>a[i][j];

    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) cin>>b[i][j];

    double l=0,r=1e+9;

    while(r-l>1e-8) {

        double mid=(l+r)/2;

        km::clear();

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

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

                km::g[j][i]=a[i][j]-mid*b[i][j];

            }

        }

        km::solve(n,n);

        if(km::ans>0) l=mid;

        else r=mid;

    }

    printf("%.6lf",l);

}

巴特西

[SDOI2017] 新生舞会 - 二分图最大权匹配,分数规划,二分答案

Solution

最新文章

热门文章