赤裸裸的最小点权覆盖,不过G++居然不支持%lf...改交C++或者改%f过了...顺便提醒OpenWings各位果断发博啊...貌似最近我太堕落了...嗯.
code
1
#include <iostream>
2#include <cstdio>
3#include <algorithm>
4#include <cstring>
5#include <vector>
6#include <cmath>
7using namespace std;
8
9const int maxn=200;
10const int maxint = 1<<28;
11
12void get_min(int &a,int b)
{
13
if(b<a) a=b;
14
}
15
16void get_max(int &a,int b){
17 if(b>a) a=b;
18}
19
20struct Graph{
21
struct Adj{
22 int v,b;
23 double c;
24 Adj(int _v,double _c,int _b):v(_v),c(_c),b(_b){}
25 Adj(){}
26
};
27 int n,S,T,h[maxn],cnt[maxn];
28 vector<Adj> adj[maxn];
29 void clear(){
30 for(int i=0;i<n;i++){
31 adj[i].clear();
32 }
33 n=0;
34 }
35 void insert(int u,int v,double c,int d=0){
36 get_max(n,max(u,v)+1);
37 adj[u].push_back(Adj(v,c,adj[v].size()));
38 adj[v].push_back(Adj(u,c*d,adj[u].size()-1));
39 }
40 double maxflow(int _S,int _T){
41 S=_S,T=_T;
42 fill(h,h+n,0);
43 fill(cnt,cnt+n,0);
44 double flow=0;
45 while(h[S]<n){
46 flow+=dfs(S,maxint);
47 }
48 return flow;
49 }
50 double dfs(int u,double flow){
51 if(u==T){
52 return flow;
53 }
54 int minh=n-1;
55 double ct=0;
56 for(vector<Adj>::iterator it=adj[u].begin();fabs(flow)>1e-5&&it!=adj[u].end();++it){
57 if(fabs(it->c)>1e-5){
58 if(h[it->v]+1==h[u]){
59 double k=dfs(it->v,min(it->c,flow));
60 if(fabs(k)>1e-5){
61 it->c-=k;
62 adj[it->v][it->b].c+=k;
63 flow-=k;
64 ct+=k;
65 }
66 if(h[S]>=n){
67 return ct;
68 }
69 }
70 get_min(minh,h[it->v]);
71 }
72 }
73 if(fabs(ct)>1e-5){
74 return ct;
75 }
76 if(--cnt[h[u]]==0){
77 h[S]=n;
78 }
79 h[u]=minh+1;
80 ++cnt[h[u]];
81 return 0;
82 }
83}G;
84
85int T,N,M,L;
86int X,Y;
87double ans,dl;
88
89int main(){
90 //freopen("3308.in","r",stdin);
91 // freopen("3308.out","w",stdout);
92 scanf("%d",&T);
93 while(T--){
94 G.clear();
95 scanf("%d%d%d",&N,&M,&L);
96 int i;
97 for(i=1;i<=N;i++){
98 scanf("%lf",&dl);
99 dl=log10(dl);
100 G.insert(0,i,dl);
101 }
102 for(i=1;i<=M;i++){
103 scanf("%lf",&dl);
104 dl=log10(dl);
105 G.insert(N+i,N+M+1,dl);
106 }
107 for(i=1;i<=L;i++){
108 scanf("%d%d",&X,&Y);
109 G.insert(X,Y+N,100.0);
110 }
111 ans=G.maxflow(0,N+M+1);
112 printf("%.4lf\n",pow(10,ans));
113 }
114 return 0;
115}
116posted on 2010-08-07 22:54
OpenWings 阅读(298)
评论(0) 编辑 收藏 引用