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

一个蒟蒻的代码回收站

最后一次省选求rp

 
 
 

日志

 
 

最大流模板(ISAP)(邻接矩阵)  

2014-02-24 15:00:00|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

#include<cstdio>

#include<iostream>

using namespace std;


#define maxn 1010

#define INF 2147483647


int pre[maxn],hash[maxn]; //pre[i]:到i的上次的弧 hash[i]:顶标为i的点有几个(gap) 

int d[maxn],w[maxn],p[maxn]; //d[i]:顶标 p[i]:当前弧优化 w[i]:到点i的最大流(模拟递归用) 

int map[maxn][maxn]; //map:邻接矩阵 

int n,m,ans,flow;

bool flag;


int main()

{

    scanf("%d%d",&m,&n);

    for (int i=1;i<=m;i++)

    {

        int a,b,c;

        scanf("%d%d%d",&a,&b,&c);

        map[a][b]+=c;

    }

    for (int i=1;i<=n;i++) p[i]=1;

    hash[0]=n;

    int i=1;

    flow=INF;

    while (d[1]<n)

    {

        w[i]=flow;

        flag=false;

        for (int j=p[i];j<=n;j++)

        {

            if (map[i][j]>0 && d[i]==d[j]+1)

            {

                flag=true;

                p[i]=j;

                flow=min(flow,map[i][j]);

                pre[j]=i;

                i=j;

                if (i==n)

                {

                    ans +=flow;

                    while (i!=1)

                    {

                        int tmp=i;

                        i=pre[i];

                        map[i][tmp]-=flow;

                        map[tmp][i]+=flow;

                    }

                    flow=INF;

                }

                break;

            }

        }

        if (flag) continue;

        int MIN = n-1,adv=0;

        for (int j=1;j<=n;j++)

        if (map[i][j]!=0 && d[j]<MIN)

        {

            MIN=d[j];

            adv=j;

        }

        p[i]=adv;

        hash[d[i]]--;

        if (hash[d[i]]==0) break;

        d[i]=MIN+1;

        hash[d[i]]++;

        if (i!=1)

        {

            i=pre[i];

            flow=w[i];

        }

    }

    printf("%d\n",ans);

    return 0;

}


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

历史上的今天

评论

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

页脚

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