spoj1476 maximum profit,最大权闭合子图 - c++编程基础

最大权闭合子图：点权之和最大的闭合图。

建图：每一条有向边变为容量为inf，源S到正权点v( wv>0 )的边容量 wv ，负权点v( wv<0 )到汇 T 的边容量 ?wv ，零权点v( wv=0 )不与源和汇相连。然后求最小割(SUM-最大流)即为答案。

/*
 * Author: yew1eb
 * Created Time:  2014年10月31日 星期五 15时39分22秒
 * File Name: spoj1476 maximum profit.cpp
 */
#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include 
             
               #include
               using namespace std; typedef long long ll; const int inf = 1e9; const ll INF = 1e18; const double eps = 1e-8; const double pi = acos(-1.0); const int maxn = 60010; const int maxm = 2000010; struct Edge { int to, cap, next; Edge(int _next=0,int _to=0,int _cap=0):next(_next),to(_to),cap(_cap) {} } edge[maxm]; int n, m, S, T, cnt; int head[maxn], tot; int d[maxn];//到汇点的距离下界。 int gap[maxn]; void init() { tot = 0; memset(head, -1, sizeof head ); } void add(int u,int v,int c, int rc=0) { edge[tot] = Edge(head[u], v, c); head[u] = tot++; edge[tot] = Edge(head[v], u, rc); head[v] = tot++; } int get_flow(int u, int flow) { if(u==T || flow==0)return flow; int res=0, f; for(int i=head[u]; ~i; i=edge[i].next) { int &v = edge[i].to; if(d[u]>d[v] && (f=get_flow(v,min(flow,edge[i].cap)))>0) { edge[i].cap -= f; edge[i^1].cap += f; res += f; flow -= f; if(flow==0) return res; } } if(!(--gap[d[u]]))d[S]=cnt+2; gap[++d[u]]++; return res; } int isap() { int flow = 0; memset(gap, 0, sizeof gap ); memset(d, 0, sizeof d ); cnt = T-S+1; gap[0] = cnt; while(d[S]
               
                ?