POJ 3308 - Paratroopers

//Memory Time 
// 796K  47MS 

#include<iostream>
#include<cmath>
#include<queue>
using namespace std;

class Node
{
public:
    int id;
    class Node* next;
    Node():id(-1),next(0){}
};

class solve
{
public:
    solve(int n,int m,int l):N(n),M(m),L(l)
    {
        Initial();
        Input_Creat();
        Dinic();
        printf("%.4lf\n",exp(MinCost));
    }
    ~solve()
    {
        delete[] level;

        for(int i=0;i<=T;i++)
            delete[] cap[i];

        EmptyList();
    }

    double min(double a,double b) const{return a<b?a:b;}
    double inf() const{return 1e8;}
    double eps() const{return 1e-8;}
    double precision(double x) const{return fabs(x)<eps()?0:x;}

    void Initial(void);                    //申请存储空间并初始化
    void Input_Creat(void);                //输入并创建单源单汇网络

    void Dinic(void);                    //Dinic算法寻找最大流
    bool BFS(void);                        //对剩余图标号分层
    double DFS(int str,double flow);    //搜索增广链，修正最大流
                                        //str:搜索起点; flow:“关口点str”允许通过的最大流

    void AddEdge(int a,int b);            //向邻接链表加入双向弧a<->b (反向弧b->a容量默认为0)
    void DelLink(Node* p);                //释放以p为表头的整条链
    void EmptyList(void);                //释放邻接链表

protected:

    int N;                //行数(X点集)
    int M;                //列数(Y点集)
    int L;                //伞兵数量
    int S;                //超级源
    int T;                //超级汇
    Node** LinkHead;    //邻接链表表头

    double** cap;        //容量，在本题“费用”即“容量”
    int* level;            //层次图上各顶点的标号
    double MinCost;        //最小总费用

};

void solve::Initial(void)
{
    MinCost=0;
    S=0;
    T=N+M+1;

    LinkHead=new Node*[T+1];
    for(int i=0;i<=T;i++)
        LinkHead[i]=0;

    cap=new double*[T+1];
    for(int j=0;j<=T;j++)
    {
        cap[j]=new double[T+1];
        memset(cap[j],0,sizeof(double)*(T+1));    //初始化所有弧的容量为0（不连通）
    }

    level=new int[T+1];

    return;
}

void solve::Input_Creat(void)
{
    /*Temporary*/

    int i,j,k;
    double R_cost,C_cost;
    int x,y;

    /*输入行费用，构造超级源S到X点集的边*/

    for(i=1;i<=N;i++)
    {
        scanf("%lf",&R_cost);
        cap[S][i]=log(R_cost);    //正向弧容量，取对数，化乘为加
        AddEdge(S,i);
    }

    /*输入列费用，构造Y点集到超级汇T的边*/

    for(j=N+1;j<T;j++)
    {
        scanf("%lf",&C_cost);
        cap[j][T]=log(C_cost);    //正向弧容量，取对数，化乘为加
        AddEdge(j,T);
    }

    /*输入伞兵的坐标，构造X点集到Y点集的边*/

    for(k=1;k<=L;k++)
    {
        scanf("%d %d",&x,&y);
        cap[x][y+N]=inf();        //正向弧容量
        AddEdge(x,y+N);
    }

    return;
}

void solve::AddEdge(int a,int b)
{
    /*正向弧部分*/

    if(!LinkHead[a])
        LinkHead[a]=new Node;

    Node* p1=LinkHead[a]->next;
    Node* pa=new Node;
    pa->id=b;
    pa->next=p1;
    LinkHead[a]->next=pa;

    /*反向弧部分*/

    if(!LinkHead[b])
        LinkHead[b]=new Node;

    Node* p2=LinkHead[b]->next;
    Node* pb=new Node;
    pb->id=a;
    pb->next=p2;
    LinkHead[b]->next=pb;

    return;
}

void solve::Dinic(void)
{
    while(BFS())
        MinCost+=DFS(S,inf());

    return;
}

bool solve::BFS(void)
{
    for(int i=S;i<=T;i++)
        level[i]=-1;

    queue<int>q;
    q.push(S);
    level[S]=0;

    while(!q.empty())
    {
        int a=q.front();
        if(LinkHead[a])
        {
            for(Node* p=LinkHead[a]->next;p;p=p->next)
            {
                int b=p->id;
                if(level[b]==-1 && precision(cap[a][b])>0)
                {
                    q.push(b);
                    level[b]=level[a]+1;
                }
            }
        }
        q.pop();
    }
    return level[T]!=-1;
}

double solve::DFS(int str,double flow)
{
    if(str==T)
        return flow;
                        //假设关口点str有多个分支
    double SubFlow=0;    //则SubFlow为前k个分支允许通过的最大流之和
                        //flow-SubFlow即为str能够给余下的分支所提供的最大流量之和

    if(LinkHead[str])
    {
        for(Node* p=LinkHead[str]->next;p;p=p->next)
        {
            int end=p->id;
            /*注意不能“跨层”搜索*/
            if(level[end]==level[str]+1 && precision(cap[str][end])>0)
            {
                double AdjustFlow=DFS(end,min(flow-SubFlow,cap[str][end]));
                SubFlow+=AdjustFlow;

                cap[str][end]-=AdjustFlow;    //正向弧容量修正
                cap[end][str]+=AdjustFlow;    //反向弧容量修正
            }
        }
    }

    return SubFlow;
}

void solve::DelLink(Node* p)
{
    if(p->next)
        p=p->next;
    delete[] p;
    return;
}

void solve::EmptyList(void)
{
    for(int i=1;i<=N;i++)
        if(LinkHead[i])
            DelLink(LinkHead[i]);
    return;
}

int main(void)
{
    int test;
    scanf("%d",&test);
    for(int t=1;t<=test;t++)
    {
        int n,m,l;
        scanf("%d %d %d",&n,&m,&l);
        solve poj3308(n,m,l);
    }
    return 0;
}