Paratroopers(最小割模型)

http://poj.org/problem?id=3308

题意：一个m*n的网格，有L位火星空降兵降落在网格中，地球卫士为了能同时消灭他们，在网格的行或列安装了一个枪支，每行或每列的枪支都能消灭这一整行或整列的空降兵，给出每一行和每一列安装枪支的花费，总的花费等于所有安装枪支的行和列的花费的乘积。求出最小的总的花费。

思路：(1)最小割：对于图中的两个点(一般为源点和汇点)来说，如果把图中的一些边去掉，如果它们之间无法连通的话，则这些边组成的集合就叫为割了。如果这些边有权值，最小割就是指权值之和最小的一个割。(2)对任意一个只有一个源点和一个汇点的图来说，从源点到汇点的最大流等于最小割，可以用Dinic算法求。由于总的花费等于各花费的乘积，取对数后就能变成和的形式了.

 #include <stdio.h>

 #include <string.h>

 #include <algorithm>

 #include <queue>

 #include <math.h>

 using namespace std;

 const int N=;

 const double eps=1e-;

 const int INF=<<;

 struct node

 {

     int v,u,next;

     double w;

 } edge[N*];

 int head[N],d[N];

 int cnt,S,T;

 void init()

 {

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

     cnt = ;

 }

 void add(int u,int v,double w)

 {

     edge[cnt].u = u;

     edge[cnt].v = v;

     edge[cnt].w = w;

     edge[cnt].next = head[u];

     head[u]=cnt++;

     edge[cnt].u = v;

     edge[cnt].v = u;

     edge[cnt].w = ;

     edge[cnt].next = head[v];

     head[v]=cnt++;

 }

 int bfs()

 {

     queue<int>q;

     q.push(S);

     memset(d,-,sizeof(d));

     d[S] = ;

     while(!q.empty())

     {

         int t = q.front();

         q.pop();

         for (int j = head[t]; j!=-; j=edge[j].next)

         {

             int v = edge[j].v;

             if (d[v]==-&&edge[j].w>eps)

             {

                 d[v] = d[t]+;

                 q.push(v);

             }

         }

     }

     if (d[T]>)

         return ;

     return ;

 }

 double dinic(int t,double sum)

 {

     if(t==T)

         return sum;

     for (int i = head[t]; i!=-; i=edge[i].next)

     {

         double a;

         int v = edge[i].v;

         double w = edge[i].w;

         if (d[v]==d[t]+&&w>eps&&(a=dinic(v,min(sum,w))))

         {

             edge[i].w-=a;

             edge[i^].w+=a;

             return a;

         }

     }

     return ;

 }

 int main()

 {

     int t,m,n,l;

     int u,v;

     double val;

     scanf("%d",&t);

     while(t--)

     {

         init();

         scanf("%d%d%d",&m,&n,&l);

         S = ;

         T=n+m+;

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

         {

             scanf("%lf",&val);

             add(S,i,log(val));

         }

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

         {

             scanf("%lf",&val);

             add(m+i,T,log(val));

         }

         while(l--)

         {

             scanf("%d%d",&u,&v);

             add(u,v+m,INF);

         }

         double ans = ;

         while(bfs())

         {

             double ss = dinic(S,INF);

             if(ss>eps)

                 ans+=ss;

             else break;

         }

         printf("%.4f\n",exp(ans));

     }

     return ;

 }

巴特西

Paratroopers(最小割模型)

最新文章

热门文章