Brief description :

给定一个流网络，选取一个包含割的边集E，使得边权的平均值最小。

/*
    Author  : xiaodao
    Problem : ZOJ 2676. Network Wars
    Status  : Accepted
    Last Modify : GMT +8. Sept 9th 14:48.
    Tags : 0/1分数规划，最小割
*/
#include 
#include 
#include 
#include 
#include 

using namespace std;
const double EPS = 1e-6, INF = 1e9;
const int N = 500, M = 2000;
struct edge{
    int v, c; double cc; bool used;
    void insert(int, int);
};
struct node{
    vector adj;
    int D;
};
struct network_flow{
    node V[N+1]; edge E[M+1];
    int edge_count; double max_flow, negative_edge;
    int n, m, s, t;
    void init();
    void print();
    void rebuild(double);
    void add_edge(int, int, int);
    void bfs();
    void Dinitz();
};
inline int _r(int x){
    return x ^ 1;
}
void edge::insert(int a, int b){
    v = a; c = b; used = false;
};
void network_flow::add_edge(int x, int y, int z){
    V[x].adj.push_back(edge_count); E[edge_count++].insert(y, z);
}


void network_flow::bfs(){
    int Q[N+1] = {s}, head = 0, tail = 1;
    for (int i=1;i<=n;i++) V[i].D = -1;
    V[s].D = 0;

    int u;
    while (head0){
                Q[tail] = arc.v; V[arc.v].D = V[u].D + 1;
                if (arc.v == t) return;
                tail++;
            }
        }
        head++;
    }
}

void network_flow::Dinitz(){
    max_flow = 0;

    bfs();
    while (V[t].D!=-1){
        int stack[n+1], cur[n+1], top = 0;
        memset(cur, 0, sizeof(cur));
        stack[0] = M;

        int u; size_t i;
        while (top!=-1){
            u = E[stack[top]].v;
            if (u == t){
                double delta = INF; int handle;
                for (int i=1;i<=top;i++){
                    edge &arc = E[stack[i]];
                    if (arc.cc < delta){
                        delta = arc.cc;
                        handle = i;
                    }
                }
                max_flow += delta;
                for (int i=1;i<=top;i++){
                    E[stack[i]].cc -= delta;
                    E[_r(stack[i])].cc += delta;
                }

                //for (int i=handle;i<=top;i++){
                  //  cur[stack[i]] = 0;
                //}  // ?

                top = handle-1;
                continue;
            }

            for (i=cur[u];i0) break;
            }

            if (i == V[u].adj.size()){
                V[u].D = -1, top--;
            }
            else {
                cur[u] = i + 1;
                stack[++top] = V[u].adj[i];
            }
        }
        bfs();
    }
}



void network_flow::init(){
    for (int i=1;i<=n;i++) V[i].adj.clear();
    edge_count = 0; s = 1; t = n;
    E[M].v = s;

    int x, y, z;
    for (int i=0;i=0) != (V[E[2*i+1].v].D>=0) )
            E[2*i].used = true;

    int count = 0;
    for (int i=0;i 0) l = m;
            else r = m;
        }
        G.print();
    }
}

Posted by xiaodao
Category: 日常