POJ 3308 Paratroopers 题解【网络流】【最小点权覆盖集】

点击量：380

很适合用来练习最小点权覆盖集的一个题。

目录

Description

It is year 2500 A.D. and there is a terrible war between the forces of the Earth and the Mars. Recently, the commanders of the Earth are informed by their spies that the invaders of Mars want to land some paratroopers in the $ m\times n$ grid yard of one their main weapon factories in order to destroy it. In addition, the spies informed them the row and column of the places in the yard in which each paratrooper will land. Since the paratroopers are very strong and well-organized, even one of them, if survived, can complete the mission and destroy the whole factory. As a result, the defense force of the Earth must kill all of them simultaneously after their landing.

In order to accomplish this task, the defense force wants to utilize some of their most hi-tech laser guns. They can install a gun on a row (resp. column) and by firing this gun all paratroopers landed in this row (resp. column) will die. The cost of installing a gun in the $ i$th row (resp. column) of the grid yard is $ r_i$ (resp. $ c_i$ ) and the total cost of constructing a system firing all guns simultaneously is equal to the product of their costs. Now, your team as a high rank defense group must select the guns that can kill all paratroopers and yield minimum total cost of constructing the firing system.

Input

Input begins with a number $ T$ showing the number of test cases and then, $ T$ test cases follow. Each test case begins with a line containing three integers $ 1\le m\le 50 , 1\le n \le 50$ and $ 1\le l\le 500$ showing the number of rows and columns of the yard and the number of paratroopers respectively. After that, a line with $ m$ positive real numbers greater or equal to $ 1.0$ comes where the $ i$th number is $ r_i$ and then, a line with $ n$ positive real numbers greater or equal to $ 1.0$ comes where the $ i$th number is $ c_i$. Finally, $ l$ lines come each containing the row and column of a paratrooper.

Output

For each test case, your program must output the minimum total cost of constructing the firing system rounded to four digits after the fraction point.

Sample Input

1
4 4 5
2.0 7.0 5.0 2.0
1.5 2.0 2.0 8.0
1 1
2 2
3 3
4 4
1 4

Sample Output

16.0000

Source

Amirkabir University of Technology Local Contest 2006

题意：

给定一个$ n\times m$的矩阵。其中有$ l$个位置有火星人。现在每行每列都有一把枪，每把枪的发射都需要一定代价。你需要找出其中方案打掉所有的火星人，并使得代价乘积最小。

题解：

以前一直不会这种“一打打一排”的题。

首先我们看到了答案要求的是乘积。不过这不影响我们的建模，甚至题目也保证了$ r_i,c_i\ge 1.0$。此时只需要使得所用枪代价的对数和最小，最终再放到$ \mathrm{e}$的指数上就可以了。

此时我们分析题目。因为每个火星人至少被行上或列上的其中一个攻击到，所以可以联想到最小点权覆盖集。刚好行和列又恰好是一对，所以利用二分图最小点权覆盖集来解决这个问题。

每一行、每一列都看作是一个点，每个火星人连接了它所在的行和它所在的列。此时每个火星人就成了一条边，因为每个火星人都要被攻击到，所以每条边上都要有点被选。令源点连到行，汇点连到列，行列之间通过火星人连接，源汇点连到这些点的边权是启用该行/该列的费用的对数，跑最大流。

最后取$ \mathrm e$的幂输出答案。

tips

• 在poj上交G++时double要用%f，交C++时用$lf

• 这个题由于取了对数，所以最大值不会很大。最大流中的inf设置为1e2即可，此时eps可以设为1e-8。（inf更大就会WA）

Code：

#include<cmath>
#include<cstdio>
#include<cstring>
#define eps 1e-8
double Min(double x,double y)
{
    return x<y?x:y;
}
struct edge
{
    int n,nxt;
    double v;
    edge(int n,int nxt,double v)
    {
        this->n=n;
        this->nxt=nxt;
        this->v=v;
    }
    edge(){}
}e[2000];
int head[150],ecnt=-1;
void add(int from,int to,double v)
{
    e[++ecnt]=edge(to,head[from],v);
    head[from]=ecnt;
    e[++ecnt]=edge(from,head[to],0);
    head[to]=ecnt;
}
int d[150],q[150];
bool bfs()
{
    int l=0,r=0;
    memset(d,0,sizeof(d));
    d[123]=1;
    q[++r]=123;
    while(l<r)
    {
        int x=q[++l];
        for(int i=head[x];~i;i=e[i].nxt)
            if(e[i^1].v>eps&&!d[e[i].n])
            {
                d[e[i].n]=d[x]+1;
                q[++r]=e[i].n;
            }
    }
    return d[0]>0;
}
double dinic(int x,double in)
{
    if(x==123)
        return in;
    double flow=in;
    for(int i=head[x];flow>eps&&~i;i=e[i].nxt)
        if(e[i].v>eps&&d[e[i].n]==d[x]-1)
        {
            double tmp=dinic(e[i].n,Min(flow,e[i].v));
            if(tmp<eps)
                d[e[i].n]=0;
            e[i].v-=tmp;
            e[i^1].v+=tmp;
            flow-=tmp;
        }
    return in-flow;
}
int main()
{
#ifdef wjyyy
    freopen("data.in","r",stdin);
    freopen("ans.out","w",stdout);
#endif
    int T,n,m,t,u,v;
    double w;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d%d",&n,&m,&t);
        memset(head,-1,sizeof(head));
        ecnt=-1;
        for(int i=1;i<=n;++i)
        {
            scanf("%lf",&w);
            add(0,i,log(w));
        }
        for(int i=1;i<=m;++i)
        {
            scanf("%lf",&w);
            add(n+i,123,log(w));
        }
        for(int i=1;i<=t;++i)
        {
            scanf("%d%d",&u,&v);
            add(u,n+v,1e2);
        }
        double ans=0;
        while(bfs())
        {
            double tmp;
            do
            {
                tmp=dinic(0,1e2);
                ans+=tmp;
            }while(tmp>eps);
        }
        printf("%.4lf\n",exp(ans));
    }
    return 0;
}