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

Boleyn Su's Blog

 
 
 
 
 

日志

 
 

SDOI2009[晨跑]  

2010-07-26 14:10:07|  分类: 信息学 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

赤裸裸的最小费用流。

CODE:

/*

AUTHOR: Su Jiao

DATE: 2010-7-26

DESCRIPTION:

山东2009年省选 晨跑

*/

#include <stdio.h>

#include <string.h>

 

#define oo 0x7f7f7f7f

#define MAXEDGE 1000000

#define MAXV 1000

 

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 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;

        }

    }

    printf("%d %d\n",flow,cost);

}

 

int N,M;

int a,b,c;

int main()

{

    scanf("%d%d",&N,&M);

    top=pool;

    S=1,T=N*2,V=N*2;

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

        scanf("%d%d%d",&a,&b,&c),add_edge(a+N,b,1,c);

    add_edge(1,1+N,oo,0);

    for (int i=2;i<N;i++) add_edge(i,i+N,1,0);

    add_edge(N,N+N,oo,0);

    min_cost_flow();

}

 

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

历史上的今天

评论

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

页脚

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