zoj 2676 Network Wars 0-1分数规划+最小割

题目详解出自论文 Amber-最小割模型在信息学竞赛中的应用

题目大意: 给出一个带权无向图 G = (V,E), 每条边 e属于E都有一个权值We，求一个割边集C,使得该割边集的平均边权最小，即最小化：

将等式转换,引入x向量，Xi取值为(0,1),得到0-1分数规划常规式:

将其转换得到一个关于的一个函数：

其中为单调递减函数, 当且仅当 = 0 , 为最优值.

然后我们可以二分枚举最优值 , 然后判定当前最优值是否符合要求.

判定思路: 对于每一条边权Wi 变换成了新的边权 , 而向量X(x1,x2,..,xm)表示对应边取或者不取，所以根据其取与不取划分成一个ST集。

令取为1,则函数就转换成了最小割的容量了（即最大流）。

有个要注意的地方，一个是枚举的最优值是一个浮点数，还有就是当 < 0 时，必定是取得，因为它能使最优值尽可能小。

最终结果可以得出最优值后，然后在跑一次最大流，然后从源点S开始DFS标记所有可以访问到的顶点，然后求出所有取得边。注意

< 0 的边要特殊处理。因为是负值放进去计算不太方便。

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<vector>

using namespace std;

const int inf = 0x3f3f3f3f;

const int MAXN = ;

const double esp = 1e-;

int sign(double x){ return x<-esp?-:(x>esp);}

int n, m, Max;

int S, N, T;

struct Edge{

    int u, v, nxt;

    double f;

}edge[];

struct Edge_Info{

    int a,b,c;

    void input(){

        scanf("%d%d%d",&a,&b,&c);

    }

}edge_info[];

bool vis[MAXN];

int h[MAXN], vh[MAXN];

int head[MAXN], idx;

void AddEdge(int a,int b,double f){

    edge[idx].u = a, edge[idx].v = b, edge[idx].f = f;

    edge[idx].nxt = head[a], head[a] = idx++;

    edge[idx].u = b, edge[idx].v = a, edge[idx].f = ;

    edge[idx].nxt = head[b], head[b] = idx++;

}

double CreateGraph(double MaxW){

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

    idx = ;

    double tmp_val = ;

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

        int a = edge_info[i].a, b = edge_info[i].b, c = edge_info[i].c;

        if( sign(c - MaxW) <  )

            tmp_val += c-MaxW;

        else AddEdge(a,b,c-MaxW),AddEdge(b,a,c-MaxW);

    }

    return tmp_val;

}

double dfs(int u,double flow){

    if(u == T) return flow;

    int tmp = h[u]+; double sum = flow;

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

        if( sign(edge[i].f) >  && (h[ edge[i].v ]+ == h[u])){

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

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

            if( sign(sum)== || h[S]==N ) return flow-sum;

        }

    }

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

        if( sign(edge[i].f) >  ) tmp = min(tmp,h[ edge[i].v ] );

    }

    if( --vh[ h[u] ] ==  ) h[S] = N;

    else ++vh[ h[u]=tmp+ ];

    return flow-sum;

}

double sap(){

    double maxflow = ;

    memset(h,,sizeof(h));

    memset(vh,,sizeof(vh));

    vh[] = N;

    while( h[S] < N ) maxflow += dfs( S,inf );

    return maxflow;

}

double Search( double l, double r ){

    while( r-l > 1e- ){

        double mid = (r+l)/2.0;

        double maxflow = CreateGraph( mid );

        maxflow += sap();

        if( sign(maxflow) <  ) r = mid;

        else l = mid;

    }

    return l;

}

void DFS(int u){

    vis[u] = true;

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

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

            DFS( edge[i].v );

    }

}

vector<int> res;

int mp[MAXN][MAXN];

void solve(){

    S = , T = n, N = n;

    double limit = Search( , Max );

    double maxflow = CreateGraph( limit );

    maxflow += sap();

    res.clear();

    memset(vis,,sizeof(vis));

    DFS(S);

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

        mp[ edge_info[i].a ][ edge_info[i].b ] = i;

        mp[ edge_info[i].b ][ edge_info[i].a ] = i;

        if( sign(edge_info[i].c-limit) <  )

            res.push_back(i);

    }

    for(int i = ; i < idx; i +=  ){ //

        int u = edge[i].u, v = edge[i].v;

        if( vis[u] && !vis[v] && sign( edge[i].f ) ==  ){ //

            res.push_back(  mp[u][v] );

        }

    }

    sort( res.begin(), res.end() );

    int num = res.size();

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

    for(int i = ; i < num; i++)

        printf( i==? "%d":" %d", res[i] );

    printf("\n");

}

int main(){

    int Case = ;

    while( scanf("%d%d",&n,&m) != EOF) {

        Max = ;

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

            edge_info[i].input();

            Max = max( Max, edge_info[i].c );

        }

        solve();

        if( Case++ >  ) puts("");

    }

    return ;

}

巴特西

zoj 2676 Network Wars 0-1分数规划+最小割

最新文章

热门文章