ZOJ 2676 Network Wars(网络流+分数规划)

传送门

题意：求无向图割集中平均边权最小的集合。

论文《最小割模型在信息学竞赛中的应用》原题。

分数规划。每一条边取上的代价为1。

#include <bits/stdc++.h>

using namespace std;

inline int read() {

    int x = , f = ; char ch = getchar();

    while (ch < '' || ch > '') { if (ch == '-') f = -; ch = getchar(); }

    while (ch >= '' && ch <= '') { x = x *  + ch - ; ch = getchar(); }

    return x * f;

}

const int N = 1e5 + ;

const double EPS = 1e-;

struct Edge { int v, next; double f; } edge[N];

int n, m, head[N], cnt, level[N], iter[N], x[N], y[N];

double z[N];

bool vis[N];

inline void add(int u, int v, double f) {

    edge[cnt].v = v; edge[cnt].f = f; edge[cnt].next = head[u]; head[u] = cnt++;

    edge[cnt].v = u; edge[cnt].f = f; edge[cnt].next = head[v]; head[v] = cnt++;

}

bool bfs() {

    for (int i = ; i <= n; i++) iter[i] = head[i], level[i] = -, vis[i] = ;

    queue<int> que;

    que.push();

    level[] = ;

    while (!que.empty()) {

        int u = que.front(); que.pop();

        for (int i = head[u]; ~i; i = edge[i].next) {

            int v = edge[i].v; double f = edge[i].f;

            if (level[v] <  && f) {

                level[v] = level[u] + ;

                que.push(v);

            }

        }

    }

    return level[n] != -;

}

double dfs(int u, double f) {

    if (u == n) return f;

    double flow = ;

    for (int i = iter[u]; ~i; i = edge[i].next) {

        iter[u] = i;

        int v = edge[i].v;

        if (level[v] == level[u] +  && edge[i].f) {

            double w = dfs(v, min(f, edge[i].f));

            //if (fabs(w) < EPS) continue;

            f -= w;

            flow += w;

            edge[i].f -= w, edge[i^].f += w;

            if (f <= ) break;

        }

    }

    return flow;

}

double dinic() {

    double ans = ;

    while (bfs()) ans += dfs(, 1e8);

    return ans;

}

bool check(double mid) {

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

    cnt = ;

    double flow = ;

    for (int i = ; i <= m; i++) {

        if (z[i] > mid) add(x[i], y[i], z[i] - mid);

        else flow += z[i] - mid;

    }

    flow += dinic();

    return flow >= EPS;

}

void get_ans(int u) {

    vis[u] = ;

    for (int i = head[u]; ~i; i = edge[i].next) {

        int v = edge[i].v;

        if (!vis[v] && edge[i].f > EPS) {

            get_ans(v);

        }

    }

}

int ans[N], tol;

int main() {

    int kase = ;

    while (~scanf("%d%d", &n, &m)) {

        if (kase > ) puts("");

        kase = ;

        for (int i = ; i <= m; i++) {

            x[i] = read();y[i] = read();

            int a = read();z[i] = (double)a;

        }

        double l = , r = 1e7;

        while (r - l > EPS) {

            double mid = (l + r) / 2.0;

            if (check(mid)) l = mid;

            else r = mid;

        }

        check(r);

        get_ans();

        tol = ;

        for (int i = ; i <= m; i++) {

            if (vis[x[i]] + vis[y[i]] ==  || z[i] <= r) {

                ans[++tol] = i;

            }

        }

        printf("%d\n", tol);

        for (int i = ; i <= tol; i++) {

            if (i - ) putchar(' ');

            printf("%d", ans[i]);

        }

        puts("");

    }

    return ;

}