点边都带权的最大密度子图,且会有必须选的点.

求\(\frac{\sum w_e}{k*(2n-k)}\)的最大值,其中k为子图点数

设$$h(g) = \sum w_e - g*(2nk-k^2)$$

假设最优解为\(g*\),则当\(g<g*\)时,\(h(g)>0\);\(g>g*时,h(g)<0\),以此判断条件二分搜索.

但是\((2nk-k^2)\)不能直接转化为点权,需要做点改变.

这个式子的意义等于对原图的每一条边都加上了边权2g,若原图两点间没有边,则新建一条权值为2g的边. 每个点的点权为\((2ng-g)\)

这样就转化成了点边均带权的最大密度子图模型.

还有一些必须要选的点.因为在最大权闭合子图的模型中,若源点S与点i之间的边不是割,则表示没有选择这个点.根据这个性质,我们在建图的时候对必须选的点,只从源点S向它建边,容量为正无穷,保证它不会成为割中的边.然后在总的流量中加上这个点的点权.

第二十组数据特别卡精度,但是eps设得过高会T.

#include<bits/stdc++.h>

using namespace std;

const double eps = 1e-7;

const int INF = 0x3f3f3f3f;

const int MAXN= 405;//点数的最大值

const int MAXM= 1e6 + 10;//边数的最大值

#define captype double

struct Edge{

    int from,to,next;

    captype cap;

};

struct SAP_MaxFlow{

    Edge edges[MAXM];

    int tot,head[MAXN];

    int gap[MAXN];

    int dis[MAXN];

    int cur[MAXN];

    int pre[MAXN];

    void init(){

        tot=0;

        memset(head,-1,sizeof(head));

    }

    void AddEdge(int u,int v,captype c,captype rc=0){

        edges[tot] = (Edge){u,v,head[u],c};  head[u]=tot++;

        edges[tot] = (Edge){v,u,head[v],rc}; head[v]=tot++;

    }

    captype maxFlow_sap(int sNode,int eNode, int n){//n是包括源点和汇点的总点个数，这个一定要注意

        memset(gap,0,sizeof(gap));

        memset(dis,0,sizeof(dis));

        memcpy(cur,head,sizeof(head));

        pre[sNode] = -1;

        gap[0]=n;

        captype ans=0;

        int u=sNode;

        while(dis[sNode]<n){

            if(u==eNode){

                captype Min=INF ;

                int inser;

                for(int i=pre[u]; i!=-1; i=pre[edges[i^1].to])

                if(Min>edges[i].cap){

                    Min=edges[i].cap;

                    inser=i;

                }

                for(int i=pre[u]; i!=-1; i=pre[edges[i^1].to]){

                    edges[i].cap-=Min;

                    edges[i^1].cap+=Min;

                }

                ans+=Min;

                u=edges[inser^1].to;

                continue;

            }

            bool flag = false;

            int v;

            for(int i=cur[u]; i!=-1; i=edges[i].next){

                v=edges[i].to;

                if(edges[i].cap>0 && dis[u]==dis[v]+1){

                    flag=true;

                    cur[u]=pre[v]=i;

                    break;

                }

            }

            if(flag){

                u=v;

                continue;

            }

            int Mind= n;

            for(int i=head[u]; i!=-1; i=edges[i].next)

            if(edges[i].cap>0 && Mind>dis[edges[i].to]){

                Mind=dis[edges[i].to];

                cur[u]=i;

            }

            gap[dis[u]]--;

            if(gap[dis[u]]==0) return ans;

            dis[u]=Mind+1;

            gap[dis[u]]++;

            if(u!=sNode)  u=edges[pre[u]^1].to;  //退一条边

        }

        return ans;

    }

}F;

int N, M ;

double d[MAXN];

int tag[MAXN];

int G[405][405];

#define U (400 * 2100)

bool check(double g)

{

    int s = 0, t = N+1;

    F.init();

    double flow = 0;

    for(int i=1;i<=N;++i){

        d[i] = 0.0;

        for(int j=1;j<=N;++j){

            if(i==j) continue;

            d[i] += 2*g + G[i][j];

            F.AddEdge(i,j,G[i][j] + 2*g);

        }

    }

    for(int i=1;i<=N;++i){

        if(tag[i]){

            flow += U + 2*g*(2*N-1) - d[i];

            F.AddEdge(s, i, INF);

        }

        else{

            F.AddEdge(s,i,U);

            F.AddEdge(i,t, U + 2 * g * (2*N - 1) - d[i]);

        }

    }

    double hg = (U*N - flow - F.maxFlow_sap(s,t,t+1)) * 0.5;

    return hg > eps;

}

int main()

{

    #ifndef ONLINE_JUDGE

        freopen("in.txt", "r", stdin);

        freopen("out.txt", "w", stdout);

    #endif

    int u,v,w;

    scanf("%d %d",&N, &M);

    for(int i=1;i<=M;++i){

        scanf("%d %d %d",&u, &v, &w);

        G[u][v] = G[v][u] = w;

    }

    for(int i=1;i<=N;++i){

        scanf("%d",&tag[i]);

    }

    double L = 0, R = 200, mid;

    while(R - L >= eps){

        mid = (L+R) * 0.5;

        if(check(mid)) L = mid;

        else R = mid;

    }

    printf("%.6f\n",(L+R)*0.5);

    return 0;

}