POJ1273 最大流模板题_Edmonds_Karp_kk303的博客-程序员秘密

赤果果的网络流...模板题...唯一要留意的是一条边可能会给出多次容量..所以每次都要加起来才是这条边的流量...用Edmonds_Karp写的:

/*
    POJ1273 最大流模板题. Edmonds_Karp  
*/
#include<iostream>
#include<queue>
using namespace std;
queue<int> Myqueue;
int NumOfPoint,NumOfLine,Network[210][210],pre[210];
int GetMin(int a,int b)
{
    if (a<b) return a; else return b;
}
int BFS()
{
    bool used[210];
    int i,NowPoint,Flow[210];
    memset(Flow,-1,sizeof(Flow));
    memset(used,0,sizeof(used));
    while (!Myqueue.empty()) Myqueue.pop();
    Myqueue.push(1); Flow[1]=1<<30; pre[1]=1;
    while (!Myqueue.empty())
    {
        NowPoint=Myqueue.front();
        Myqueue.pop();
        for (i=1;i<=NumOfPoint;i++)
         if ( !used[i] && Network[NowPoint][i] ) // 每次广搜..每个点只use一次..!
         {
              Flow[i]=GetMin ( Flow[NowPoint] , Network[NowPoint][i] );
              used[i]=true;
              pre[i]=NowPoint;           
              Myqueue.push(i);       
         }        
    }   
    if (Flow[NumOfPoint]==-1) return 0; 
    return Flow[NumOfPoint];
}
int Edmonds_Karp()
{
    int i,MinFlow,ans=0;
    while (MinFlow=BFS())
    {
        ans+=MinFlow;  
        int NowPoint=NumOfPoint,PrePoint;
        while (NowPoint!=1)
        {
            PrePoint=pre[NowPoint];
            Network[PrePoint][NowPoint]-=MinFlow;
            Network[NowPoint][PrePoint]+=MinFlow;
            NowPoint=PrePoint;    
        }
    }    
    return ans;
}  
int main()
{
    freopen("1458.in","r",stdin);
    freopen("1458.out","w",stdout);
    while (scanf("%d%d",&NumOfLine,&NumOfPoint)!=EOF)
    {
      int x,y,R;  
      memset(Network,0,sizeof(Network));
      for (int i=1;i<=NumOfLine;i++) 
      {
          scanf("%d%d",&x,&y);
          scanf("%d",&R);  
          Network[x][y]+=R;
      } 
      printf("%d\n",Edmonds_Karp());
    }    
    return 0;   
}

本文链接：https://blog.csdn.net/kk303/article/details/6707736

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

知道防火墙是什么吗？WAF (web application Firewall)防火墙原理及其简单绕过_AAAAAAAAAAAA66的博客-程序员秘密

不会吧，不会吧，不会还有人没听过防火墙吧？~~听过是一回事，但了不了解又是另外一会事了，在我小时候，家里电脑刚买，对电脑那是相当的’爱护‘，每次开机都得克制我玩游戏的强烈欲望，先用对电脑进行杀毒，那免不了天天和360安全卫士打交道，凡是联了网，它就会显示防火墙已开启。（其实360也有着作为防火墙的功能）这样就应该是我认识防火墙这个词的过程的过程，不过真正的仔细了解还是在若干年后的大学了，计算机专业说不知道防火墙就有点说不过去了。偷偷问一句，你们还用360不？目录简介防火墙的类型1

关于vue中滚动监听失效问题_weixin_30548917的博客-程序员秘密

在vue项目中,监听window滚动失效;并且document.body.scrollTop一直是0的情况!查找了许多资料;并没有找到合理的解决方案;最中发现,在index.html设置了html,body的宽高设置成了100%;这样会造成window.onscroll监听不到正确的滚出高度(恒为0);不和你们多bb:解决方案:将html,body的height设...

一起Talk Android吧（第五百零七回：图片滤镜ImageFilterView)_android图片滤镜_talk_8的博客-程序员秘密

本章回中主要介绍了ImageFilterView组件的功能和用法。这些功能包含：滤镜、圆角、旋转、缩放和平移。

L2-002 链表去重（25 分）_码奴生来就只知道前进的博客-程序员秘密

L2-002 链表去重（25 分）给定一个带整数键值的单链表L，本题要求你编写程序，删除那些键值的绝对值有重复的结点。即对任意键值K，只有键值或其绝对值等于K的第一个结点可以被保留。同时，所有被删除的结点必须被保存在另外一个链表中。例如：另L为21→-15→-15→-7→15，则你必须输出去重后的链表21→-15→-7、以及被删除的链表-15→15。输入格式：输入第一行包含链表第一个结...

ubuntu 12.04 无法连接无线网络驱动问题解决_zlp1992的博客-程序员秘密

自己的Ubuntu 12.04 无法连接无线，也无法搜索到可用的无线网络，使用系统设置->附加驱动里查找对应的驱动，找到 Broadcom STA 无线驱动没有激活，如下：于是点击 "激活"，等待一段时间提示对不起,这个驱动的安装失败了，查看日志 /var/log/jockey.log 网上查找使用命令，比如 sudo apt-get install --reinstall bcm

AVL树--单旋转、双旋转与实现_avl树双旋_iEucliwood的博客-程序员秘密

AVL树AVL（Adelson-Velskii andLandis）树是带有平衡条件的二叉查找树。必须保证树的深度是。最简单的想法是要求左右子树具有相同的高度。另一种平衡条件是要求每个节点都必须要有相同高度的左子树和右子树。如果空子树的高度定义为-1（通常就是这么定义的），那么只有具有个节点的理想平衡树（perfectly balanced tree）满足这个条件。因此虽然这种平衡条件保证了树的深度小，但是它太严格，难以使用需要放...