「网络流练习」defuze
连锁炸弹是恐怖分子最近开始使用的一种威力巨大的爆炸物。其复杂的结构使拆除它的难度大大增加了。
一个连锁炸弹由m个引爆装置和n枚炸弹组成。每个引爆装置中有n条信号线分别与这n枚炸弹相连（1号线连接炸弹1，2号线连接炸弹2，……）。与一枚炸弹相连的m条信号线中只有一条是“安全线”——剪断后可以拆除炸弹，而剪断其它信号线则引爆炸弹。
专业的技术人员将给出一个m×n的表格。其中第i行第j列显示了引爆装置i与炸弹j连接的信号线是“安全线”的可能性Pij（Pij∈(0，1)），并且已知每个引爆装置上的“安全线”数目不超过k。技术人员的分析结果是绝对值得信任的。
政府的安全部门常常雇佣一些程序员去设计解决突发情况的程序。其中一项任务正是提高排除连锁炸弹的成功率。成功的拆除一个连锁炸弹，必须切断与炸弹相连所有n条“安全线”。现在，请设计一个程序，求出应剪断哪n条信号线，才能使拆除所有炸弹的可能性 ∏ Pij（即所有剪断的信号线pij的乘积）最大。
输入文件
输入的第一行为3个整数m,n,k（用空格分隔开）。(m≤50,k≤n≤50)
接下来的m行，每行有n个实数（用空格分隔开）。这就是技术人员提供的表格，其内容已经在问题中详细说明了（pij为 (0,1) 的实数 ）。
输出文件
仅一个数据，最大成功拆除的可能性（保留小数点后4位）。
输入样例
4 5 2
0.95 0.20 0.57 0.48 0.50
0.56 0.88 0.42 0.80 0.90
0.70 0.65 0.42 0.60 0.87
0.91 0.80 0.72 0.44 0.20
输出样例
0.4189
样例说明：
对应的拆除方案是：切断引爆装置1上的1号线；切断引爆装置2上的2，4号线；切断引爆装置3上的5号线；切断引爆装置4上的3号线。）
题解
乘法转对数加法后，作二分图带权最大匹配TAT
注意精度问题
|
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 |
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<set> #include<ctime> #include<vector> #include<queue> #include<algorithm> #include<map> #include<cmath> #define inf 1000000000 #define pa pair<int,int> #define ll long long #define eps 1e-8 using namespace std; double a[55][55],ans; int n,m,K,cnt=1,T; int q[105],last[105]; double d[105]; bool mark[105]; struct edge{ int to,next,v;double c; }e[100005]; void insert(int u,int v,int w,double c) { e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;e[cnt].v=w;e[cnt].c=c; e[++cnt].to=u;e[cnt].next=last[v];last[v]=cnt;e[cnt].v=0;e[cnt].c=-c; } bool spfa() { int head=0,tail=1; for(int i=0;i<=T;i++)d[i]=-inf; memset(mark,0,sizeof(mark)); q[0]=T;d[T]=0; while(head!=tail) { int now=q[head];head++;mark[now]=0; if(head==105)head=0; for(int i=last[now];i;i=e[i].next) if(d[now]+e[i^1].c>d[e[i].to]&&e[i^1].v) { d[e[i].to]=d[now]+e[i^1].c; if(!mark[e[i].to]) { mark[e[i].to]=1; q[tail++]=e[i].to; if(tail==105)tail=0; } } } return d[0]!=-inf; } int dfs(int x,int f) { mark[x]=1;if(x==T)return f; int w,used=0; for(int i=last[x];i;i=e[i].next) if(fabs(d[x]-e[i].c-d[e[i].to])<eps&&!mark[e[i].to]&&e[i].v) { w=dfs(e[i].to,min(f-used,e[i].v)); e[i].v-=w;e[i^1].v+=w; ans+=e[i].c*w; used+=w;if(used==f)return f; } return used; } void zkw() { while(spfa()) { mark[T]=1; while(mark[T]) { memset(mark,0,sizeof(mark)); dfs(0,inf); } } } int main() { scanf("%d%d%d",&m,&n,&K);T=m+n+1; for(int i=1;i<=m;i++) for(int j=1;j<=n;j++) scanf("%lf",&a[i][j]); for(int i=1;i<=m;i++) insert(0,i,K,0); for(int i=1;i<=n;i++) insert(i+m,T,1,0); for(int i=1;i<=m;i++) for(int j=1;j<=n;j++) insert(i,m+j,1,log(a[i][j])); zkw(); printf("%.4lf\n",exp(ans)); return 0; } |
OI 课件=>
