首页 > 代码库 > 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;}