poj3308 Paratroopers 二分图的最小割 - c++编程基础

有L个伞兵空降到n*m的地图中，告诉你伞兵的坐标，你可以在任意位置设立一个激光炮，激光炮可以花费r[i] 杀死这一行的伞兵，花费c[i]杀死这一列的伞兵，最后的

总花费是每次花费的乘积。（其实log(a)+log(b)+...+log(z)=log(a*b*...*z)，对数可以将乘法变成加法）。

对于这样的行列模型，很容易想到二分图，将行列看成二分图的X和Y集，从源点到X集建边，容量为log(r[i])，Y集到汇点建边，容量为log(c[i])，根据伞兵的左边从X集到Y集建边，容量为INF（保证不选到）。这样建图后，原问题就变成了求最小割。

最后再用exp将答案转回来就行了。

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
         #include
         
           #include
          
            #include
           
             #define eps 1e-12 //#define INF 0x7fffffff #define maxn 10000 using namespace std; double INF=999999999.0; int n,m,q; int en; int st,ed; //源点和汇点 int dis[maxn] ;//dis[i],表示 到 原点 s 的 层数 double nn[555],mm[555]; int que[9999999]; struct edge { int to,next; double c; }; edge e[9999999]; int head[maxn]; void add(int a,int b,double c) { c=log(c); e[en].to=b; e[en].c=c; e[en].next=head[a]; head[a]=en++; e[en].to=a; e[en].c=0; e[en].next=head[b]; head[b]=en++; } int bfs() { memset(dis,-1,sizeof(dis)); dis[st]=0; int front=0,rear=0; que[rear++]=st; while(front
            
             0) { dis[i] = dis[j]+ 1 ; que[rear++]=i; if(i==ed) return true; } } } return false; } double dfs(int x,double mx) { int i,a; if(x==ed) return mx ; double ret=0; for(int k=head[x];k!=-1&&ret