2961506_ac_62ms_224k.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

const int mx = 110;
const double inf = (double)1e9;

int N, M, S, T, L, R, d[mx], op[mx], st[mx], lst[mx], tp;
double c[mx][mx], maxflow;

int init();
int calc();
void flow();

int main()
{
	int cas;

	scanf("%d",&cas);
	while(cas--) 
	{
		init();
		while(calc()) 
			flow();
		printf("%.4lf\n", exp(maxflow));
	}
	return 0;
}

double min(double a,double b)
{
	return a - b < 0 ? a : b;
}

int init()
{
	int row, col;
	int x, y;
	int i;
	double tmp;

	scanf("%d%d%d",&row,&col,&M);
	N = row+col+2;
	memset(c,0,sizeof(c));
	for(i = 0; i < row; i++)
	{
		scanf("%lf",&tmp);
		tmp = log(tmp);
		c[0][i+1] = tmp;
	}
	for(i = 0; i < col; i++)
	{
		scanf("%lf",&tmp);
		tmp = log(tmp);
		c[row+1+i][N-1] = tmp;
	}
	for(i = 0; i < M; i++)
	{
		scanf("%d%d",&x,&y);
		c[x][y+row] = min(c[0][x],c[y+row][N-1]);
	}
	S = 0; T = N - 1;
	maxflow = 0;
	return 1;
}

int calc()
{
  fill_n(d, mx, 0);
  d[op[0] = S] = 1;
  st[1] = 1;

  for(L = 0, R = 1; L < R; L++)
    for(int i = 0; i < N; i++) 
      if(c[op[L]][i] && !d[i]) {
    d[op[R++] = i] = d[op[L]] + 1;
    st[d[i]] = R;
      }
  return d[T];
}

int fnext(int u)
{
  if(d[u] == d[op[R - 1]]) return -1;
  for(int i = st[d[u]]; i < st[d[u] + 1]; i++) if(d[op[i]] > 0 && c[u][op[i]]) return op[i];
  return -1;
}

double refresh(int& tp)
{
  int top(tp);
  double ret = inf;

  for(int i = top - 1; i; i--) 
  {
	  if(c[lst[i-1]][lst[i]]<ret)
		  ret = c[lst[i - 1]][lst[i]];
  }
  for(i = top - 1; i; i--) {
    c[lst[i]][lst[i - 1]] += ret;
    if(!(c[lst[i - 1]][lst[i]] -= ret)) tp = i - 1;
  }
  return ret;
}

void flow()
{
  for(tp = 1, lst[0] = S; tp; ) 
    if(lst[tp - 1] == T) maxflow += refresh(tp);
    else {
      lst[tp] = fnext(lst[tp - 1]);
      if(lst[tp] >= 0) tp++;
      else d[lst[--tp]] = -10;
    }
}