BZOJ4819 新生舞会

4819: [Sdoi2017]新生舞会

Time Limit: 10 Sec Memory Limit: 128 MB

Description

学校组织了一次新生舞会，Cathy作为经验丰富的老学姐，负责为同学们安排舞伴。有n个男生和n个女生参加舞会买一个男生和一个女生一起跳舞，互为舞伴。Cathy收集了这些同学之间的关系，比如两个人之前认识没计算得出a[i][j] ，表示第i个男生和第j个女生一起跳舞时他们的喜悦程度。Cathy还需要考虑两个人一起跳舞是否方便，比如身高体重差别会不会太大，计算得出 b[i][j]，表示第i个男生和第j个女生一起跳舞时的不协调程度。当然，还需要考虑很多其他问题。Cathy想先用一个程序通过a[i][j]和b[i][j]求出一种方案，再手动对方案进行微调。Cathy找到你，希望你帮她写那个程序。一个方案中有n对舞伴，假设没对舞伴的喜悦程度分别是a'1,a'2,...,a'n，假设每对舞伴的不协调程度分别是b'1,b'2,...,b'n。令C=(a'1+a'2+...+a'n)/(b'1+b'2+...+b'n),Cathy希望C值最大。

Input

第一行一个整数n。

接下来n行，每行n个整数，第i行第j个数表示a[i][j]。

接下来n行，每行n个整数，第i行第j个数表示b[i][j]。

1<=n<=100,1<=a[i][j],b[i][j]<=10^4

Output

一行一个数，表示C的最大值。四舍五入保留6位小数，选手输出的小数需要与标准输出相等

Sample Input

3
19 17 16
25 24 23
35 36 31
9 5 6
3 4 2
7 8 9

Sample Output

5.357143

题解

分数规划 + 网络流

二分C值，设当前C值为C', 每对人对答案的贡献为\( a - b * C' \)，费用流使贡献总和最大，为正则说明C'可行。

使用迭代会使效率更高，每次费用流都是在找一个尽量更优或可行的答案，所以我们把费用流跑出的方案记录下来，作为下一次的C'值。

每次迭代结束比较上一次的C'与现在跑出来的C''，差的绝对值小于eps则找到最优解，C'的初始值任意。

代码

/* Stay hungry, stay foolish. */

#include<iostream>

#include<algorithm>

#include<queue>

#include<string>

#include<map>

#include<vector>

#include<set>

#include<sstream>

#include<stack>

#include<ctime>

#include<cmath>

#include<cctype>

#include<climits>

#include<cstring>

#include<cstdio>

#include<cstdlib>

#include<iomanip>

#include<bitset>

#include<complex>

using namespace std;

/*

#define getchar() getc()

char buf[1<<15],*fs,*ft;

inline char getc()  {return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin)),fs==ft)?0:*fs++;}

*/

template <class _T> inline void read(_T &_x) {

    int _t; bool _flag=false;

    while((_t=getchar())!='-'&&(_t<''||_t>'')) ;

    if(_t=='-') _flag=true,_t=getchar(); _x=_t-'';

    while((_t=getchar())>=''&&_t<='') _x=_x*+_t-'';

    if(_flag) _x=-_x;

}

typedef long long LL;

const int maxn = ;

const int maxm = ;

const double eps = 1e-;

struct Edge {

    int v, from, nxt, flow; double cost;

    Edge() {}

    Edge(int a, int b, int c, double d): v(a), nxt(b), flow(c), cost(d) {}

}e[maxm];

int fir[maxn], ecnt, pre[maxn], preu[maxn];

double dis[maxn]; bool vis[maxn];

inline void addedge(int a, int b, int c, double d) {

    e[++ecnt] = Edge(b, fir[a], c, d), fir[a] = ecnt;

    e[++ecnt] = Edge(a, fir[b], , -d), fir[b] = ecnt;

}

int n, sink, a[maxn][maxn], b[maxn][maxn];

inline bool spfa() {

    memset(dis, 0xfe, sizeof (double) * (sink + ));

    memset(vis, false, sizeof (bool) * (sink + ));

    double DMIN = dis[];

    queue<int> q; dis[] = , q.push();

    while (!q.empty()) {

        int now = q.front(); q.pop(); vis[now] = false;

        for (int u = fir[now]; u; u = e[u].nxt) if (e[u].flow) {

            if (dis[e[u].v] < dis[now] + e[u].cost) {

                dis[e[u].v] = dis[now] + e[u].cost;

                pre[e[u].v] = now, preu[e[u].v] = u;

                if (!vis[e[u].v]) {

                    vis[e[u].v] = true;

                    q.push(e[u].v);

                }

            }

        }

    }

    return dis[sink] != DMIN;

}

double augment() {

    int now = sink;

    while (now != ) {

        e[preu[now]].flow -= ;

        e[preu[now] ^ ].flow += ;

        now = pre[now];

    }

    return dis[sink];

}

double mcmf() {

    double ret = ;

    while (spfa()) {

        ret += augment();

    }

    return ret;

}

double Run(double ans) {

    ecnt = ;

    memset(fir, , sizeof (int) * (sink + ));

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

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

            addedge(i, j + n, , a[i][j] - ans * b[i][j]);

        }

    }

    for (int i = ; i <= n; ++i) addedge(, i, , );

    for (int i = ; i <= n; ++i) addedge(n + i, sink, , );

    mcmf();

    int ansa = , ansb = ;

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

        for (int u = fir[i]; u; u = e[u].nxt) {

            if (e[u].flow ==  && e[u].v > n && e[u].v < sink) {

                ansa += a[i][e[u].v - n], ansb += b[i][e[u].v - n];

            }

        }

    }

    return (double)ansa / ansb;

}

int main() {

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

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

    read(n); sink = n + n + ;

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

        read(a[i][j]);

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

        read(b[i][j]);

    double prev, ans = ;

    do {

        prev = ans, ans = Run(ans);

    } while (fabs(ans - prev) > eps);

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

    return ;

}

巴特西