【网络流】 HDU 3157 Crazy Circuits 有源汇上下界最小流-白红宇

【网络流】 HDU 3157 Crazy Circuits 有源汇上下界最小流

阅读量：4306 次

发布时间：2019-06-06

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

最小流解法：先按照【上下界可行流】建图但先不建end --> star 边

MAXFlow=按新建的源点和汇点跑一次最大流

再建end->star的边

MAXFlow+=再按新建的源点和汇点跑一次最大流

如果MAXFlow == 新建源点流出的sum值

则有ans = end->star的流量

否则无ans

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            using namespace std;#include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 #include 
                  
                   ;#define cler(arr, val) memset(arr, val, sizeof(arr))#define FOR(i,a,b) for(int i=a;i<=b;i++)#define IN freopen ("in.txt" , "r" , stdin);#define OUT freopen ("out.txt" , "w" , stdout);typedef long long LL;const int MAXN = 100;const int MAXM = 1500;const int INF = 0x3f3f3f3f;//const int INF = 22222;const int mod = 1000000007;struct Edge{ int to,next,cap,flow;} edge[MAXM];int tol,head[MAXN];int gap[MAXN],dep[MAXN],cur[MAXN];void init(){ tol=0; cler(head,-1);}void addedge(int u,int v,int w,int rw=0){ edge[tol].to=v,edge[tol].cap=w,edge[tol].flow=0,edge[tol].next=head[u]; head[u]=tol++; edge[tol].to=u,edge[tol].cap=rw,edge[tol].flow=0,edge[tol].next=head[v]; head[v]=tol++;}int Q[MAXN];void BFS(int star,int end){ cler(dep,-1); cler(gap,0); gap[0]=-1; int front= 0, rear = 0; dep[end]=0; Q[rear++] = end; while(front!= rear) { int u=Q[front++]; for(int i = head[u]; i!=-1; i=edge[i].next) { int v=edge[i].to; if(dep[v]!= -1) continue; Q[rear++]= v; dep[v]=dep[u]+1; gap[dep[v]]++; } }}int S[MAXN];int sap(int star,int end,int N){ BFS(star,end); memcpy(cur,head,sizeof(head)); int top=0, u=star,ans=0; while(dep[star]
                   
                    edge[S[i]].cap-edge[S[i]].flow) { Min=edge[S[i]].cap-edge[S[i]].flow; inser=i; } for(int i=0; i
                    
                     0) { addedge(Star,i,low[i]); sum+=low[i]; } else addedge(i,End,-low[i]); } int maxflow=sap(Star,End,n+4); addedge(end,star,INF); maxflow+=sap(Star,End,n+4); if(maxflow!=sum) printf("impossible\n"); else printf("%d\n",edge[tol-2].flow); } return 0;}