MYF

POJ 2987 Firing

Posted on | In | | Visitors

题目链接

POJ 2987

方法：网络流最大权闭合图

题目分析

题目大意

老板要裁员，他有若干个员工，已知裁每一个员工的损失/获益，但是裁一个领导的话，就必须要把他的所有下属都裁掉，问当老板获得的收益最大时，要裁掉几个人，获得的收益是多少？

解析

网上找最大权闭合图的问题时搜到的这个题。

将图构造出来，发现每一个点的后继节点都在图中，所以这个图是一个最大权闭合图。我们希望选择一些点，使这些点权之和最大，但是选择一些点的话会产生一些选择这些点的花费，也就是会说，如果你裁一个领导，可能获益为正，但是你必须要同时把这个领导的下属给裁掉，可能产生负的利益。这样转化为了一个最大权闭合图的问题，建立一个超级源点，一个超级汇点，所有正权的点连接源点s，负权的点连接汇点t，对于每一对(领导，下属)关系，我们建立两者之间的流量为正无穷，从领导指向下属，求出这个图的最优解。最优解很明显 = 所有正权顶点的权值之和 － 不选的正权顶点的权值和 － 选择这些正权顶点的总费用。当对于我们建的图求最小割时，求的即为（不选的正权顶点权值和 ＋ 选择这些正权顶点的总费用）

参考题解：

注意要用long long

代码

dinic解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <string>
#include <vector>
#include <iomanip>
#include <bitset>
#include <cstring>
#include <iostream>
#include <iosfwd>
#include <deque>
#include <algorithm>
#define Memset(a,val) memset(a,val,sizeof(a))
#define PI acos(-1.0)
#define PB push_back
#define MP make_pair
#define rt(n)       (i == n ? '\n' : ' ')
#define hi         printf("Hi----------\n")
#define IN freopen("input.txt","r",stdin);
#define OUT freopen("output.txt","w",stdout);
#define debug(x) cout<<"Debug : >>>"<<x<<"<<<"<<endl;
#define debug2(x,y) cout<<"Debug : >>>"<<x<<" , "<<y<<"<<<"<<endl;
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
typedef pair<int,int> PII;
typedef long long ll;
const int mod=1000000007;
const int INF=0x3f3f3f3f;
const double eps=1e-8;
#define vmax 5000+5  //最大顶点数
#define emax 500005 //最大边数
struct Dinic{
    ll src,target,ecnt;//源点，汇点，边数
    ll head[vmax];//邻接表表头
    ll cur[vmax];
    ll dis[vmax];//从源点到该点的距离
    struct edge{
        ll to,next,cap;
    }e[2*emax];//边可能是双向的，故乘2
    
    void init(ll start,ll end){
        ecnt=0;
        src=start;
        target=end;
        memset(head,-1,sizeof(head));
    }
    
    void adde(ll from,ll to,ll cap){
        e[ecnt].to=to;
        e[ecnt].cap=cap;
        e[ecnt].next=head[from];
        head[from]=ecnt++;
        
        e[ecnt].to=from;
        e[ecnt].cap=0;
        e[ecnt].next=head[to];
        head[to]=ecnt++;
    }
    
    bool BFS(){
        memset(dis, -1, sizeof(dis));
        dis[src]=0;
        queue<ll>q;
        q.push(src);
        while(!q.empty()){
            ll tmp=q.front();
            q.pop();
            for(ll i=head[tmp];i!=-1;i=e[i].next){
                ll tp=e[i].to;
                if(dis[tp]==-1&&e[i].cap){
                    dis[tp]=dis[tmp]+1;
                    q.push(tp);
                    if(tp==target)
                        return true;
                }
            }
        }
        return false;
    }
    
    ll DFS(ll u,ll delta){
        if(u==target||delta==0)
            return delta;
        ll f,flow=0;
        for(ll& i=cur[u];i!=-1;i=e[i].next){
            if(dis[u]+1==dis[e[i].to] && (f=DFS(e[i].to,min(delta,e[i].cap))))
            {
                e[i].cap-=f;
                e[i^1].cap+=f;
                flow+=f;
                delta-=f;
                if(!delta)break;
            }
        }
        return flow;
    }
    
    ll dinic(){
        ll tmp=0,maxflow=0;
        while(BFS()){
            for(ll i=src;i<=target;i++) cur[i]=head[i];
            while((tmp=DFS(src, INF)))
                maxflow+=tmp;
        }
        return maxflow;
    }
}d;
ll vis[vmax],numberOfFire;
void dfs(int u){
    vis[u]=1;
    numberOfFire++;
    for (int i = d.head[u]; i!=-1; i = d.e[i].next) {
        if (!vis[d.e[i].to]&&d.e[i].cap>0) {
            dfs(d.e[i].to);
        }
    }
}
int main(){
    int n,m,tmp,u,v;
    while (scanf("%d%d",&n,&m)!=EOF) {
        d.init(0, n+1);
        ll sum = 0;
        for (int i=1; i<=n; i++) {
            scanf("%d",&tmp);
            if (tmp>0) {d.adde(0, i, tmp); sum+=tmp; }
            else d.adde(i, n+1, -tmp);
        }
        for (int i=1; i<=m; i++) {
            scanf("%d%d",&u,&v);
            d.adde(u, v, INF);
        }
        ll ans = sum - d.dinic();
        numberOfFire = 0;
        memset(vis, 0, sizeof(vis));
        dfs(0);
        cout<<numberOfFire-1<<" "<<ans<<endl;
    }
    return 0;
}

ISAP解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
// poj 2987
#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <string>
#include <vector>
#include <iomanip>
#include <bitset>
#include <cstring>
#include <iostream>
#include <iosfwd>
#include <deque>
#include <algorithm>
#define Memset(a,val) memset(a,val,sizeof(a))
#define PI acos(-1.0)
#define PB push_back
#define MP make_pair
#define rt(n)       (i == n ? '\n' : ' ')
#define hi         printf("Hi----------\n")
#define IN freopen("input.txt","r",stdin);
#define OUT freopen("output.txt","w",stdout);
#define debug(x) cout<<"Debug : >>>"<<x<<"<<<"<<endl;
#define debug2(x,y) cout<<"Debug : >>>"<<x<<" , "<<y<<"<<<"<<endl;
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
typedef pair<int,int> PII;
typedef long long ll;
const int mod=1000000007;
const int INF=0x3f3f3f3f;
const double eps=1e-8;
const int Vmax = 5000+10;
const int Emax = 120900;
namespace ISAP{
    int n;
    struct Node {
        int v;    // vertex
        ll cap;    // capacity
        ll flow;   // current flow in this arc
        int nxt;
    } e[Emax * 2];
    int he[Vmax], fcnt;
    int st, ed;
    ll dist[Vmax], numbs[Vmax], q[Vmax];
    void adde(int u, int v, ll c) {    //单向加边的过程
        e[++fcnt].v = v;
        e[fcnt].cap = c;
        e[fcnt].flow = 0;
        e[fcnt].nxt = he[u];
        he[u] = fcnt;
        e[++fcnt].v = u;
        e[fcnt].cap = 0;
        e[fcnt].flow = 0;
        e[fcnt].nxt = he[v];
        he[v] = fcnt;
    }
    void init(int src,int sink,int n_) {
        memset(he, 0, sizeof(he));
        fcnt = 1;
        n=n_;
        st = src, ed = sink;/*修改*/
    }
    void rev_bfs() {
        int font = 0, rear = 1;
        for (int i = 0; i <= n; i++) { //n为总点数
            dist[i] = Vmax;
            numbs[i] = 0;
        }
        q[font] = ed;
        dist[ed] = 0;
        numbs[0] = 1;
        while(font != rear) {
            int u = q[font++];
            for (int i = he[u]; i; i = e[i].nxt) {
                if (e[i ^ 1].cap == 0 || dist[e[i].v] < Vmax) continue;
                dist[e[i].v] = dist[u] + 1;
                ++numbs[dist[e[i].v]];
                q[rear++] = e[i].v;
            }
        }
    }
    ll maxflow() {
        rev_bfs();
        ll u, totalflow = 0;
        ll curg[Vmax], revpath[Vmax];
        for(ll i = 0; i <= n; ++i) curg[i] = he[i];
        u = st;
        while(dist[st] < n) {
            if(u == ed) {   // find an augmenting path
                ll augflow = INF;
                for(ll i = st; i != ed; i = e[curg[i]].v)
                    augflow = min(augflow, e[curg[i]].cap);
                for(ll i = st; i != ed; i = e[curg[i]].v) {
                    e[curg[i]].cap -= augflow;
                    e[curg[i] ^ 1].cap += augflow;
                    e[curg[i]].flow += augflow;
                    e[curg[i] ^ 1].flow -= augflow;
                }
                totalflow += augflow;
                u = st;
            }
            ll i;
            for(i = curg[u]; i; i = e[i].nxt)
                if(e[i].cap > 0 && dist[u] == dist[e[i].v] + 1) break;
            if(i) {   // find an admissible arc, then Advance
                curg[u] = i;
                revpath[e[i].v] = i ^ 1;
                u = e[i].v;
            } else {    // no admissible arc, then relabel this vertex
                if(0 == (--numbs[dist[u]])) break;    // GAP cut, Important!
                curg[u] = he[u];
                ll mindist = n;
                for(ll j = he[u]; j; j = e[j].nxt)
                    if(e[j].cap > 0) mindist = min(mindist, dist[e[j].v]);
                dist[u] = mindist + 1;
                ++numbs[dist[u]];
                if(u != st)
                    u = e[revpath[u]].v;    // Backtrack
            }
        }
        return totalflow;
    }
}
int vis[Vmax],numberOfFire;
void dfs(int u){
    vis[u]=1;
    numberOfFire++;
    for (int i=ISAP::he[u]; i; i = ISAP::e[i].nxt) {
        int v = ISAP::e[i].v;
        if (!vis[v]&&ISAP::e[i].cap) {
            dfs(v);
        }
    }
}
int main(){
    int n,m,tmp,u,v;
    while (scanf("%d%d",&n,&m)!=EOF) {
        ISAP::init(0, n+1, n+2);
        ll sum = 0;
        for (int i=1; i<=n; i++) {
            scanf("%d",&tmp);
            if (tmp>0) {ISAP::adde(0, i, tmp); sum+=tmp; }
            else ISAP::adde(i, n+1, -tmp);
        }
        for (int i=1; i<=m; i++) {
            scanf("%d%d",&u,&v);
            ISAP::adde(u, v, INF);
        }
        ll ans = sum - ISAP::maxflow();
        numberOfFire = 0;
        memset(vis, 0, sizeof(vis));
        dfs(0);
        cout<<numberOfFire-1<<" "<<ans<<endl;
    }
}