POJ2987 Firing 最大权闭合图-白红宇

POJ2987 Firing 最大权闭合图

阅读量：4677 次

发布时间：2019-06-09

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

详情请参考http://www.cnblogs.com/kane0526/archive/2013/04/05/3001557.html

值得注意的地方，割边会把图分成两部分，一部分和起点相连，另一部分和汇点相连

我们只需要关注和起点相连的点的点就好，如何统计呢？

只需要从起点开始搜索，只要边不是满流，一直搜就好

然后，答案就是总权值-最小割

注：对于dinic网络流，我还是喜欢LRJ白书上的，用起来方便

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            #include 
             
              #include 
              
               using namespace std;typedef long long LL;const int N = 20;const int INF = 0x3f3f3f3f;const LL mod = 1e9+7;const int maxn=5e3+5;struct Edge{ int from,to,cap,flow; Edge(int u,int v,int c,int d):from(u),to(v),cap(c),flow(d) {}};struct dinic{ int s,t; vector
               
                edges; vector
                
                 G[maxn]; int d[maxn]; int cur[maxn]; bool vis[maxn]; void init(){ for(int i=0;i

q; q.push(s); d[s]=0; vis[s]=1; while(!q.empty()) { int x=q.front(); q.pop(); for(int i=0; i

e.flow) { vis[e.to]=1; d[e.to]=d[x]+1; q.push(e.to); } } } return vis[t]; } int dfs(int x,int a) { if(x==t||a==0)return a; int flow=0,f; for(int &i=cur[x]; i

s=s; this->t=t; LL flow=0; while(bfs()) { memset(cur,0,sizeof(cur)); flow+=dfs(s,INF); } memset(vis,false,sizeof(vis)); return flow; } void addedge(int u,int v,int c) { Edge x(u,v,c,0),y(v,u,0,0); edges.push_back(x); edges.push_back(y); int l=edges.size(); G[u].push_back(l-2); G[v].push_back(l-1); } int search(int u){ int ret=1;vis[u]=true; for(int i=0;i

0)sum+=w,solve.addedge(0,i,w); else if(w<0)solve.addedge(i,n+1,-w); } for(int i=0;i

View Code

转载于:https://www.cnblogs.com/shuguangzw/p/5719525.html

你可能感兴趣的文章