注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Boleyn Su's Blog

 
 
 
 
 

日志

 
 

[The 2009 ACM-ICPC Asia Harbin Regional Contest]D.Gold Mines  

2012-04-08 17:11:37|  分类: 信息学 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

最小费用流。

CODE:

#include <iostream>

#include <algorithm>

#include <string>

#include <cstring>

#include <cassert>

using namespace std;

 

#define oo 0x7f7f7f7f

#define MAXEDGE 510000

#define MAXV 1002

 

typedef struct struct_edge* edge;

struct struct_edge{int v,c,d;edge n,b;};

struct_edge pool[MAXEDGE];

edge top;

int S,T,V;

edge adj[MAXV];

int q[MAXV];

bool inq[MAXV];

int head,tail;

edge p[MAXV];

int d[MAXV];

void add_edge(int u,int v,int c,int d)

{

     top->v=v,top->c=c,top->d=d,top->n=adj[u],adj[u]=top++;

     top->v=u,top->c=0,top->d=-d,top->n=adj[v],adj[v]=top++;

     adj[u]->b=adj[v];

     adj[v]->b=adj[u];

}

int min_cost_flow(int n,int t)

{

    int flow=0,cost=0;

    for (;;)

    {

        memset(d,oo,sizeof(d));

        inq[q[head=tail=0]=S]=true;

        d[S]=0;

        p[S]=0;

        while (head<=tail)

        {

              int u;

              inq[u=q[(head++)%MAXV]]=false;

              for (edge i=adj[u];i;i=i->n)

                  if (i->c&&d[i->v]>d[u]+i->d)

                  {

                     if (!inq[i->v])

                        inq[q[(++tail)%MAXV]=i->v]=true;

                     d[i->v]=d[u]+i->d;

                     p[i->v]=i;

                  }

        }

        if (d[T]==oo) break;

        else

        {

            int delta=oo;

            for (edge i=p[T];i;i=p[i->b->v])

                if (delta>i->c) delta=i->c;

            for (edge i=p[T];i;i=p[i->b->v])

                i->c-=delta,i->b->c+=delta;

            flow+=delta;

            cost+=d[T]*delta;

        }

    }

    if (flow!=n) return 1+t;

    return cost;

}

 

int E;

int u[MAXEDGE],v[MAXEDGE];

int n;

int mine[MAXV];

int price[MAXV];

bool source[MAXV];

int total_price;

int result(int t)

{

    if (t)

    {

       int answer=-1,i=0;

       if (t==n)

       {

           source[0]=true;

           int get=result(t-1);

           if (get>answer) answer=get;

           source[0]=false;

       }

       else

       {

           int k=n-t;

           while (k) if (source[i++]) k--;

           while (i<n*2)

           {

              if (!source[i])

              {

                  source[i]=true;

                  int get=result(t-1);

                  if (get>answer) answer=get;

                  source[i]=false;

              }

              i++;

           }

       }

       return answer;

    }

    else

    {

       memset(adj,0,sizeof(adj));

       top=pool;

       S=V+V,T=V+V+1;

       for (int i=0;i<E;i++)

           add_edge(u[i]+V,v[i],1,0),

           add_edge(v[i]+V,u[i],1,0);

       for (int i=0;i<V;i++)

           add_edge(i,i+V,1,price[i]);

       for (int i=0;i<n*2;i++)

           if (source[i]) add_edge(S,mine[i],1,0);

           else add_edge(mine[i]+V,T,1,0);

       return total_price-min_cost_flow(n,total_price);

    }

}

 

int main()

{

    int T;

    cin>>T;

    for (int t=0;t<T;t++)

    {

       cin>>V>>E;

       for (int i=0;i<E;i++)

           cin>>u[i]>>v[i];

       cin>>n;

       for (int i=0;i<n*2;i++) cin>>mine[i];

       total_price=0;

       for (int i=0;i<V;i++) cin>>price[i],total_price+=price[i];

       cout<<result(n)<<endl;

    }

}

 

  评论这张
 
阅读(1135)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018