学步园

ZOJ_2676

    这个题目可以像最优比率生成树那样用0-1分数规划去做，只不过最优比率生成树每次是求一棵生成树，而这个题目要求一个最小割。

    对于每次二分，在建图的时候可能会出现边权为负的边，由于通过分析后可知这些边一定会选，所以就没必要再将其加入到新建的图中了。

    最后要输出最小割集，求最小割集的时候可以用DFS遍历做完最大流之后的图，且只能沿没有满流的边向下走。遍历完成后，如果某条边有一个端点遍历到了而另外一个端点没有遍历到，那么就说明这条边是属于最小割集中的。

#include<stdio.h>
#include<string.h>
#include<algorithm>
#define zero 1e-8
#define MAXD 110
#define MAXM 1610
#define INF 0x3f3f3f3f
using namespace std;
int N, M, S, T, first[MAXD], work[MAXD], e, next[MAXM], v[MAXM], id[MAXM], use[MAXM], vis[MAXD], q[MAXD], d[MAXD];
double flow[MAXM];
struct Graph
{
    int u[MAXM], v[MAXM], w[MAXM], id[MAXM], e;
    void init()
    {
        e = 0;
    }
    void add(int x, int y, int z, int flag)
    {
        u[e] = x, v[e] = y, w[e] = z, id[e] = flag;
        ++ e;
    }
}g;
void init()
{
    int i, x, y, z;
    g.init();
    for(i = 1; i <= M; i ++)
    {
        scanf("%d%d%d", &x, &y, &z);
        g.add(x, y, z, i);
    }
}
void add(int x, int y, double f, int flag)
{
    v[e] = y, flow[e] = f, id[e] = flag;
    next[e] = first[x], first[x] = e ++;
}
double initgraph(double r)
{
    int i;
    double ans = 0;
    memset(use, 0, sizeof(use));
    memset(first, -1, sizeof(first));
    e = 0;
    for(i = 0; i < g.e; i ++)
    {
        if(g.w[i] - r <= zero)
            use[g.id[i]] = 1, ans += g.w[i] - r;
        else
        {
            add(g.u[i], g.v[i], g.w[i] - r, g.id[i]), add(g.v[i], g.u[i], 0, g.id[i]);
            add(g.v[i], g.u[i], g.w[i] - r, g.id[i]), add(g.u[i], g.v[i], 0, g.id[i]);
        }
    }
    return ans;
}
int bfs()
{
    int i, j, rear = 0;
    memset(d, -1, sizeof(d));
    d[S] = 0, q[rear ++] = S;
    for(i = 0; i < rear; i ++)
        for(j = first[q[i]]; j != -1; j = next[j])
            if(flow[j] > zero && d[v[j]] == -1)
            {
                d[v[j]] = d[q[i]] + 1;
                if(v[j] == T)
                    return 1;
                q[rear ++] = v[j];
            }
    return 0;
}
double dfs(int cur, double a)
{
    if(cur == T)
        return a;
    double t;
    for(int &i = work[cur]; i != -1; i = next[i])
        if(flow[i] > zero && d[v[i]] == d[cur] + 1)
            if((t = dfs(v[i], flow[i] < a ? flow[i] : a)) > zero)
            {
                flow[i] -= t;
                flow[i ^ 1] += t;
                return t;
            }
    return 0;
}
double dinic()
{
    double ans = 0, t;
    while(bfs())
    {
        memcpy(work, first, sizeof(first));
        while((t = dfs(S, INF)) > zero)
            ans += t;
    }
    return ans;
}
void DFS(int cur)
{
    int i;
    vis[cur] = 1;
    for(i = first[cur]; i != -1; i = next[i])
        if(flow[i] > zero && !vis[v[i]])
            DFS(v[i]);
}
void print()
{
    int i, j, n = 0, flag = 0;
    memset(vis, 0, sizeof(vis));
    DFS(S);
    for(i = 1; i < N; i ++)
        for(j = first[i]; j != -1; j = next[j])
            if((vis[i] & !vis[v[j]]) || (!vis[i] && vis[v[j]]))
                use[id[j]] = 1;
    for(i = 1; i <= M; i ++)
        if(use[i])
            ++ n;
    printf("%d\n", n);
    for(i = 1; i <= M; i ++)
        if(use[i])
        {
            flag ? printf(" ") : flag = 1;
            printf("%d", i);
        }
    printf("\n");
}
void solve()
{
    int i;
    double ans, min, max, mid;
    max = 10000010, min = 0;
    S = 1, T = N;
    for(i = 0; i < 50; i ++)
    {
        mid = (min + max) / 2;
        ans = initgraph(mid);
        ans += dinic();
        if(ans > 0)
            min = mid;
        else
            max = mid;
    }
    print();
}
int main()
{
    while(scanf("%d%d", &N, &M) == 2)
    {
        init();
        solve();
    }
    return 0;
}