[POJ 3155] Hard Life 最大密度子图

传送门·Teleport!

题目大意

给定无向图,点有点权,边有边权,一条边被选中当且仅当这条边链接的两个点被选中,现在求一个联通子图让所有被选中点权值之和除以被选中边的权值之和最小。

解题报告

原谅我懒一把，这题不给样例了~

首先外面套个01分数规划的套路。。如果不很清楚安利一篇博文，写的很详细！ PerSeAwe的博文链接
二分出密度mid值，首先发现边和点有关系：如果变u-v被选中，那么点u和点v也必须被选中。把每条边抽象为一个点，然后就转化成了 最大/小权密闭子图 的问题啦！
但是这么做时间不够理想，换个思路，设V为选中子图的点集，那么点集中边权和为所有和该点集有关的边的权值和减去V和G(图的总点集)-V之间的边权。设这个值为r，那么我们最大化r就是最小化-r。如果把最大流中的s集(源点集)看做V集，这就转化成了最小割模型，为了防止出现负流量边，所有的整数需要加上一个足够大的无意义整数U。
(讲的很简略。。大家如果不能理解的话可以看看 胡伯涛《最小割模型在信息学竞赛中的应用》 ，pdf论文上的一个公式有错，ppt上没有并且个人认为易懂一点。。)

然后。。。我被卡精度了。。

一句忠言：千万记得输出答案前用最后一次二分成功值更新一下流网络！不然33wa瞬间爆炸，别问我怎么知道的！
代码！

代码

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <cmath>
using namespace std;
const double EPS = 1e-4;
const int MAXN = 110;
const int MAXM = 1100;
namespace isap {
    const int MAXD = MAXN*2;
    const int MAXE = 400000;
    struct Node {
        int v, bk, nxt;
        double w;
    } d[MAXE];
    int head[MAXD], etot;
    inline int addEdge (int a, int b, double c) {
        etot ++;
        d[etot].v = b;
        d[etot].w = c;
        d[etot].bk = etot + 1;
        d[etot].nxt = head[a];
        head[a] = etot;
        etot ++;
        d[etot].v = a;
        d[etot].w = 0;
        d[etot].bk = etot - 1;
        d[etot].nxt = head[b];
        head[b] = etot;
        //printf("isap:%d -> %d: %d\n", a, b, c);
        return etot;
    }

    int S, T, N;
    int dis[MAXD], vd[MAXD];
    int seq[MAXD+100];
    void bfs (int s) {
        int l, r;
        memset(dis, 0x3f, sizeof dis);
        dis[seq[l=r=0] = s] = 0;
        while(l<=r) {
            int u = seq[l++];
            for(int e = head[u]; e; e = d[e].nxt)
            if(dis[d[e].v] > dis[u] + 1) {
                dis[d[e].v] = dis[u] + 1;
                seq[++r] = d[e].v;
            }
        }
    }
    double dfs (int u, double val) {
        if(u == T) return val;
        double now = 0;
        for(int e = head[u]; e; e = d[e].nxt)
            if(d[e].w > 0 && dis[d[e].v]+1 == dis[u]) {
                double t = dfs(d[e].v, min(val-now, d[e].w));
                now += t;
                d[e].w -= t;
                d[d[e].bk].w += t;
                if(dis[S] >= N || now == val)
                    break;
            }
        if(now <= 0) {
            if(!(--vd[dis[u]])) {dis[S] = N; return 0;}
            dis[u] = N;
            for(int e = head[u]; e; e = d[e].nxt)
                if(d[e].w > 0)
                    dis[u] = min(dis[u], dis[d[e].v]+1);
            vd[dis[u]] ++;
            return 0;
        }
        return now;
    }

    double sap (int s, int t, int n) {
        S = s, T = t, N = n;
        memset(vd, 0, sizeof vd);
        bfs(T);
        for(int i = 1; i <= N; i++)
            if(dis[i] < N) vd[dis[i]] ++;
        double flow = 0;
        while(dis[S] < N)
            flow += dfs(S, 1e20);
        return flow;
    }
    void clear () {
        etot = 0;
        memset(head, 0, sizeof head);
    }
}
int inp[MAXM][2], rad[MAXN];
int N, M, S, T;
bool check (double mid) {
    isap :: clear();
    for(int i = 1; i<=M; i++)
        isap :: addEdge(inp[i][0], inp[i][1], 1),
        isap :: addEdge(inp[i][1], inp[i][0], 1);
    int U = 2*M+1;
    for(int i = 1; i<=N; i++) {
        isap :: addEdge(S, i, U);
        isap :: addEdge(i, T, U-rad[i]+2.0*mid);
    }
    double ans = (U*N-isap::sap(S, T, T))/2.0;
    return ans > EPS;
}

int cnt = 0;
bool vis[MAXN];
void dfs (int u) {
    if(vis[u]) return ;
    vis[u] = true; cnt ++;
    for(int e = isap :: head[u]; e; e = isap :: d[e].nxt)
        if(isap :: d[e].w > 0)
            dfs(isap :: d[e].v);
}

int main () {
    scanf("%d%d", &N, &M);
    if(M == 0) {
        printf("1\n1\n");
        return 0;
    }
    S = N+1, T = N+2;
    for(int i = 1; i<=M; i++)
        scanf("%d%d", &inp[i][0], &inp[i][1]),
        rad[inp[i][0]] ++, rad[inp[i][1]] ++;
    double l = 0, r = 1.0*M;
    while(r-l > EPS) {
        double mid = (l+r)/2.0;
        if(check(mid)) l = mid;
        else r = mid;
    }
    check(l); // ************************************非常重要！************************************
    dfs(S);
    printf("%d\n", cnt-1);
    for(int i=1; i<=N; i++)
        if(vis[i])
            printf("%d\n", i);

    return 0;
}