[GDKOI2016]寻宝 题解

01 分数规划+最大权闭合子图

教练居然告诉我说这两个我都学过，我咋不知道我学过/wq

所以这里顺带学一手/kk

Statement

[GDKOI2016]寻宝 - 题目(fzoi.top)

Solution

题目可以进行这样的转化：

给定一个有向图，每个点有权值 \(a_i,b_i\) ，要求选出一个闭合子图 \(S\)，使得 \(S\) 中 \(\dfrac{\sum b_i}{\sum a_i}\) 最小化（之前一直读成了最大化qwq）

闭合图一般指一个图中点集，从该集合中所有的点出发，能到达的点要求都必须在该点集中。也就是说，从该集合中出发，一定要回到该集合中，不能出到集合外

看到这个分式，容易想到 \(0/1\) 分数规划，

01 分数规划

一般的，问题被描述为构造一个 \(x_i\in\{0,1\}\) ，使得 \(\dfrac{\sum x_ib_i}{\sum x_ia_i}\) 最大/小化

我们给出的方法是二分一个答案 \(ans\) ，以最小化为例，判断实际答案是否可以 \(\le ans\)

即是否存在一个 \(x_i\) ，使得 \(\sum x_ib_i\le \sum x_ia_ians\)

即 \(\sum x_i(a_ians-b_i)\ge0\) ，如若可以，那么 \(r=mid\) ，否则 \(l=mid\)

这个问题的判断十分简单，把所有正的 \(a_ians-b_i\) 相加即可

01 分数规划还能解决一些奇奇怪怪的问题，长大后再学习

最大权闭合子图

容易发现原问题上一个 01 分数规划的二分答案之后，变成了给定一个有向图，每个点有点权 \(a_ians- b_i\) ，求解最大权闭合子图

所以这某种意义上是一个二合一题哈哈

这个问题我们可以使用网络流解决：新建立一个网络流图，如若点权为正，连边 \((s,i,v)\) ；点权为负 连边，\((i,t,-v)\)；对于原图中本来就有的边，连边 \((u,v,inf)\)

然后你发现再这个上面跑一个最小割，设 \(cut=\) 最小割，\(sum=\) 正点权之和（从 \(s\) 出发的边的流量之和），那么最大权值就是 \(sum-cut\)

咋理解。显然，\(inf\) 边不可能割，只可能割掉与 \(s/t\) 有关的边

首先可能需要画图理解一下为什么不是直接把 \(s/t\) 割成一个独立的点（完全不会最大流）

然后，从感性的角度理解这个结论，我们为了选择一些正边（从 \(s\) 出发的边），我们不得不选择一些负边（到 \(t\) 的边），具体是那些负边需要选择呢？选择割集中的所有负边就可以了（首先因为这是一个割，假如里面有边没有选到，那么 \(s,t\) 连通，意味着选出的边在原图上对应的点没有构成一个闭合子图；其次不用选其他负边了，因为为了最大化 \(sum-cut\) ，我们想要最小化 \(cut\)）。这样的话，每一种割法对应一种选择闭合子图的方式，自然最小割就是最优的啦。

理性证明可以参考：

所以这道题讲完了/hanx ，复杂度 \(O(n^2m\log n)\)

Code

#include
#define eps 1e-8
using namespace std;
const int N = 1e4+5;

// char buf[1<<23],*p1=buf,*p2=buf;
// #define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
int read(){
    int s=0,w=1; char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
    while(isdigit(ch))s=s*10+(ch^48),ch=getchar();
    return s*w;
}

struct Edg{
    int nex,to;
    double flow;
}edge[N<<1];
int head[N],cur[N];
vectorEdge[N];
int w[N],d[N],dep[N];
int n,fg,elen,s,t;
queueq;

void addedge(int u,int v,double w){
    edge[++elen]=(Edg){head[u],v,w},head[u]=elen;
    edge[++elen]=(Edg){head[v],u,0},head[v]=elen;//负边流量 0
}
bool bfs(){
    memset(dep,-1,sizeof(dep));
    q.push(s),dep[s]=0;
    while(q.size()){
        int u=q.front(); q.pop();
        for(int e=head[u],v;v=edge[e].to,e;e=edge[e].nex)
            if(dep[v]==-1&&edge[e].flow-eps>0)dep[v]=dep[u]+1,q.push(v);
    }
    return dep[t]!=-1;
}
double dfs(int u,double flow){// Dinic 板子，注意在 double 背景下 >0 的判定
    if(u==t)return flow; double res=0;
    for(int &e=cur[u],v;v=edge[e].to,e;e=edge[e].nex)
        if(dep[v]==dep[u]+1&&edge[e].flow-eps>0){
            double tmp=dfs(v,min(flow,edge[e].flow));
            edge[e].flow-=tmp,flow-=tmp;
            edge[e^1].flow+=tmp,res+=tmp;
            if(flow0)sum+=v,addedge(s,i,v);
        else addedge(i,t,-v);
    }
    // puts("");
    while(bfs())
        memcpy(cur,head,sizeof(head)),
        cut+=dfs(s,1e18);
    // cout<cut;
}

signed main(){
    n=read(),s=n+1,t=n+2;
    for(int i=1,k,v;i<=n;++i){
        k=read(),fg|=(k==0);
        for(int j=1;j<=k;++j)
            v=read(),Edge[i].push_back(v);
    }
    for(int i=1;i<=n;++i)w[i]=read(),d[i]=read();
    if(!fg)return puts("CanNotFindTreasure!"),0;
    //其实这种判断无解的方式是错的，只是因为数据比较水
    //实际上应该执行拓扑排序，判断是否有可以到达的 w[i]>0
    double l=0,r=1e10,ans=-1;
    while(l+eps