题意：有些火星人要来袭击地球，我们知道这些火星人登陆的坐标（row,col)，现在要把他们全部KO。地球上有一种激光武器每次可以消灭一行或者一列中所有的火星人。但是不同的行以及不同的列上安置武器的花费不一样。并且总花费为每一行每一列的花费的乘积。现在要求在最小花费的情况下消灭所有火星人。
题解：最小点权覆盖，最小割。求乘积则换成log。给出了两组代码。第一组与EK算法有些相似的地方，可以结合着看，第二组跟简洁一些。。
#include <cmath>
#include <iostream>
using namespace std;
#define MAX 1000
#define eps 0.0001
#define INF 9999999999
#define min(a,b) (a<b?a:b)
struct Edge
{
int st, ed;
int next;
double flow;
} edge[MAX*10];
int pre[MAX]; // pre[u]储存以u为终点的边的编号，它储存的是边
int head[MAX], out[MAX];
/* 每次跟新out[u]都相当于把点u所关联的下一条边存储起来，这样就可以避免重复地由head[u]开始一个一个找。
有的写法没有用out[]这个数组，而是标记出所有被删除的边，所以增加了一个数组del[], 这样写貌似会浪费一些时间，
因为每次都需要从某个点的第一条边逐步地找，直到找到合适的边。*/
int leve[MAX]; // 层次图中每个点的层次
int que[MAX], stk[MAX];
int E, R, C, L, src, dest;
void add_edge ( int u, int v, double val )
{
edge[E].st = u;
edge[E].ed = v;
edge[E].flow = val;
edge[E].next = head[u];
head[u] = E++;
edge[E].st = v;
edge[E].ed = u;
edge[E].flow = 0;
edge[E].next = head[v];
head[v] = E++;
}
bool dinic_bfs ()
{
int front, rear, u, v, i;
front = rear = 0;
memset(leve,-1,sizeof(leve));
que[rear++] = src;
leve[src] = 0;
while ( front != rear )
{
u = que[front];
front = ( front + 1 ) % MAX;
for ( i = head[u]; i != -1; i = edge[i].next )
{
v = edge[i].ed;
if ( leve[v] == -1 && edge[i].flow > eps )
{
leve[v] = leve[u] + 1;
que[rear] = v;
rear = ( rear + 1 ) % MAX;
}
}
}
return leve[dest] >= 0; // leve[dest] == -1 说明没有找到增广路径
/* 有的写法是在循环中，只要到达dest立即返回true。个人感觉这样效率不会太高，因为得到的层次图是不完整的，而Dinic的优势就在于通过层次图
来优化寻找增广路的过程. */
}
double dinic_dfs ()
{
int top = 0, u, v, pos,i;
double minf, res = 0;
memcpy(out,head,sizeof(head)); // 将head的值拷给out
stk[top++] = u = src;
while ( top != 0 ) //栈空说明在当前层次图中，所有的增广路径寻找完毕
{
while ( u != dest )
{
for ( i = out[u]; i != -1; i = edge[i].next )
{
v = edge[i].ed;
if ( edge[i].flow > eps && leve[u] + 1 == leve[v] )
{
out[u] = edge[i].next; // 下一次访问的时候，就可以直接得到edge[i].next
pre[v] = i; // 存储边的编号
stk[top++] = v; // 栈中放的是点
u = v;
break;
}
}
if ( i == -1 ) // 若从某点出发找不到合法的边
{
top--; // 把该点从栈中删除
if ( top <= 0 ) break;
u = stk[top-1]; // 返回前一个点
}
}
if ( u == dest )
{
minf = INF;
while ( u != src )
{
minf = min ( edge[pre[u]].flow, minf );
u = edge[pre[u]].st;
}
u = dest;
while ( u != src )
{
edge[pre[u]].flow -= minf;
edge[pre[u]^1].flow += minf;
if ( edge[pre[u]].flow < eps ) pos = edge[pre[u]].st; // 记录下零流出现的顶点。取最前面的哪一个。
u = edge[pre[u]].st;
}
while ( top > 0 && stk[top-1] != pos ) top--; // 退回到零流出现的顶点
if ( top > 0 ) u = stk[top-1];
res += minf;
}
}
return res;
}
double Dinic ()
{
double ans = 0, temp;
while ( dinic_bfs() )
{
temp = dinic_dfs();
if ( temp > eps ) ans+=temp;
else break;
}
return ans;
}
int main()
{
int T, a, b, i;
double val;
scanf("%d",&T);
while ( T-- )
{
scanf("%d%d%d",&R,&C,&L);
memset(head,-1,sizeof(head));
src = E = 0;
dest = R + C + 1;
for ( i = 1; i <= R; i++ )
{
scanf("%lf",&val);
add_edge ( src, i, log(val) );
}
for ( i = 1; i <= C; i++ )
{
scanf("%lf",&val);
add_edge ( i+R, dest, log(val) );
}
while ( L-- )
{
scanf("%d%d",&a,&b);
add_edge(a,b+R,INF);
}
val = Dinic();
printf("%.4f\n",exp(val));
}
return 0;
}
下面的代码更简洁···
#include <cmath>
#include <iostream>
using namespace std;
#define MAX 1000
#define INF 1000000000
#define eps 0.00001
#define min(a,b) (a<b?a:b)
struct Edge
{
int st, ed;
int next;
double flow;
} edge[MAX*10];
int head[MAX], out[MAX];
int dep[MAX], que[MAX], stk[MAX];
int R, C, L, E;
int src, dest;
void add_edge ( int u, int v, double w )
{
edge[E].flow = w;
edge[E].st = u;
edge[E].ed = v;
edge[E].next = head[u];
head[u] = E++;
edge[E].flow = 0;
edge[E].st = v;
edge[E].ed = u;
edge[E].next = head[v];
head[v] = E++;
}
bool dinic_bfs()
{
memset(dep, -1, sizeof(dep));
int front = 0, rear = 0;
bool flag = false;
que[rear++] = src;
dep[src] = 0;
while ( front < rear )
{
for( int i = head[que[front++]]; i != -1; i = edge[i].next )
{
if ( dep[edge[i].ed] == -1 && edge[i].flow > eps )
{
dep[edge[i].ed] = dep[edge[i].st] + 1;
que[rear++] = edge[i].ed;
if ( edge[i].ed == dest ) flag = true; // 不直接返回true效率会高些，因为构成的层次图更完整
}
}
}
return flag;
}
double Dinic ()
{
double maxFlow = 0, temp;
while ( dinic_bfs() )
{
int u = src, top = 0, i;
for ( i = src; i <= dest; i++ )
out[i] = head[i];
while ( out[src] != -1 ) // 一个深搜的过程，当与源点关联的所有边都被访问过，则查询完毕
{
if ( u == dest )
{
temp = INF;
for ( i = top - 1; i >= 0; i-- )
temp = min ( temp, edge[stk[i]].flow );
maxFlow += temp;
for ( i = top - 1; i >= 0; i-- )
{
edge[stk[i]].flow -= temp;
edge[stk[i]^1].flow += temp;
if ( fabs(edge[stk[i]].flow) <= eps ) top = i; // 找出零流最先出现的边，从该边的起点进行下一次增广
}
u = edge[stk[top]].st;
}
else if ( out[u] != -1 && edge[out[u]].flow > eps && dep[u] + 1 == dep[edge[out[u]].ed] )
{
stk[top++] = out[u]; // 栈中储存的是边
u = edge[out[u]].ed;
}
else
{
// 删去出度为0的边或者流量为0的边。
// 仔细体会下面的循环，当某个点的所有出边都被变了过之后，它便可以出栈了，否则out[u]应该指向下一条边
while ( top > 0 && u != src && out[u] == -1 )
u = edge[stk[--top]].st;
out[u] = edge[out[u]].next;
}
}
}
return maxFlow;
}
int main()
{
int T, a, b, i;
double val;
scanf("%d",&T);
while ( T-- )
{
scanf("%d%d%d",&R,&C,&L);
memset(head,-1,sizeof(head));
src = E = 0;
dest = R + C + 1;
for ( i = 1; i <= R; i++ )
{
scanf("%lf",&val);
add_edge ( src, i, log(val) );
}
for ( i = 1; i <= C; i++ )
{
scanf("%lf",&val);
add_edge ( i+R, dest, log(val) );
}
while ( L-- )
{
scanf("%d%d",&a,&b);
add_edge(a,b+R,INF);
}
val = Dinic();
printf("%.4f\n",exp(val));
}
return 0;
}