P10757 [WC2011] 关系挖掘 题解

xieziheng · 2024-08-15 21:40:17 · 题解

好像是洛谷首 A，虽然不知道其他地方能不能交。

提答题真好玩！

发现题目就是让我们求图的 k 个点的导出子图使得边权和最大，这显然是个 NPC 问题。

看一下每个测试点。

1. 测试点 1

发现 n=20，所以直接状压暴力求出来就行了。

2. 测试点 2,3,4

对于测试点 5，发现图是一个二分图，左边有 20 个点，右边有 1500 个点，边数 15000。

考虑直接暴力枚举左边选了哪些点，设左边选的点集为 S，对于右边的点 x，按 a_x=\sum_{y\in S,(y,x,w)\in E} w 从大到小排序找到前 k-|S| 大即可。设左边部分点集大小为 l 复杂度 \mathcal{O}(2^l(m+n\log n))

不过这样毛估估一下可能跑的时间有点长，可以有几个优化：

• 状压枚举集合 S 时时刻更新 a 这样由于位的变化均摊是 \mathcal{O}(1) 的所以可以把 m 变成 n。

• 由于只需要找至多前 k 大，而 k=37，可以快排或者归并排序，复杂度 \mathcal{O}(n\log k)。

这样用我的破笔记本两分钟就可以跑完第五个点。

对于测试点 6，发现好像没啥规律。不过依据测试点 5 的规律，我们猜测图的性质是一样的，把所有点按度数排个序重新标一个号就一样了。用上述做法我跑了 10 分钟多一点。

4. 测试点 7,8

暴力在这里就不完全可以了，开始乱搞。

我们发现图很稠密，且边权都是 1。

直接模拟退火应该也有不少分，不过应该没法满分。

观察一下满分的条件，发现 ans=\frac {k(k-1)}2 也就是说是求一个大小为 k 的团。

方便起见，我取了原图的补图，转化为求一个大小为 k 的独立集。那我们只需要求出最大独立集就好了

众所周知，求最大独立集有一个非常简单的随机化方法：

每次随机一个排列，然后按顺序贪心选出一个独立集然后取最大的那个。

不过这里可能过不去。至少第八个点应该不太行。

先做第七个点。

继续观察补图，发现 m 只比 n 大一点点，难道还要广义串并联图？其实不是。把补图划分为若干个连通块，发现有 23 个大小为 1 的，4 个大小为 2 的和 1 个大小为 169 的，由于是独立集，我们一定是取了所有单点和两个点中的恰好一个以及大连通块里的一个独立集。

对大一点的图运行上述算法几分钟就可以跑出一个解。

但是对于第八个点，这个做法就失败了，原因是 n=500,k=317 实在有点大。我跑了二十分钟都不行。

我们考虑如何优化：直观上感觉，最大独立集中的点的度数应该都比较小，设点 x 度数为 d_x。于是每次随机化我们给第 x 个点随机一个在 [l,r] 中的权值 v_x，并按照 d_xv_x 从小到大排序。

取 l=1000,r=3000 就可以在三十秒内得到一组解（好像有一次我三秒就跑出来了），感觉还是非常快的！！！

5. 测试点 9,10

注意力最集中的一集。

我们仔细观察这个图，发现这个图没有任何特殊性质。。。

这时候我们不禁怀疑：难道这个题前面的点都是与 《正解》 关系不大的部分分？这道题竟然存在不依赖随机的多项式做法？？？

当然，这是不可能的。

考虑这个问题的形式，其实是和几道可做题很像的。

例如：

• CF1082G Petya and Graph：定义一个图的权值为其边权和减去点权和，求一个图权值最大的生成子图。做法：对点和边建图，跑最小割。

• UVA1389 Hard Life：定义一个图的密度为其边数除以点数，求一个图密度最大的生成子图。做法：二分密度，转化为可行性问题，套用上题做法即可。

这个题多出的限制就是 k。

注意到

我们不妨大胆的假设：题目给出的 k 就是第二题中带边权密度最大的子图的大小。

事实上，这就是对的。感觉这个真的只能注意到。。。

于是和第二题用类似的方法做就行。但是注意精度问题。

给个这两个点的代码：

#pragma GCC optimize("O2,O3,Ofast,inline,unroll-loops")
#pragma GCC target("avx2,sse4")
#include <bits/stdc++.h>
#define il inline
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
typedef long long ll;
il long double ab(long double x){return x>=0.0?x:-x;}
const int N=1e5+5,oo=1e9;const long double inf=1e18,eps=1e-15,EPS=1e-9;
int n,m,k,deg[N];ll sum,ans,val[1005][1005];
struct edge{
    int u,v,w;
    il edge(){u=v=w=0;}
    il edge(int u,int v,int w) : u(u),v(v),w(w) {}
}g[N];
int s,t,head[N],cur[N],dis[N],tot=1,q[N],hh,tt;
struct node{
    int to,nxt;long double v;
    il node(){to=nxt=0,v=0;}
}e[N<<2];
il void add(int x,int y,long double z){e[++tot].to=y,e[tot].nxt=head[x],e[tot].v=z,head[x]=tot;}
il void adde(int x,int y,long double z){add(x,y,z),add(y,x,0);}
il int bfs(){
    int x,y,z;for(int i=0;i<=t;++i) dis[i]=oo;
    dis[s]=0,cur[s]=head[s],hh=1,tt=0,q[++tt]=s;
    while(hh<=tt){
        x=q[hh++];if(x==t) return 1;
        for(int i=head[x];i;i=e[i].nxt){
            y=e[i].to;
            if(e[i].v>eps && dis[y]==oo) dis[y]=dis[x]+1,cur[y]=head[y],q[++tt]=y;
        }
    }return 0;
}
long double dfs(int x,long double sum){
    if(x==t) return sum;
    int y;long double z,ret=0;
    for(int i=cur[x];i && sum>eps;i=e[i].nxt){
        y=e[i].to,cur[x]=i;
        if(dis[y]==dis[x]+1 && e[i].v>eps){
            z=dfs(y,min(sum,e[i].v));if(z<=eps) dis[y]=oo;
            e[i].v-=z,e[i^1].v+=z,sum-=z,ret+=z;
        }
    }return ret;
}
il void init(){
    for(int i=0;i<=tot;++i) e[i].to=e[i].nxt=0,e[i].v=-inf;
    for(int i=0;i<=n+m+2;++i) head[i]=cur[i]=dis[i]=q[i]=0;s=t=tot=hh=tt=0;
}
il long double ck(long double mid){
    int x,y,z;long double u,v,w,ret=0;init();
    s=n+1,t=n+2,tot=1;

    for(int i=1;i<=m;++i){
        x=g[i].u,y=g[i].v,z=g[i].w;
        adde(x,y,z),adde(y,x,z);
    }
    for(int i=1;i<=n;++i) adde(s,i,sum),adde(i,t,sum+2.00*mid-deg[i]);
    while(bfs()) ret+=dfs(s,inf);
    return ret;
}
int dfn[N],low[N],cnt,st[N],top,bel[N],idx,vis[N];
void tarjan(int x){
    int y,z;dfn[x]=low[x]=++cnt,st[++top]=x,vis[x]=1;
    for(int i=head[x];i;i=e[i].nxt){
        y=e[i].to;if(e[i].v<eps) continue;
        if(!dfn[y]) tarjan(y),low[x]=min(low[x],low[y]);
        else if(vis[y]) low[x]=min(low[x],dfn[y]);
    }
    if(dfn[x]==low[x]){
        ++idx;
        do{
            y=st[top--],bel[y]=idx,vis[y]=0;
        }while(y!=x);
    }
}
int use[N],cc;
void dfs0(int x){
    use[x]=1;if(x!=s) ++cc;int y;
    for(int i=head[x];i;i=e[i].nxt){
        y=e[i].to;
        if(!use[y] && e[i].v>0) dfs0(y);
    }
}
int x,y,z,a[N],len;long double u,v,w,l,r,mid,ret;
int main(){
    freopen("relation10.in","r",stdin);
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=m;++i){
        scanf("%d%d%d",&x,&y,&z),sum+=1ll*z,g[i]={x,y,z};
        val[x][y]=val[y][x]=1ll*z;
        deg[x]+=z,deg[y]+=z;
    }
    l=0,r=1.00*sum;
    while(r-l>EPS){
        mid=(l+r)/2.00;;
        if(1.00*sum*n-ck(mid)>1e-5) ret=mid,l=mid;
        else r=mid;
    }
    w=ck(ret);
    ans=ll(ret*k);printf("%lld\n",ans);
    dfs0(s);
    len=0;for(int i=1;i<=n;++i) if(use[i]) a[++len]=i;printf("%d\n",len);
    for(int i=1;i<=len;++i) printf("%d\n",a[i]);
    return 0;
}