POJ 3308 最小割 - c++编程基础

TOP

POJ 3308 最小割

2014-11-23 21:42:23 来源: 作者: 【大中小】浏览:10次

题意：给出一个坐标系，这个接下来会有伞兵降落在这个坐标系内，每个伞兵有个坐标，现在地球的军队要使得伞兵降落在地上的一瞬间杀死他们，所以他们造了一些激光，这些激光可以杀死一整行或者一整列的伞兵，每行每列都有一个造激光的花费，最后的总花费就是所有激光造价的乘积，问造价最少是多少。

思路：首先我们不考虑他的总花费是激光造价的乘积，如果仅仅是和的话，那么这个问题很简单，就是求最小割，但是现在他的造价不是和，那么怎么转化呢。

这时候我们就想到了对数的性质，lg(a ) + lg(b) = lg(a * b)。可以知道，要使得a * b 最小，就是使得lg(a) + lg(b)最小，那么问题就可以转化了。

所以我们可以将每行每列的造价转化称对数，然后求一次最小割即可。

建图过程就不赘述了，很模版的建图。

#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#define Max 2505  
#define FI first  
#define SE second  
#define ll long long  
#define PI acos(-1.0)  
#define inf 0x3fffffff  
#define LL(x) ( x << 1 )  
#define bug puts("here")  
#define PII pair  
#define RR(x) ( x << 1 | 1 )  
#define mp(a,b) make_pair(a,b)  
#define mem(a,b) memset(a,b,sizeof(a))  
#define REP(i,s,t) for( int i = ( s ) ; i <= ( t ) ; ++ i )  
  
using namespace std;  
#define N 5000  
int n , m , k ;  
struct kdq{  
    int s , e  , next ;  
    double l ;  
}ed[N] ;  
int head[N] , num ;  
int S , T ;  
void add(int s ,int e , double l ){  
    ed[num].e = e ;  
    ed[num].l = l ;ed[num].next = head[s] ;  
    head[s] = num ++ ;  
    ed[num].e = s ;ed[num].l = 0 ;ed[num].next = head[e] ;  
    head[e] = num ++ ;  
}  
void init(){  
    mem(head ,-1) ;num = 0 ;  
}  
int deep[N] ;  
int qe[N] ;  
int dinic_bfs(){  
    mem(deep ,-1) ;  
    deep[S] = 0 ;  
    int h = 0 , t = 0 ;  
    qe[h ++ ] = S ;  
    while(h > t){  
        int tmp = qe[t ++ ] ;  
        for (int i = head[tmp] ; ~i ; i = ed[i].next ){  
            double l = ed[i].l ;  
            int e = ed[i].e ;  
            if(l > 0 && deep[e] == -1){  
                deep[e] = deep[tmp] + 1 ;  
                qe[h ++ ] = e ;  
            }  
        }  
    }  
    return deep[T] != -1 ;  
}  
double dinic_dfs(int now ,double f){  
    if(now == T)return f ;  
    double flow = 0 ;  
    for (int i = head[now] ; ~i ; i = ed[i].next ){  
        int e = ed[i].e ;  
        double l = ed[i].l ;  
        if(deep[e] == deep[now] + 1 && l > 0 && (f - flow) > 0 ){  
            double mm = min(l , f - flow) ;  
            double nn = dinic_dfs(e , mm) ;  
            flow += nn ;  
            ed[i].l -= nn ;  
            ed[i ^ 1].l += nn ;  
        }  
    }  
    if(flow < 1e-8)deep[now] = -2 ;  
    return flow ;  
}  
  
double dinic(){  
    double flow = 0 ;  
    while(dinic_bfs()){  
        flow += dinic_dfs(S,  inf) ;  
    }  
    return flow ;  
}  
int main() {  
    int tt ;  
    cin >> tt ;  
    while(tt -- ){  
        cin >> n >> m >> k ;  
        init() ;  
        T = n + m + 1 ;  
        for (int i = 1 ; i <= n ; i ++ ){  
            double d ;  
            scanf("%lf",&d) ;  
            add(S , i , log(d * 1.0)) ;  
        }  
        for (int i = 1 ; i <= m ; i ++ ){  
            double d ;  
            scanf("%lf",&d) ;  
            add(i + n , T , log(d * 1.0)) ;  
        }  
        for (int i = 0 ; i < k ; i ++ ){  
            int x , y ;scanf("%d%d",&x,&y) ;  
            add(x , y + n , inf) ;  
        }  
        printf("%.4f\n",exp(dinic())) ;//最后转化回来就可以了  
    }  
    return 0 ;  
}


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：HDU4528+BFS	下一篇：CF DIV.2 A. The Wall

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: