【POJ 2987】Firing （最小割-最大权闭合子图）

裁员

【问题描述】

在一个公司里，老板发现，手下的员工很多都不务正业，真正干事员工的没几个，于是老板决定大裁员，每开除一个人，同时要将其下属一并开除，如果该下属还有下属，照斩不误。给出每个人的贡献值和从属关系，求在最大贡献值的前提下最小剩下多少人及最大贡献值。留下多少人无所谓，现在老板想知道留下的人最大的贡献值是多少。

【输入描述】

    第一行两个整数n,m，表示有多少个员工与多少个从属关系。

第二行n个整数，表示每个员工的贡献值。

接着m行，每行两个数x,y，表示x是y的下属,一个员工可能有多个下属但不会有多个上司

【输出描述】

包括两个数，表示最大贡献值前提下最小剩下多少人及最大贡献值和。

【其他说明】：

0 < n ≤ 5000

0 ≤ m ≤ 60000

员工价值≤107

样例中留下4,5号员工是最好情况

【分析】

　　最大权闭合子图。

　　假设每个正权的人都留着，然后求最少要减掉多少（即还裁掉多少正权的人，雇佣多少负权的人才能满足情况）

　　所以对于w[i]>0的i add(st,i,w[i])

　　　　对于w[i]|<0 的i add(i,ed,-w[i])

　　原图 x->y add(s,y,INF)

　　然后求最小割。

　　但是这题要最大流的情况下，点数最小。这个不是很懂明天再说吧= =

　　我看别人是dfs的，然后我也dfs了。

　　还有什么厉害的放大边权的方法（其实之前已经领教过一次了）ORZ。。。

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #include<queue>

 using namespace std;

 #define Maxn 5010

 #define Maxm 60010

 #define INF 0xfffffff

 #define LL long long

 struct node

 {

     LL x,y,f,o,next;

 }t[Maxm*];LL len;

 LL first[Maxn];

 void ins(LL x,LL y,LL f)

 {

     t[++len].x=x;t[len].y=y;t[len].f=f;

     t[len].next=first[x];first[x]=len;t[len].o=len+;

     t[++len].x=y;t[len].y=x;t[len].f=;

     t[len].next=first[y];first[y]=len;t[len].o=len-;

 }

 LL mymin(LL x,LL y) {return x<y?x:y;}

 LL w[Maxn],st,ed;

 LL dis[Maxn];

 queue<LL > q;

 bool bfs()

 {

     while(!q.empty()) q.pop();

     memset(dis,-,sizeof(dis));

     q.push(st);dis[st]=;

     while(!q.empty())

     {

         LL x=q.front();

         for(LL i=first[x];i;i=t[i].next) if(t[i].f>)

         {

             LL y=t[i].y;

             if(dis[y]==-)

             {

                 dis[y]=dis[x]+;

                 q.push(y);

             }

         }

         q.pop();

     }

     if(dis[ed]==-) return ;

     return ;

 }

 LL ffind(LL x,LL flow)

 {

     if(x==ed) return flow;

     LL now=;

     for(LL i=first[x];i;i=t[i].next) if(t[i].f>)

     {

         LL y=t[i].y;

         if(dis[y]==dis[x]+)

         {

             LL a=ffind(y,mymin(flow-now,t[i].f));

             t[i].f-=a;

             t[t[i].o].f+=a;

             now+=a;

         }

         if(now==flow) break;

     }

     if(now==) dis[x]=-;

     return now;

 }

 LL max_flow()

 {

     LL ans=;

     while(bfs())

     {

         ans+=ffind(st,INF);

     }

     return ans;

 }

 bool vis[Maxn];

 void dfs(LL x)

 {

     vis[x]=;

     for(LL i=first[x];i;i=t[i].next) if(!vis[t[i].y]&&t[i].f>)

         dfs(t[i].y);

 }

 int main()

 {

     LL n,m;

     LL ans=,sum=;

     scanf("%lld%lld",&n,&m);

     for(LL i=;i<=n;i++) {scanf("%lld",&w[i]);if(w[i]>) ans+=w[i];}

     st=n+,ed=st+;

     for(LL i=;i<=m;i++)

     {

         LL x,y;

         scanf("%lld%lld",&x,&y);

         ins(x,y,INF);

     }

     for(LL i=;i<=n;i++) if(w[i]>) ins(st,i,w[i]);

     for(LL i=;i<=n;i++) if(w[i]<) ins(i,ed,-w[i]);

     LL fl=max_flow();

     ans-=fl;

     memset(vis,,sizeof(vis));

     dfs(st);

     for(LL i=;i<=n;i++) if(vis[i]) sum++;

     printf("%lld %lld\n",sum,ans);

     return ;

 }

放点不是我写的，比我可信的最大权闭合子图解释

1、本题某些东西的解释

2、最大权闭合子图

【POJ 2987】Firing （最小割-最大权闭合子图）-LMLPHP

3、ORZ 胡伯涛

2016-11-03 22:00:24

好困Zzz...