poj1087最小割-白红宇

poj1087最小割

阅读量：5226 次

发布时间：2019-06-14

本文共 1167 字，大约阅读时间需要 3 分钟。

最大流最小割定理：移除最小边集使网络流中断的集值等于这个网络的最大流。

建图：第一个cpu 流向第i的模块的流量为ai ，第i个模块流向第二个cpu的流量为 bi 。模块之间连边 a->b= w b->a=w。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 using namespace std;int s;int en;int n;int m;struct edge{ int to;int val;int next;int op;}e[1111111];const int INF=0xfffffff;int Min(int a,int b){ return a>b?b:a;}int len;int head[111111];int level[111111];void add(int from,int to,int val){ e[len].val=val;e[len].to=to;e[len].next=head[from];e[len].op=len+1; head[from]=len++; e[len].val=0;e[len].to=from;e[len].next=head[to];e[len].op=len-1; head[to]=len++;}bool bfs(){ for(int i=0;i

q; q.push(s); while(!q.empty()){ int cur=q.front(); q.pop(); for(int i=head[cur];i!=-1;i=e[i].next){ if(!e[i].val) continue; int cc=e[i].to; if(!level[cc]){ level[cc]=level[cur]+1; q.push(cc); } } } return level[en];}int dfs(int x,int val){ int tem=val; if(x==en) return val; for(int i=head[x];i!=-1&&tem;i=e[i].next){ if(!e[i].val) continue; int cc=e[i].to; // cout<

<<" "<

转载于:https://www.cnblogs.com/yigexigua/p/3884837.html

你可能感兴趣的文章