P3705 [SDOI2017]新生舞会 题解


以下题解仅供学习参考使用。

抄袭、复制题解,以达到刷AC率/AC数量或其他目的的行为,在洛谷是严格禁止的。

洛谷非常重视学术诚信。此类行为将会导致您成为作弊者。具体细则请查看洛谷社区规则

评论

  • 还没有评论
作者: xyz32768 更新时间: 2017-12-03 21:08  在Ta的博客查看    5  

由于题目求的是最优配对方案,所以很容易想到建一个二分图后用费用流求解,即建立源点和汇点,由源点向每个男生连一条容量为$1$的边,由每个女生向汇点连一条容量为$1$的边,再从任意一个男生向任意一个女生连一条容量为$1$的边。

再考虑费用分配。这时候主要的问题在于$C=\frac{\sum a}{\sum b}$这个式子中$\sum b$在分母位置,无法简单求和。因此可以利用分数规划的思想去掉分母。先二分答案$ans$。

接下来判断最优解$C$能否大于或等于$ans$。把式子$C=\frac{\sum a}{\sum b}$变形后为$\sum a-C\sum b=0$。这时候就可以推出如果$C\geq ans$,就一定存在一种$\sum a,\sum b$的合法分配方案,使得$\sum a-ans\sum b\geq 0$。此时就可以得出,源点连向男生,以及女生连向源点的边的费用都为$0$,第$i$个男生向第$j$个女生的边的费用为$a_{i,j}-ans*b_{i,j}$。建图完成后,如果最大费用最大流大于等于$0$,那么$C\geq ans$。

代码:

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
inline int read() {
    int res = 0; bool bo = 0; char c;
    while (((c = getchar()) < '0' || c > '9') && c != '-');
    if (c == '-') bo = 1; else res = c - 48;
    while ((c = getchar()) >= '0' && c <= '9')
        res = (res << 3) + (res << 1) + (c - 48);
    return bo ? ~res + 1 : res;
}
const int L = 105, N = 5e5 + 5; const double eps = 1e-8;
int n, a[L][L], b[L][L], ecnt, nxt[N], adj[N], go[N], cap[N], len,
que[N], S, T; double cost[N], dis[N], ans;
bool vis[N], walk[N];
void add_edge(int u, int v, int w, double x) {
    nxt[++ecnt] = adj[u]; adj[u] = ecnt; go[ecnt] = v;
    cap[ecnt] = w; cost[ecnt] = x;
    nxt[++ecnt] = adj[v]; adj[v] = ecnt; go[ecnt] = u;
    cap[ecnt] = 0; cost[ecnt] = -x;
}
bool spfa() {
    int i; for (i = S; i <= T; i++) dis[i] = -1e20, walk[i] = 0;
    dis[que[len = 1] = S] = 0;
    for (i = 1; i <= len; i++) {
        int u = que[i]; vis[u] = 0;
        for (int e = adj[u], v; e; e = nxt[e])
            if (cap[e] > 0 && dis[u] + cost[e] > dis[v = go[e]]) {
                dis[v] = dis[u] + cost[e];
                if (!vis[v]) vis[que[++len] = v] = 1;
            }
    }
    return dis[T] >= -1e19;
}
int dfs(int u, int flow) {
    if (u == T) return ans += dis[T] * flow, flow;
    int res = 0, delta; walk[u] = 1;
    for (int e = adj[u], v; e; e = nxt[e])
        if (!walk[v = go[e]] && cap[e] > 0 &&
        abs(dis[v] - dis[u] - cost[e]) <= eps) {
            delta = dfs(v, min(cap[e], flow - res));
            if (delta) {
                cap[e] -= delta; cap[e ^ 1] += delta;
                res += delta; if (res == flow) break;
            }
        }
    return res;
}
double mcmf() {
    ans = 0;
    while (spfa()) dfs(S, 0x3f3f3f3f);
    return ans;
}
bool check(double mid) {
    int i, j; ecnt = S = 1; T = (n << 1) + 2;
    for (i = S; i <= T; i++) adj[i] = 0;
    for (i = 1; i <= n; i++) add_edge(S, i + 1, 1, 0);
    for (i = n + 2; i < T; i++) add_edge(i, T, 1, 0);
    for (i = 1; i <= n; i++) for (j = 1; j <= n; j++)
        add_edge(i + 1, j + n + 1, 1, 1.0 * a[i][j] - 1.0 * b[i][j] * mid);
    double ap = mcmf(); return abs(ap) <= eps || ap > eps;
}
int main() {
    int i, j; n = read();
    for (i = 1; i <= n; i++) for (j = 1; j <= n; j++)
        a[i][j] = read();
    for (i = 1; i <= n; i++) for (j = 1; j <= n; j++)
        b[i][j] = read();
    double l = -1e7, r = 1e7;
    while (abs(r - l) > eps) {
        double mid = (l + r) / 2;
        if (check(mid)) l = mid;
        else r = mid;
    }
    printf("%.6lf\n", r);
    return 0;
}

评论

  • 还没有评论
作者: 暴躁的蒟蒻 更新时间: 2017-05-07 21:28  在Ta的博客查看    6  

费用流+分数规划+二分答案

首先我们可以想到二分答案C,但C的满足条件似乎并不好处理

但我们可以利用分数规划的思想将C进行转换

C = (a1 + a2 + …… + an) / (b1 + b2 + …… + bn)
(b1 + b2 + …… + bn) * C = (a1 + a2 + …… + an)
(a1 + a2 + …… + an) - (b1 + b2 + …… + bn) * C = 0
(a1 - b1 * C) + (a2 - b2 * C) + …… + (an - bn * C) = 0

由此我们得出这道二分图的最小费用最大流:

1)将源点向每个男生连一条流量为1、费用为0的边

2)将每个女生向汇点连一条流量为1、费用为0的边

3)将每一对男女舞伴间连一条流量为1、费用为[a[i][j] - b[i][j] * C]的边

然后每次判断最小费用是否小于(或大于)0来缩小边界,最后得到答案。

代码如下:

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const double Maxn = 1e9;
const int N = 205, M = 8e4 + 5;
const double eps = 1e-8;
int pre[N], nxt[M], to[M], lst[N], fr[M], flw[M], Q[M];
int n, s, t, T; bool vis[N];
double a[N][N], b[N][N], cst[M], Ans, dis[N]; 
template <class T> inline void CkMin(T &a, const T b) {if (a > b) a = b;}
inline void Add(const int x, const int y, const int z, const double g)
{
    nxt[++T] = lst[x]; lst[x] = T; to[T] = y; fr[T] = x; flw[T] = z; cst[T] = g;
    nxt[++T] = lst[y]; lst[y] = T; to[T] = x; fr[T] = y; flw[T] = 0; cst[T] = -g;
}
inline bool Bul()
{
    for (int i = s; i <= t; ++i) dis[i] = -Maxn;
    int te = 0, we = 1, x, y; 
    dis[Q[1] = s] = 0.0;
    while (te < we)
    {
        x = Q[++te]; vis[x] = false;
        for (int i = lst[x]; i; i = nxt[i])
        if (dis[y = to[i]] < dis[x] + cst[i] && flw[i])
        {
            dis[y] = dis[x] + cst[i]; pre[y] = i; 
            if (!vis[y]) vis[y] = true, Q[++we] = y;
        }
    }
    return dis[t] > -Maxn;
}
inline void Deal()
{
    int Mif = Maxn;
    for (int i = pre[t]; i; i = pre[fr[i]]) CkMin(Mif, flw[i]);
    for (int i = pre[t]; i; i = pre[fr[i]])
     flw[i] -= Mif, flw[i ^ 1] += Mif, Ans += (double)Mif * cst[i];
}
inline bool check(const double mi)
{
    T = 1; memset(lst, 0, sizeof(lst));
    for (int i = 1; i <= n; ++i) 
     Add(s, i, 1, 0), Add(i + n, t, 1, 0);
    for (int i = 1; i <= n; ++i)
     for (int j = 1; j <= n; ++j)
      Add(i, j + n, 1, a[i][j] - mi * b[i][j]);
    Ans = 0.0; while (Bul()) Deal();
    return (Ans <= 0); 
}
int main()
{
    scanf("%d", &n); s = 0; t = (n << 1) + 1;
    for (int i = 1; i <= n; ++i)
     for (int j = 1; j <= n; ++j) scanf("%lf", &a[i][j]);
    for (int i = 1; i <= n; ++i)
     for (int j = 1; j <= n; ++j) scanf("%lf", &b[i][j]);
    double l = 0, r = 1e4;
    while (r - l >= eps)
    {
        double mid = (l + r) / 2;
        (check(mid) ? r : l) = mid;
    } 
    return printf("%.6lf\n", l), 0;
}

评论

  • 还没有评论
作者: 念恒 更新时间: 2018-05-06 17:33  在Ta的博客查看    2  

分数规划,最大费用最大流

题意可以简化为给出一个矩阵,要求每行和每列必须且只能取一个格子,要求$sigma\ a_{i,j}/sigma\ b_{i,j}$ 最大

考虑分数规划,可以将式子转化:

$sigma\ a_{i,j}/sigma\ b_{i,j}=C$

$sigma\ a_{i,j}=sigma\ b_{i,j}*C$

$sigma\ a_{i,j}-sigma\ b_{i,j}*C=0$

$sigma(\ a_{i,j}-b_{i,j}*C)=0$

C就是我们要求的最大值,我们可以$mid$实数二分它,对于每一个$mid$,求出这种情况下$sigma(\ a_{i,j}-b_{i,j}*mid)=0$的最大值,如果最大值小于0,就说明$mid>C$,反之亦然。

至于怎么求最大值,可以将横坐标建一个点集,纵坐标建一个点集,对于每个矩阵上的点$a_{i,j}$建一条从i到j的弧,流量为1,费用为$a_{i,j}-sigma\ b_{i,j}*mid$,然后跑最大费用最大流就行了

代码:

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<map>
#define inf 0x7fffffff
using namespace std;
inline int read()
{
    int ans=0,fh=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
            fh=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
        ans=(ans<<1)+(ans<<3)+ch-'0',ch=getchar();
    return ans*fh;
}
const int maxn=300;
const int maxm=10010;
const double eps=0.00000001;
int s,t,v[maxm*2],u[maxm*2],w[maxm*2],qq[maxn],ll[maxn],nex[maxm*2],head[maxn],num=1,n,a[110][110],b[110][110];
double f[maxm*2],bj[maxn],l,r,mid;
bool cz[maxn];
queue<int>q;
void add(int x,int y,double fee)
{
    u[++num]=x;
    v[num]=y;
    w[num]=1;
    f[num]=fee;
    nex[num]=head[x];
    head[x]=num;
    u[++num]=y;
    v[num]=x;
    w[num]=0;
    f[num]=-fee;
    nex[num]=head[y];
    head[y]=num;
}
bool spfa()
{
    memset(qq,0,sizeof(qq));
    for(int i=1;i<=n*2+2;i++)
        bj[i]=2100000000;
    memset(ll,0,sizeof(ll));
    q.push(s);
    bj[s]=0;
    ll[s]=inf;
    while(!q.empty())
    {
        int now=q.front();
        q.pop();
        cz[now]=0;
        for(int i=head[now];i;i=nex[i])
            if(w[i]&&bj[v[i]]>bj[now]+f[i])
            {
                bj[v[i]]=bj[now]+f[i];
                ll[v[i]]=min(w[i],ll[now]);
                qq[v[i]]=i;
                if(!cz[v[i]])
                    q.push(v[i]),cz[v[i]]=1;
            }
    }
    return qq[t]>0;
}
double EK()
{
    double fee=0;
    while(spfa())
    {
        int liu=ll[t];
        for(int i=qq[t];i;i=qq[u[i]])
            w[i]-=liu,w[i^1]+=liu;
        fee+=liu*bj[t];
    }
    return fee*-1;
}//最大费用最大流
double work(double x)
{
    memset(head,0,sizeof(head));
    num=1;
    for(int i=1;i<=n;i++)
        add(s,i,0),add(i+n,t,0);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            add(i,j+n,(double)x*b[i][j]-a[i][j]);//建图
    return EK();
}
int main()
{
    n=read();
    s=n*2+1;t=s+1;
    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();
    r=1000000;
    while(r-l>eps)
    {
        mid=(l+r)*0.5;
        double dd=work(mid);
        if(dd>=0)
            l=mid;
        else
            r=mid;
    }//实数二分
    printf("%.6lf",l);
    fclose(stdin);
    return 0;
}

评论

  • 还没有评论
作者: Isonan 更新时间: 2018-08-11 23:33  在Ta的博客查看    0  

原题传送门>Here<

我的01分数规划学习笔记>Here<

这道题是道比较有趣的01分数规划题,不仅需要01分数规划的思想,还要应用网络流求解,有一些复杂。

考虑对于二分出的每一个值,我们都可以网络流建图:

从源点向所有男生建边,流为1,费用为0;

从男生向女生建边,流为1,费用为$mid*b_{ij}-a_{ij}$;

从女生向汇点建边,流为1,费用为0。

接下来跑一遍最小费用最大流求出匹配的最小费用,判断是否是负数就可以了。

这题还需要卡一点常,也算是考验下应试技巧。

代码:

#include <cstdio>
#include <cstring>
#define min(X,Y) ((X)<(Y)?(X):(Y))

int n,head[301],nxt[180001],b[180001],v[180001],k=1;
int vt[180001],flow[301],q[100001],h,t,S,T,pre[301];
double dis[301],ct[180001],bene[180001],cost[180001],a[101][101],bad[101][101],tem,l=0.0,r=100000000.0,mid;
bool inq[301];
void push(int s,int t,int val,double c){
    nxt[++k]=head[s];
    head[s]=k;
    b[k]=t;
    v[k]=val;
    cost[k]=c;
}
void link(int s,int t,int val,double c){
    push(s,t,val,c);
    push(t,s,0,-c);
}
bool spfa(){
    for(int i=S;i<=T;i++)dis[i]=1000000000.0;
    h=t=0;
    q[++t]=S;
    inq[S]=1;
    dis[S]=0.0;
    flow[S]=0x7f7f7f7f;
    while(h<t){
        ++h;inq[q[h]]=0;
        for(register int i=head[q[h]];i;i=nxt[i])
            if(dis[b[i]]>dis[q[h]]+cost[i]&&v[i]){
                dis[b[i]]=dis[q[h]]+cost[i];
                flow[b[i]]=min(flow[q[h]],v[i]);
                pre[b[i]]=i;
                if(!inq[b[i]])inq[b[i]]=1,q[++t]=b[i];
            }
    }
    return dis[T]!=1000000000.0;
}
bool judge(double u){
    double ans=0.0;
    memset(head,0,sizeof head);
    k=1;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++)
            link(i,j+n,1,u*bad[i][j]-a[i][j]);
        link(S,i,1,0.0);
        link(i+n,T,1,0.0);
    }
    while(spfa()){
        int tem=T;
        while(tem!=S){
            v[pre[tem]]-=flow[T];
            v[pre[tem]^1]+=flow[T];
            tem=b[pre[tem]^1];
        }
        ans+=(double)flow[T]*dis[T];
    }
    return ans<0.0;
}
int read(){
    int x=0;
    char ch=getchar();
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x;
}
int main(){
    n=read();
    T=n+n+1; 
    for(register int i=1;i<=n;i++)
        for(register int j=1;j<=n;j++)
            a[i][j]=(double)read();
    for(register int i=1;i<=n;i++)
        for(register int j=1;j<=n;j++)
            bad[i][j]=(double)read();
    while(r-l>=0.000000001){
        mid=(l+r)/2;
        if(judge(mid))l=mid;
        else r=mid;
    }
    printf("%.6lf",l);
}

评论

  • 还没有评论
作者: shadowice1984 更新时间: 2018-03-27 08:13  在Ta的博客查看    0  

不知道为什么我一吸氧就开始疯狂炸……

(总之是在没有$O_{2}$的情况下疯狂卡常过了这道题)

01分数规划

看起来这道题似乎非常的不可做

但是熟练的OIER应该一眼就可以推出做法吧

首先我们发现题目中给出的式子是这样的

最大化

$Mid=\frac{\sum a_{i,j}}{\sum b_{i,j}}$

那么我们可以认为这是一个网格图,每个格子上有一个物品,价值为$a_{i,j}$,代价为$b_{i,j}$现在要求你每一行每一列取且仅能取一个,求$Mid$最大值

如果你学习过一种叫01分数规划的东西的话,你会意识到,处理这类问题第一反应是二分答案,更准确的来讲,我们判断我们二分的答案mid是否比真实答案大,这样就可以求出这个函数的值了

让我们来试着变换下刚才的式子

$\sum a_{i,j}-\sum Midb_{i,j}=0$

也就是说如果mid=c,那么这个式子最大值会等于0

如果mid>c这个式子最大值会小于0

如果mid<c这个式子最大值会大于0

然后我们就可以就此二分答案了

唯一要解决的问题是,在给定mid的前提下如何求出刚才那个式子的最大值

显然我们可以把一个格子的权值变成$a_{i,j}-Midb_{i,j}$现在唯一要考虑的问题就是如何满足每一行每一列取且仅能取一个的前提下做到最优

这里我们需要使用网络流描述一个互斥的关系,如果你足够熟练的话应该可以很快反应过来这是行列拆点

具体来讲我们把每一行和每一列看作点,每一个点看作行列间的一条边,那么我们如果从源点向所有行点连一条容量为1的边,所有列点向汇点连一条容量为1的边,那么我们会发现这样可以满足每个行列都只选一次的限制条件

剩下的事情就是把每个点作为一个容量为1的点连入,然后点权作为边权跑费用流就好了

(不就是二分图最大带权匹配吗……会的话不需要我多说吧)

卡常数

本题唯一的难点在于丧心病狂的$10^{-6}$精度要求,因此我们的二分次数将不可避免的多

具体来讲卡常数的办法就是去掉你程序里的全部结构题再手写一个队列,依靠信仰可以通过卡常来通过本题

上代码~

#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;const int N=110;typedef double db;db eps=1e-8;int n;
int v[4*N*N];int x[4*N*N];int c[4*N*N];db val[4*N*N];
int al[2*N];int ct=1;int rst[4*N*N];//去掉了所有的结构体,大家凑合着看吧 
inline void add(int p,int y)
{
    v[++ct]=y;x[ct]=al[p],c[ct]=1;al[p]=ct;rst[ct]=1;
    v[++ct]=p;x[ct]=al[y];c[ct]=0;al[y]=ct;rst[ct]=0;
}db cost;db d[2*N];int s;int t;int ctt;int q[4000010];int hd=1;int til;
int fr[2*N];int nu[2*N];bool book[2*N];
inline bool spfa()
{
    for(int i=1;i<=ctt;i++){d[i]=-0x3f3f3f3f;}d[s]=0;
    for(q[++til]=s;hd<=til;++hd)//这里手写了队列…… 
    {
        for(int w=q[hd],i=al[w];i;i=x[i])//spfa不说了 
        {
            if(d[v[i]]<d[w]+val[i]&&c[i]!=0)
            {
                fr[v[i]]=w;nu[v[i]]=i;d[v[i]]=d[w]+val[i];
                if(!book[v[i]]){q[++til]=v[i];book[v[i]]=true;}
            }
        }book[q[hd]]=false;
    }hd=1;til=0;//记得手动清空 
    if(d[t]==-0x3f3f3f3f){return false;}//这里为了省常数直接+1-1因为边权只有1和0 
    for(int p=t;p!=s;p=fr[p]){c[nu[p]]-=1;c[nu[p]^1]+=1;}
    cost+=d[t];return true;
}db a[N][N];db b[N][N];int tr[N][N];
inline void rebuild(db mid)//这里维护了一个点到边的映射 
{
    for(int i=1;i<=ct;i++){c[i]=rst[i];}
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)//重新设置下边权 
        {
            val[tr[i][j]]=a[i][j]-b[i][j]*mid;
            val[tr[i][j]^1]=-val[tr[i][j]];
        }
    }cost=0;
}
int main()
{
    scanf("%d",&n);ctt=2*n;s=++ctt;t=++ctt;
    for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){scanf("%lf",&a[i][j]);}}
    for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){scanf("%lf",&b[i][j]);}}
    for(int i=1;i<=n;i++){add(s,i);add(n+i,t);}//加边 
    for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){add(i,n+j);tr[i][j]=ct-1;}}
    db l=0;db r=1e4;
    while(r-l>eps)//二分答案 
    {
        db mid=(l+r)/2;rebuild(mid);
        while(spfa());if(cost<0){r=mid;}else {l=mid;}
    }printf("%.6lf",l);return 0;//拜拜程序~ 
}