beloved_ACM

SB,NB,都是一个B.
posts - 29, comments - 2, trackbacks - 0, articles - 0
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

POJ_2987 最大权闭合图

Posted on 2010-09-30 19:50 成幸毅 阅读(553) 评论(0)  编辑 收藏 引用

   建模很简单,设置源点连接正权点,边权为该点值,负权点连接汇点,边权点为该点的绝对值,输入的边权值设为INF,然后求最大流,然后让正权点值的累加和减去最大流就是闭合图的最大权。《最小割模型在信息学竞赛中的应用》有详细的证明。

#include <iostream>
using namespace std;

const int N=20010;
int NN;
const int MAXE=200010;
const int INF=1<<30;
int head[N];
int u,v;
int value; 
int e[N];
bool tnt[N];

struct Edge
{
    
int v,next,w;
}
edge[MAXE * 5];

int cnt,n,m,s,t;

void addedge(int u,int v,int w)
{
    edge[cnt].v
=v;
    edge[cnt].w
=w;
    edge[cnt].next
=head[u];
    head[u]
=cnt++;
    edge[cnt].v
=u;
    edge[cnt].w
=0;
    edge[cnt].next
=head[v];
    head[v]
=cnt++;
}

__int64 sap()
{   
    memset(e,
0,sizeof(e));
    
int pre[N],cur[N],dis[N],gap[N];
    __int64 flow
=0,aug=INF,u;
    
bool flag;
    
for(int i=0;i<=NN;i++)
    
{
        gap[i]
=dis[i]=0;
    }

    gap[s]
=NN;
    u
=pre[s]=s;
    
while(dis[s]<NN)
    
{
        flag
=0;
        
for(int j= head[u];j!=-1;j=edge[j].next)  
        
{
            
int v=edge[j].v;
            
if(edge[j].w>0&&dis[u]==dis[v]+1)
            
{
                flag
=1;
                
if(edge[j].w<aug) aug=edge[j].w;
                e[u] 
= j;
                pre[v]
=u;
                u
=v;
                
if(u==t)
                
{
                    flow
+=aug;
                    
while(u!=s)
                    
{
                        u
=pre[u];
                        edge[e[u]].w
-=aug;
                        edge[e[u]
^1].w+=aug;
                    }

                    aug
=INF;
                }

                
break;
            }

        }

        
if(flag)
            
continue;
        
int mindis=NN;
        
for(int j=head[u];j!=-1;j=edge[j].next)
        
{
            
int v=edge[j].v;
            
if(edge[j].w>0&&dis[v]<mindis)

            
{
             mindis
=dis[v];
             e[u]
=j;
            }

        }

        
if((--gap[dis[u]])==0)
            
break;
       gap[dis[u]
=mindis+1]++;
       u
=pre[u];
    }

    
return flow;
}


void dfs(int u) {
    
    
if(u == t) return;
    tnt[u] 
= true;
    
for(int addr = head[u]; addr != -1; addr = edge[addr].next) {
       
if(edge[addr].w > 0 && !tnt[edge[addr].v])
          dfs(edge[addr].v);
    }
 
}


int main() {
   
   
while(scanf("%d%d",&n,&m) != EOF) {
      memset(head,
-1,sizeof(head));
      memset(tnt,
0,sizeof(cnt));
      s 
= 0,t = n+1;
      NN 
= t+1;
      __int64 sum  
= 0;
      
int tot = 0;
      
for(int i = 1; i <= n; i++
         scanf(
"%d",&value);
         
if(value <= 0{
            addedge(i,t,
-value);
         }

         
else  {
            addedge(s,i,value);
            sum 
+= value;
         }

      }

      
      
for(int j = 1; j <= m; j++{
         scanf(
"%d%d",&u,&v);
         addedge(u,v,INF);
      }
 
      
      __int64 ans 
= sap();
      
      dfs(
0);
      
for(int i = 1; i <= n; i++{
         
if(tnt[i])
           tot
++;
      }

      printf(
"%d %I64d\n",tot,sum - ans);
      
   }

  
// system("pause");
   return 0;
}



 


 


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理