当前位置:编程学习 > C/C++ >>

POJ 3308 二分图最小点权覆盖 最大流

本题题意就是,公元XXXX年,地球跟外星人打仗,然后有一个n*m的网格,会有外星人降落到某些位置上,因为外星人比较猛,所以必须一下来就消灭他们,现在可以在某些行或者某些列的首部放一些激光枪。这些枪的特性就是你放在行的首部你就消灭这一行的敌人,放在列的首部就消灭一列的敌人。但是放置这些枪也需要一定的费用,这些费用已经给出来了,最后总费用是这些枪的费用之积,现在要求最小的这个费用。
看到积之后,我们可以转换为加法,就是取log,但是不知道数据是什么情况,会不会超过double,就试一下。
然后就能发现是一个二分图最小点权覆盖的模型了
然后就是建图,源点跟所有的行节点连边,值呢就是相应花费的log,然后列节点与汇点连边,值也为相应的花费的log,行与列的连边就代表着相应的外星人了,值为INF。
注意到INF不能太大,因为double的精度问题,INF如果位数太多,算最大流的时候由于有小数,小数点后如果有8位,小数点之前如果再有太多的位数,就会损失精度
最后的结果用exp函数求回来即可

[cpp] 
#include <iostream> 
#include <algorithm> 
#include <cstring> 
#include <string> 
#include <cstdio> 
#include <cmath> 
#include <queue> 
#include <map> 
#include <set> 
#define eps 1e-5 
#define MAXN 111 
#define MAXM 55555 
#define INF 1000007 
using namespace std; 
struct node 

    int v; 
    double c, f; 
    int next, r; 
}edge[MAXM]; 
int dist[MAXN], nm[MAXN], src, des, n; 
int head[MAXN], e; 
void add(int x, int y, double c) 

    edge[e].v = y; 
    edge[e].c = c; 
    edge[e].f = 0; 
    edge[e].r = e + 1; 
    edge[e].next = head[x]; 
    head[x] = e++; 
    edge[e].v = x; 
    edge[e].c = 0; 
    edge[e].f = 0; 
    edge[e].r = e - 1; 
    edge[e].next = head[y]; 
    head[y] = e++; 

void rev_BFS() 

    int Q[MAXN], h = 0, t = 0; 
    for(int i = 1; i <= n; ++i) 
    { 
        dist[i] = MAXN; 
        nm[i] = 0; 
    } 
    Q[t++] = des; 
    dist[des] = 0; 
    nm[0] = 1; 
    while(h != t) 
    { 
        int v = Q[h++]; 
        for(int i = head[v]; i != -1; i = edge[i].next) 
        { 
            if(edge[edge[i].r].c == 0 || dist[edge[i].v] < MAXN)continue; 
            dist[edge[i].v] = dist[v] + 1; 
            ++nm[dist[edge[i].v]]; 
            Q[t++] = edge[i].v; 
        } 
    } 

void init() 

    e = 0; 
    memset(head, -1, sizeof(head)); 

double maxflow() 

    rev_BFS(); 
    int u; 
    double total = 0; 
    int cur[MAXN], rpath[MAXN]; 
    for(int i = 1; i <= n; ++i)cur[i] = head[i]; 
    u = src; 
    while(dist[src] < n) 
    { 
        if(u == des)     // find an augmenting path 
        { 
            double tf = INF; 
            for(int i = src; i != des; i = edge[cur[i]].v) 
                tf = min(tf, edge[cur[i]].c); 
            for(int i = src; i != des; i = edge[cur[i]].v) 
            { 
                edge[cur[i]].c -= tf; 
                edge[edge[cur[i]].r].c += tf; 
                edge[cur[i]].f += tf; 
                edge[edge[cur[i]].r].f -= tf; 
            } 
            total += tf; 
            u = src; 
        } 
        int i; 
        for(i = cur[u]; i != -1; i = edge[i].next) 
            if(edge[i].c > 0 && dist[u] == dist[edge[i].v] + 1)break; 
        if(i != -1)     // find an admissible arc, then Advance 
        { 
            cur[u] = i; 
            rpath[edge[i].v] = edge[i].r; 
            u = edge[i].v; 
        } 
        else        // no admissible arc, then relabel this vtex 
        { 
            if(0 == (--nm[dist[u]]))break;    // GAP cut, Important! 
            cur[u] = head[u]; 
            int mindist = n; 
            for(int j = head[u]; j != -1; j = edge[j].next) 
                if(edge[j].c > 0)mindist = min(mindist, dist[edge[j].v]); 
            dist[u] = mindist + 1; 
            ++nm[dist[u]]; 
            if(u != src) 
                u = edge[rpath[u]].v;    // Backtrack 
      &n

补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,