打鸟问题-EK-最大流

在一个 n * m (0 < m, n <=300) 的方阵中有 k(0cj<=10000) ，现已知 n, m, k 以及每一行和每一列上开一枪的花费，请问打死所有鸟所需的最小总花费。 [ 输入 ]

输入包含多组测试数据。

每组测试数据第一行有三个整数 n, m, k 。

接下来一行有 n 个整数，第 i 个整数表示在第 i 行开一枪所需的花费 ri 。 接下来一行有 m 个整数，第 j 个整数表示在第 j 行开一枪所需的花费 cj 。

接下来 k 行，每行有两个整数 x, y (0对于每组测试数据，请输出一行，包含一个整数，即打死该图中所有鸟所需的最小花费值。 解题思路：打鸟问题，是一个用EK算法解决最大流问题的一个典型。选取一个源点，和所有的行连上边，流量为给定的花费；所有的汇点和所有的列连，流量为给定的花费；所有有鸟的位置的行和列连上边，权值无穷，反向权值值为0。算出的最大流就是最小花费。

#include #include #include using namespace std; const int N=602;

const int INF=99999999; int n,m,pp; struct point { int len; int an[N]; int tag; };

struct edge1 { int flow; };

struct point2 { int pos; int pre; }po[N];

inline int min(int a,int b) { return aint high=1,low=0; struct point p[N];

struct edge1 edge[N][N];

int bfs(int start) { int i; while(high!=low) { for(i=0;i0&&p[p[po[low].pos].an[i]].tag==0) { po[high].pos=p[po[low].pos].an[i]; p[po[high].pos].tag=1; po[high].pre=low; if(po[high++].pos==pp) goto OUT; } } ++low; } OUT: if(high==low) return 0; else return 1; };

int EK(int src,int dst) {

int i, totalFlow = 0, PingJing; if (src == dst) return INF; high=1;low=0; while (bfs(src)) { for(i=0;i<=pp;++i) p[i].tag=0; PingJing = INF; for( i = high-1; i>0;i=po[i].pre ) PingJing = min(PingJing, edge[po[po[i].pre].pos][po[i].pos].flow); totalFlow += PingJing; for( i = high-1; i>0; i=po[i].pre ) { edge[po[po[i].pre].pos][po[i].pos].flow -= PingJing; if(po[po[i].pre].pos!=0&&po[i].pos!=pp) edge[po[i].pos][po[po[i].pre].pos].flow += PingJing; ;///反¤¡ä向¨°边À? } high=1;low=0; }

return totalFlow; }

int main() {

}

int i,j,bn;//n为a行D，ê?m为a列¢D，ê?bn为a鸟?的Ì?数ºy量¢? int a,b;

while( scanf(\"%d%d%d\",&n,&m,&bn)!=EOF) { pp=n+m+1; for(i=1;i<=n;++i) for(j=n+1;jreturn 0;