|
|
Posted on 2010-10-06 11:40 成幸毅 阅读(398) 评论(0) 编辑 收藏 引用
最小点权覆盖，参考胡伯涛论文，这里是要求成本的乘积，所以先用log函数改成加法形式。
 #include <iostream>
#include <cmath>
using namespace std;
const double INF = 1e7;
const int MAXN = 100000;
  struct node  {
 double w;
int v,next;
 }edge[MAXN];
inline double min(double x,double y) {
return x > y?y:x;
}
int e[MAXN],s,t;
int sps;
int NN;
int head[MAXN];
void addedge(int u,int v,double val) {
edge[sps].v = v;
edge[sps].w = val;
edge[sps].next = head[u];
head[u] = sps++;
edge[sps].v = u;
edge[sps].w = 0;
edge[sps].next = head[v];
head[v] = sps++;
}
double sap()
{
memset(e,0,sizeof(e));
int pre[MAXN],cur[MAXN],dis[MAXN],gap[MAXN];
double flow=0,aug=INF;
int u;
bool flag;
for(int i=0;i<=NN;i++)
  {
gap[i]=dis[i]=0;
 }
gap[s]=NN;
u=pre[s]=s;
while(dis[s]<NN)
{
flag=0;
for(int j= head[u];j!=-1;j=edge[j].next)
{
int v=edge[j].v;
if(edge[j].w>0&&dis[u]==dis[v]+1)
{
flag=1;
if(edge[j].w<aug) aug=edge[j].w;
e[u] = j;
pre[v]=u;
u=v;
if(u==t)
{
flow+=aug;
while(u!=s)
{
u=pre[u];
edge[e[u]].w-=aug;
edge[e[u]^1].w+=aug;
}
aug=INF;
}
break;
}
}
if(flag)
continue;
int mindis=NN;
for(int j=head[u];j!=-1;j=edge[j].next)
{
int v=edge[j].v;
if(edge[j].w>0&&dis[v]<mindis)
{
mindis=dis[v];
e[u]=j;
}
}
if((--gap[dis[u]])==0)
break;
gap[dis[u]=mindis+1]++;
u=pre[u];
}
return flow;
}
int main() {
int cas;
scanf("%d",&cas);
while(cas--) {
double value;
memset(head,-1,sizeof(head));
int a,b,n,m,l;
sps = 0;
scanf("%d%d%d",&n,&m,&l);
s = 0,t = n + m + 1;
for(int i = 1; i <= n; i++) {
scanf("%lf",&value);
addedge(s,i,log10(value));
}
for(int i = 1; i <= m; i++) {
scanf("%lf",&value);
addedge(i+n,t,log10(value));
}
for(int i = 1; i <= l; i++) {
scanf("%d%d",&a,&b);
addedge(a,b+n,INF);
}
NN = t+1;
double ans = sap();
printf("%.4lf\n",pow(10,ans));
}
// system("pause");
return 0;
}
|