题目概述

有 $n$ 个神犇JZ，某两个JZ配合有神犇值，共有 $m$ 组这样的JZ。现在要选出若干个JZ（假设选了 $k$ 个），贡献为存在于这些JZ中的所有配合的神犇值之和除以 $k(2n-k)$ ，求最大贡献。

解题报告

显然是最大密度子图啊？但是我太naive了，一直在想怎么把 $k(2n-k)$ 放进点权里，实际上应该放到边权里……先二分，然后推一推：

$$ {\sum w_{i,j}\over k(2n-k)}\ge mid\\ \sum w_{i,j}-k(2n-k)mid\ge 0\\ \sum w_{i,j}-2nkmid+k^2mid\ge 0\\ \sum w_{i,j}-2nkmid+kmid+{k(k-1)\over 2}2mid\ge 0\\ \sum(w_{i,j}+2mid)-(2n-1)kmid\ge 0 $$

再就很明显了……新边权为 $w_{i,j}+2mid$ ，新点权为 $(2n-1)mid$ ，刷最大密度子图就行了。

示例程序

精度坑死人！！！我恨分数规划！！！

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define fr first
#define sc second
#define mp make_pair
using namespace std;
typedef long double DB;
const int maxn=400,maxm=maxn*maxn,maxe=maxm+maxn<<2;

int n,m,w[maxn+5][maxn+5];bool chs[maxn+5];
int E,lnk[maxn+5],cur[maxn+5],son[maxe+5],nxt[maxe+5];
DB D[maxn+5];pair<DB,DB> e[maxe+5];
int que[maxn+5],dis[maxn+5],ti,vis[maxn+5];

inline int fcmp(DB a,DB b) {if (fabs(a-b)<1e-10) return 0;if (a<b) return -1;return 1;}
inline void Add(int x,int y,DB z){
    son[E]=y;e[E]=mp(0,z);nxt[E]=lnk[x];lnk[x]=E++;
    son[E]=x;e[E]=mp(0,0);nxt[E]=lnk[y];lnk[y]=E++;
}
inline bool Bfs(int s,int t){
    int Head=0,Tail=0;que[++Tail]=s;vis[s]=++ti;dis[s]=0;
    while (Head!=Tail)
        for (int x=que[++Head],j=lnk[x],u;~j;j=nxt[j])
            if (vis[u=son[j]]<ti&&fcmp(e[j].fr,e[j].sc)<0) que[++Tail]=u,vis[u]=ti,dis[u]=dis[x]+1;
    return vis[t]==ti;
}
DB Dfs(int x,int t,DB MIN=1e18){
    if (x==t||!fcmp(MIN,0)) return MIN;DB now,f=0;
    for (int &j=cur[x];~j;j=nxt[j])
        if (dis[x]+1==dis[son[j]]&&fcmp(now=Dfs(son[j],t,min(MIN,e[j].sc-e[j].fr)),0)){
            e[j].fr+=now;e[j^1].fr-=now;f+=now;
            if (!fcmp(MIN-=now,0)) break;
        }
    return f;
}
inline bool check(DB mid){
    DB U=n*(2*mid+100);E=0;memset(lnk,255,sizeof(lnk));memset(D,0,sizeof(D));
    for (int i=1;i<n;i++)
        for (int j=i+1;j<=n;j++){
            Add(i,j,w[i][j]+2*mid);Add(j,i,w[i][j]+2*mid);
            D[i]+=w[i][j]+2*mid;D[j]+=w[i][j]+2*mid;
        }
    for (int i=1;i<=n;i++) Add(0,i,chs[i]?1e18:U),Add(i,n+1,U+2*mid*(2*n-1)-D[i]);
    DB MAX=0;while (Bfs(0,n+1)) memcpy(cur,lnk,sizeof(lnk)),MAX+=Dfs(0,n+1);
    return fcmp(U*n,MAX)>0;
}
int main(){
    freopen("program.in","r",stdin);
    freopen("program.out","w",stdout);
    scanf("%d%d",&n,&m);
    for (int i=1,x,y,z;i<=m;i++) scanf("%d%d%d",&x,&y,&z),w[x][y]=w[y][x]=z;
    for (int i=1,x;i<=n;i++) scanf("%d",&x),chs[i]=x;
    DB L=0,R=m*100,mid;while (fcmp(R-L,1e-8)>0) check(mid=(L+R)/2)?L=mid:R=mid;
    return printf("%.6f\n",(double)L),0;
}