典型的最小割模型题目。做之前先读了国家集训队论文《最小割模型在信息学竞赛中的应用》。
题目大意是，有一个m*n的网格，m行和n列各对应一个权值。网格里面有l个点，如何在m行和n列中选择某些行列，使所有的点被覆盖，且使行列权值之积最小。
建图时S连所有行，E连所有列，行和列之间的边则对应原图的点且容量为无穷。这样便能应用最小割模型，得到的点集划分中割边必定为有穷边，且对应着原图中选中的行或列，使原图中每个点都能被覆盖（不能同时到S、E可达）。这里由于所求是作乘，将其取log，便转换成加法运算了。用EK求得最大流后，再从S点出发作DFS，就得到了实际的最小割方案，再依次检查遍历情况作乘即可。
不知为何c++竟然没有log2，CE了一次…T__T
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 |
#include<cmath> #include<cstdio> #include<cstring> #include<queue> using namespace std; int t,m,n,hd[1002],el,b[1002],p[1002],S=0,E; double c[1002][1002],d[1002][1002],mnf[1002]; struct edge { int j,p; }e[300000]; inline void adde(int i,int j,double k) { c[i][j]=k; e[el].j=j; e[el].p=hd[i]; hd[i]=el++; e[el].j=i; e[el].p=hd[j]; hd[j]=el++; } void EK() { int i,j,k,l; double f; while(1) { memset(b,0,sizeof b); mnf[S]=1e10; b[S]=1; queue<int>Q; Q.push(S); while(!Q.empty()&&!b[E]) { i=Q.front(); Q.pop(); for(l=hd[i];l!=-1;l=e[l].p) { j=e[l].j; if(b[j]||c[i][j]<1e-10) continue; mnf[j]=mnf[i]<c[i][j]?mnf[i]:c[i][j]; p[j]=i; b[j]=1; Q.push(j); } } if(!b[E]) break; for(j=E;j!=S;j=p[j]) { i=p[j]; c[i][j]-=mnf[E]; c[j][i]+=mnf[E]; } } } void DFS(int i) { int j,l; for(l=hd[i];l!=-1;l=e[l].p) { j=e[l].j; if(b[j]||c[i][j]<1e-10) continue; b[j]=1; DFS(j); } } int main() { int i,j,k,l; double f; scanf("%*d"); while(~scanf("%d%d%d",&m,&n,&l)) { el=0; E=m+n+1; memset(hd,-1,sizeof hd); memset(c,0,sizeof c); for(i=1;i<=m;i++) { scanf("%lf",&f); adde(S,i,log(f)); d[S][i]=f; } for(;i<=m+n;i++) { scanf("%lf",&f); adde(i,E,log(f)); d[i][E]=f; } while(l--) { scanf("%d%d",&i,&j); adde(i,m+j,1e10); } EK(); memset(b,0,sizeof b); b[S]=1; DFS(S); for(i=1,f=1;i<=m;i++) { if(!b[i]) f*=d[S][i]; } for(;i<=m+n;i++) { if(b[i]) f*=d[i][E]; } printf("%.4lf\n",f); } return 0; } |