首页 > 代码库 > poj3308最小割
poj3308最小割
这题做的稀里糊涂 首先 建图不会,然后 dinic姿势不对 ,还不知道 为啥。。。。还有这尼玛怎么看出来是 最小割的
#include <cstdio>#include <cstring>#include <algorithm>#include <climits>#include <string>#include <iostream>#include <map>#include <cstdlib>#include <list>#include <set>#include <queue>#include <stack>#include<math.h>using namespace std;const double INF=1e10;const double eps=1e-9;double Map[222][222];int level[222];int s,e;double Min(double a,double b){ return a>b?b:a;}bool bfs(){ memset(level,0,sizeof(level)); queue<int> q;q.push(s); level[s]=1; while(!q.empty()){ int cur=q.front();q.pop(); for(int i=0;i<=e;i++){ if(Map[cur][i]>eps&&!level[i]){ level[i]=level[cur]+1; q.push(i); } } } return level[e];}double dfs(int x,double val){ double sum=0; if(x==e) return val; for(int i=0;i<=e;i++){ if(val>=eps&&Map[x][i]>=eps&&level[i]==level[x]+1){ double t=dfs(i,Min(val,Map[x][i])); sum+=t; val-=t; Map[x][i]-=t;Map[i][x]+=t; } } if(sum<eps) level[x]=-1;//优化 此时的层次网络 进过某点的流量为0说明 不用再更新这点了即使还有边连 return sum;}double dinic(){ double ans=0; while(bfs()) ans+=dfs(s,INF); return ans;}int main(){ int Icase; int n,m,l; scanf("%d",&Icase); while(Icase--){ scanf("%d%d%d",&m,&n,&l); memset(Map,0,sizeof(Map)); s=0;e=n+m+1; for(int i=1;i<=m;i++){ double a; scanf("%lf",&a); a=log(a); Map[s][i]=a; } for(int i=m+1;i<e;i++){ double a; scanf("%lf",&a); a=log(a); Map[i][e]=a; } for(int i=0;i<l;i++){ int a;int b; scanf("%d%d",&a,&b); b+=m; Map[a][b]=INF; } printf("%.4f\n",exp(dinic())); } return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。