P3705 [SDOI2017]新生舞会 题解


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

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

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

评论

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

由于题目求的是最优配对方案,所以很容易想到建一个二分图后用费用流求解,即建立源点和汇点,由源点向每个男生连一条容量为$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;
}

评论

  • 还没有评论
作者: nianheng 更新时间: 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;
}

评论

  • 还没有评论
作者: Venus 更新时间: 2019-01-25 13:31  在Ta的博客查看    0  

二分图最佳匹配 + 分数规划。读题,发现要求最优配对,很显然,这个图是一张二分图,那么最佳匹配我们可以用 $\text{KM}$ 或者 费用流 来求出,这里不赘述如何求出最佳匹配。我们来考虑怎么计算这个 $C=\frac{\sum_{i=1}^{k}a'[i]}{\sum_{i=1}^{k}b'[i]}$。显然,这里的 $\sum_{i=1}^{k}b'[i]$ 是非常不好处理的,所以我们要引入分数规划的思想,将这个式子转化成 $\sum_{}^{}a'-C\sum_{}^{}b'=0$,然后二分答案 $C$,每次 $\text{Check}$ 都跑一遍最佳匹配,边权就设成 $a[i][j]-mid\times b[i][j]$,然后跑最大权最佳匹配(也就是最大费用最大流),判断最后得到的权和是否为 $0$ 即可。

同步发表于笔者的博客:题解 P3705 [SDOI2017]新生舞会

代码选用 $\text{zkw}$ 费用流。

#include<bits/stdc++.h>
#define MAXN 1005
#define inf 1010580540
#define eps 1e-8
using namespace std;
deque <int> q;
int cnt,fst[MAXN],nxt[MAXN<<5],to[MAXN<<5],w[MAXN<<5],cur[MAXN];
int n,m,S,T,maxflow;
double dis[MAXN],a[MAXN][MAXN],b[MAXN][MAXN],cot[MAXN<<5],mincost;
bool inq[MAXN],vis[MAXN];
void AddEdge(int u,int v,int c,double fl)
{
    to[++cnt]=v;
    nxt[cnt]=fst[u];
    fst[u]=cnt;
    w[cnt]=c;
    cot[cnt]=fl;
}
bool Spfa()
{
    for(int i=S;i<=T;i++) dis[i]=inf;
    memset(inq,0,sizeof(inq));
    q.push_front(T);
    dis[T]=0;
    inq[T]=1;
    while(!q.empty())
    {
        int u=q.front();
        q.pop_front();
        inq[u]=0;
        for(int i=fst[u];i;i=nxt[i])
        {
            int v=to[i];
            if(dis[v]>dis[u]-cot[i] && w[i^1])
            {
                dis[v]=dis[u]-cot[i];
                if(!inq[v])
                {
                    if(!q.empty() && dis[v]<dis[q.front()]) q.push_front(v);
                    else q.push_back(v);
                    inq[v]=1;
                }
            }
        }
    }
    return dis[S]!=inf;
}
int Dfs(int u,int flow)
{
    vis[u]=1;
    if(u==T || !flow) return flow;
    int used=0;
    for(int &i=cur[u];i;i=nxt[i])
    {
        int v=to[i];
        if(dis[v]==dis[u]-cot[i] && w[i] && !vis[v])
        {
            int fl=Dfs(v,min(flow,w[i]));
            if(fl)
            {
                used+=fl;
                flow-=fl;
                w[i]-=fl;
                w[i^1]+=fl;
                if(!flow) break;
            }
        }
    }
    return used;
}
void zkwMCMF()
{
    while(Spfa())
    {
        vis[T]=1;
        while(vis[T])
        {
            memset(vis,0,sizeof(vis));
            memcpy(cur,fst,sizeof(fst));
            int fl=Dfs(S,inf);
            maxflow+=fl;
            mincost+=dis[S]*fl;
        }
    }
    mincost=-mincost;
}
bool Check(double mid)
{
    maxflow=mincost=0;
    cnt=1;
    memset(fst,0,sizeof(fst));
    for(int i=1;i<=n;i++)
    {
        AddEdge(S,i,1,0);
        AddEdge(i,S,0,0);
    }
    for(int i=n+1;i<=n*2;i++)
    {
        AddEdge(i,T,1,0);
        AddEdge(T,i,0,0);
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            AddEdge(i,j+n,1,-a[i][j]+b[i][j]*mid);
            AddEdge(j+n,i,0,a[i][j]-b[i][j]*mid);
        }
    }
    zkwMCMF();
    return fabs(mincost)<=eps || mincost>eps;
}
int main()
{
    scanf("%d",&n);
    S=0;
    T=n*2+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.0;
        if(Check(mid)) l=mid;
        else r=mid;
    }
    printf("%.6lf\n",r);
    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);
}