题意：n*m的地图，给出L个火星人登陆的坐标，要在火星人登陆地球的瞬间全部消灭他们，有一种激光枪，一次可以消灭一行（或一列），消灭一行（或一列）有不同的代价，总代价是所有激光枪的代价之积。
思路：之前做过类似的题是求最少多少次能消灭，而最少的次数不一定是代价最小的，行跟列建立二分图，每个火星人就是一条边，就是选一些点覆盖所有的边，这些点的权值之积最小，如果是求和的话就是二分图的最小点权覆盖集了，所以要把求积转化成求和，a*b=log(a)+log(b);求出最小割就可以了。
#include#include #include const int N=3000;#define inf 100.0int head[N],num,ans,start,end,gap[N],dis[N];struct edge{ int st,ed,next; double flow;}e[N*100];void addedge(int x,int y,double w){ e[num].st=x;e[num].ed=y;e[num].flow=w;e[num].next=head[x];head[x]=num++; e[num].st=y;e[num].ed=x;e[num].flow=0;e[num].next=head[y];head[y]=num++;}double dfs(int u,double minflow){ if(u==end)return minflow; int i,v; double f,flow=0.0; for(i=head[u];i!=-1;i=e[i].next) { v=e[i].ed; if(e[i].flow>0) { if(dis[v]+1==dis[u]) { f=dfs(v,e[i].flow>minflow-flow?minflow-flow:e[i].flow); flow+=f; e[i].flow-=f; e[i^1].flow+=f; if(minflow-flow<=1e-8)return flow; if(dis[start]>=ans)return flow; } } } if(--gap[dis[u]]==0) dis[start]=ans; dis[u]++; gap[dis[u]]++; return flow;}double isap(){ double maxflow=0.0; memset(gap,0,sizeof(gap)); memset(dis,0,sizeof(dis)); gap[0]=ans; while(dis[start]