[Sdoi2017]新生舞会 [01分数规划 二分图最大权匹配]

[Sdoi2017]新生舞会

题意：沙茶01分数规划

---

貌似\(*10^7\)变成整数更科学

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <cmath>

using namespace std;

typedef long long ll;

#define fir first

#define sec second

const int N=205, INF=1e9, M=1e5+5;

const double eps=1e-10;

inline int read() {

	char c=getchar(); int x=0, f=1;

	while(c<'0' || c>'9') {if(c=='-')f=-1; c=getchar();}

	while(c>='0' && c<='9') {x=x*10+c-'0'; c=getchar();}

	return x*f;

}

int n, s, t, a[N][N], b[N][N];

namespace cf {

	struct edge{int v, ne, c, f; double w;} e[M];

	int cnt=1, h[N];

	inline void ins(int u, int v, int c, double w) { //printf("ins %d %d  %lf\n",u,v,w);

		e[++cnt]=(edge){v, h[u], c, 0, w}; h[u]=cnt;

		e[++cnt]=(edge){u, h[v], 0, 0, -w}; h[v]=cnt;

	}

	int q[N], head, tail, inq[N]; double d[N];

	int pre[N], pos[N];

	inline void lop(int &x) {if(x==N) x=1;}

	int tt=0;

	bool spfa() {  //printf("spfa %d\n", ++tt);

		memset(inq, 0, sizeof(inq));

		for(int i=s; i<=t; i++) d[i] = -INF;

		head=tail=1;

		q[tail++]=s; inq[s]=1; d[s]=0;

		pre[t] = -1;

		while(head != tail) {

			int u = q[head++]; lop(head); inq[u]=0; //if(tt==2)printf("u %d\n", u);

			for(int i=h[u];i;i=e[i].ne) {

				int v = e[i].v; //printf("v %d  %d  %lf\n",v, e[i].c>e[i].f, d[v]);

				if(e[i].c > e[i].f &&  d[v] < d[u] + e[i].w ) {

					d[v] = d[u] + e[i].w;

					pre[v] = u; pos[v] = i;

					if(!inq[v]) {

						inq[v] = 1;

						if(d[v] > d[q[head]]) head--, lop(head), q[head] = v;

						else q[tail++] = v,  lop(tail);

					}

				}

			}

		}

		return pre[t] != -1;

	}

	double ek() {

		int flow=0; double cost=0;

		while(spfa()) {

			int x, f=INF;

			for(int i=t; i!=s; i=pre[i]) x=pos[i], f = min(f, e[x].c - e[x].f);

			flow += f;

			cost += d[t]*f; //printf("ek %d %d %lf\n",f,flow,(double)cost);

			for(int i=t; i!=s; i=pre[i]) x=pos[i], e[x].f += f, e[x^1].f -= f;

		}

		return cost;

	}

	bool check(double mid) { //printf("check %lf\n",mid);

		s=0; t=n+n+1;

		cnt=1; memset(h, 0, sizeof(h));

		for(int i=1; i<=n; i++) ins(s, i, 1, 0), ins(i+n, t, 1, 0);

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

			for(int j=1; j<=n; j++) ins(i, j+n, 1, (double) a[i][j] - mid*b[i][j]);

		return ek() > eps;

	}

	void solvebequone() {

		s=0; t=n+n+1;

		cnt=1; memset(h, 0, sizeof(h));

		for(int i=1; i<=n; i++) ins(s, i, 1, 0), ins(i+n, t, 1, 0);

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

			for(int j=1; j<=n; j++) ins(i, j+n, 1, (double)a[i][j]);

		double ans = ek();

		printf("%.6lf", ans / n);

	}

}

void solve() {

	double l=0, r=1e4;

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

		double mid = (l+r)/2.0; //printf("mid %lf\n", mid);

		if(cf::check(mid)) l=mid;

		else r=mid;

	}

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

}

int main() {

	freopen("ball.in", "r", stdin);

	freopen("ball.out", "w", stdout);

	n=read();

	int flag=0;

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

	for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) {b[i][j]=read(); if(b[i][j] != 1) flag=1;}

	if(!flag) cf::solvebequone();

	else solve();

	//printf("\n\ntime %lf\n", (double)clock()/CLOCKS_PER_SEC);

}