首页 > 代码库 > poj Firing(最大权闭合图)

poj Firing(最大权闭合图)

                                                                              Firing   

 

题目:

   要解雇一些人,而解雇的这些人如果人跟他有上下级的关系,则跟他有关系的人也要一起解雇。每个人都会创造一定的价值,要求你求出在最大的获利下,解雇的人最小。

 

算法分析:

   在这之前要知道一个定理:

     最小割 = 最大流

   一道最大权闭合图的裸题,而这又可以转换成最小割来求解。证明可以看2007年胡伯涛的论文则可以直接套出模板,没看过的最好去看一下,那里解释的清楚。这里我给出他的原文的一些构造方法。

增加源s汇t
源s连接原图的正权点,容量为相应点权
原图的负权点连接汇t,容量为相应点权的相反数
原图边的容量为正无限.

 

 

而这里其实最难的是第一问。而由于本人的实力有限。所以,难以解释清楚。但是网上流传的该题解题报告的人很少有解释清的,都是一笔带过。找了好久才找到了一篇正确的解释。下面给出解释。

////////////////////////////////////////////////////////////////

 

标准的最大权闭合图,构图:从源点s向每个正收益点连边,容量为收益;从每个负收益点向汇点t连边,容量为收益的相反数;对于i是j的上司,连边i->j,容量为inf。最大收益 = 正收益点权和 - 最小割 = 正收益点权和 - 最大流(胡波涛论文上有证明)。这题的关键是如何在最小割的前提下求出最少的割边数目,可以从源点对残量网络进行一次DFS,每个割都会将源汇隔开,所以从源点DFS下去一定会因为碰到某个割而无法前进,用反证法易知这时遍历过的点数就是S集的最少点数。

/////////////////////////////////////////////////////////////////

 

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstdio>
#include <cstring>
using namespace std;

typedef long long LL;
const int MAXN = 5000 + 10;
const LL INF = (1LL) << 60;       //必须(1LL)!!!!!!!!!!!!!!!!!!!!  T_T......
struct Edge{
   int from,to;
   LL cap,flow;
   Edge(){};
   Edge(int _f,int _t,LL _c,LL _fw)
        :from(_f),to(_t),cap(_c),flow(_fw){};
};

vector<Edge> edges;
vector<int> G[MAXN];
bool vst[MAXN];
int d[MAXN],cur[MAXN];
int V,E,S,T;
int cnt;         //最少割边数
LL ans,sum;

void clr(){
    ans = sum = 0;
    S = 0; T = V + 1;
    for(int i = 0;i <= V;++i)
        G[i].clear();
    edges.clear();
}

void addEdge(int f,int t,LL cap){
    edges.push_back(Edge(f,t,cap,0));
    edges.push_back(Edge(t,f,0,0));
    int sz = edges.size();
    G[f].push_back(sz - 2);
    G[t].push_back(sz - 1);
}

void init(){
    LL x;
    for(int i = 1;i <= V;++i){
        scanf("%I64d",&x);
        if(x > 0){
            addEdge(S,i,x);
            sum += x;
        } else {
           addEdge(i,T,-x);
        }
    }

    int a,b;
    for(int i = 0;i < E;++i){
        scanf("%d%d",&a,&b);
        addEdge(a,b,INF);
    }
}

bool BFS(){
   memset(vst,0,sizeof(vst));
   queue<int> Q;
   Q.push(S);
   d[S] = 0;
   vst[S] = 1;

   while(!Q.empty()){
      int x = Q.front();  Q.pop();
      for(int i = 0;i < (int)G[x].size();++i){
          Edge& e = edges[G[x][i]];
          if(!vst[e.to] && e.cap > e.flow){
              vst[e.to] = 1;
              d[e.to] = d[x] + 1;
              Q.push(e.to);
          }
      }
   }

   return vst[T];
}

LL DFS(int x,LL a){
   if(x == T||a == 0)
      return a;


   LL flow = 0,f;
   for(int& i = cur[x];i < (int)G[x].size();++i){
       Edge& e = edges[G[x][i]];
       if(d[x] + 1 == d[e.to]&&(f = DFS(e.to,min(a,e.cap - e.flow))) > 0){
           e.flow += f;
           edges[G[x][i]^1].flow -= f;
           flow += f;
           a -= f;
           if(a == 0) break;
       }
   }
   return flow;
}

LL Maxflow(){
   LL flow = 0;
   while(BFS()){
       memset(cur,0,sizeof(cur));
       flow += DFS(S,INF);
   }

   return flow;
}

//求解在最小割的前提下,得最好割边
void dfs(int u){
   vst[u] = 1;
   for(int i = 0;i < (int)G[u].size();++i){
      Edge& e = edges[G[u][i]];
      if(!vst[e.to] && e.cap > e.flow){
         cnt++;
         dfs(e.to);
      }
   }
}

void solve(){

    LL ans = sum - Maxflow();

    cnt = 0;
    memset(vst,0,sizeof(vst));
    dfs(S);

    printf("%d %I64d\n",cnt,ans);
}

int main()
{
   // freopen("Input.txt","r",stdin);

    while(~scanf("%d%d",&V,&E)){
        clr();
        init();

        solve();
    }
    return 0;
}


 

poj Firing(最大权闭合图)