题解 P3705 【[SDOI2017]新生舞会】

· · 题解

然而类似方格取数问题套上一个分数规划。。。

题面意思大致是给一个 n*n 的矩阵，每个元素有两个权值(a,b)

每行每列都只能选一个，最大化\dfrac{\sum_{i=1}^na_i}{\sum_{i=1}^nb_i}

设C=\dfrac{\sum_{i=1}^na_i}{\sum_{i=1}^nb_i}

稍做变形：C*\sum_{i=1}^nb_i = \sum_{i=1}^n a_i

即：

\sum_{i=1}^na_i - C*b_i=0

考虑二分C值，然后套上费用流求解即可。

建图比较简单，每行向源点连1，每列向汇点连1，费用均为 0

然后每行向每列连流量1 费用 a_{i,j}-C*b_{i,j}

#include<bits/stdc++.h>
using namespace std;
int read() {
    char cc = getchar(); int cn = 0, flus = 1;
    while(cc < '0' || cc > '9') {  if( cc == '-' ) flus = -flus;  cc = getchar();  }
    while(cc >= '0' && cc <= '9')  cn = cn * 10 + cc - '0', cc = getchar();
    return cn * flus;
}
const int M = 2e5 + 5 ; 
const int N = 200 + 5 ; 
#define inf 123456789
#define eps 1e-8
#define rep( i, s, t ) for( register int i = s; i <= t; ++ i )
#define Next( i, x ) for( register int i = head[x]; i; i = e[i].next )
struct E {
    int to, next, w;
    double f ; 
} e[M * 2]; 
int head[N * 2], cur[N * 2], cnt, n, mark[N * 2], vis[N * 2], s, t ;
double dis[N * 2], Ans, a[N][N], b[N][N] ;
void add( int x, int y, int z, double f ) {
    e[++ cnt] = (E){ y, head[x], z, f }, head[x] = cnt ; 
    e[++ cnt] = (E){ x, head[y], 0, -f }, head[y] = cnt ; 
} 
queue< int > q; 
bool spfa() {
    rep( i, s, t ) dis[i] = - inf ; 
    memset( vis, 0, sizeof(vis) ) ;
    q.push(s) ; dis[s] = 0 ;
    while( !q.empty() ) {
        int u = q.front() ; q.pop() ; vis[u] = 0;
        Next( i, u ) {
            int v = e[i].to ; 
            if( dis[v] < dis[u] + e[i].f && e[i].w ) {
                dis[v] = dis[u] + e[i].f;
                if( !vis[v] ) q.push(v), vis[v] = 1; 
            }   
        }
    }
    return dis[t] != -inf ;
}
int dfs( int x, int dist ) {
    mark[x] = 1 ; 
    if( x == t ) return dist ; 
    int flow = 0 ; 
    for( register int &i = cur[x]; i; i = e[i].next ) {
        int v = e[i].to ; 
        if( !mark[v] && dis[v] == dis[x] + e[i].f && e[i].w ) {
            int di = dfs( v, min( dist, e[i].w ) ) ; 
            if( di > 0 ) {
                e[i].w -= di, e[i ^ 1].w += di;
                flow += di, dist -= di ; 
                Ans += di * e[i].f ; 
                if( dist == 0 ) return flow ; 
            }
        }
    }
    return flow ;
}
void zkwflow() {
    Ans = 0;
    while(spfa()) {
        memcpy( cur, head, sizeof(head) ) ;
        mark[t] = 1 ; 
        while( mark[t] ) {
            memset( mark, 0, sizeof(mark) ) ;
            dfs( s, inf ) ;
        }
    }
} 
bool check( double x ) {
    s = 0, t = 2 * n + 1 ; cnt = 1;
    memset( head, 0, sizeof(head) );
    rep( i, 1, n ) add( s, i, 1, 0 ), add( i + n, t, 1, 0 ) ;
    rep( i, 1, n ) rep( j, 1, n ) add( i, j + n, 1, a[i][j] - x * b[i][j] );
    zkwflow() ;
    return Ans >= 0 ;
}
void solve() {
    double l = 0, r = 10000 + 5, mid, ans = 0 ;
    while( r - l > eps ) {
        mid = ( l + r ) / 2.0 ; 
        if( check(mid) ) ans = mid, l = mid + eps ; 
        else r = mid - eps ;
    }
    printf("%.6lf\n", ans ) ;
}
signed main()
{
    n = read() ; 
    rep( i, 1, n ) rep( j, 1, n ) a[i][j] = read() ; 
    rep( i, 1, n ) rep( j, 1, n ) b[i][j] = read() ; 
    solve() ; 
    return 0;
}