MYF

HDU 5855 Less Time, More profit

Posted on | In | | Visitors

题目链接

HDU 5855

题目类型：网络流求最大权闭合图

题目来源：2016 Multi-University Training Contest 9 （816惨案）

题目分析

题目大意

某城市有n个工厂和m个商店，给出n个工厂的建造时间ti以及建造成本Li，这些工厂可以同时开始建造，对于每一个商店，给出可以获得的利润，以及若干个工厂，该商店开业的话必须要建立这些工厂。问，在最短的时间，如何获得至少为k的利润，求出所需要的时间以及所得的利润

解析

看了题解之后，发现二分的去找建造的时间，然后求出对于每一个建造的时间可以获得的最大利润数量，如果得到的多了，就把右边界左移。对于一个有顶点含有负权的图，想要求出来这个图的最大权，就要跑最大权闭合图了，结果就是所有权值为正的点权之和，减去用网络流跑出来的最大流。

最大权闭合图，推荐两篇文章：

  1. 最大权闭合图
  2. 最大权闭合图&&最大密度子图

代码

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
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
#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("1012.in","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 maxn=100000+5;
const int mod=1000000007;
const int INF=0x3f3f3f3f;
const double eps=1e-8;
const int Vmax=2005; //需要拆点的话记得加倍
namespace ISAP{
    const int Emax = 420900;
    ll n;
    struct Node {
        int v;    // vertex
        ll cap;    // capacity
        ll flow;   // current flow in this arc
        int nxt;
    } e[Emax * 2];
    ll g[Vmax], fcnt;
    ll 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 = g[u];
        g[u] = fcnt;
        e[++fcnt].v = u;
        e[fcnt].cap = 0;
        e[fcnt].flow = 0;
        e[fcnt].nxt = g[v];
        g[v] = fcnt;
    }
    void init(ll src,ll sink,ll n_) {
        memset(g, 0, sizeof(g));
        fcnt = 1;
        n=n_;
        st = src, ed = sink;/*修改*/
    }
    void rev_bfs() {
        ll font = 0, rear = 1;
        for (ll i = 0; i <= n; i++) { //n为总点数
            dist[i] = Vmax;
            numbs[i] = 0;
        }
        q[font] = ed;
        dist[ed] = 0;
        numbs[0] = 1;
        while(font != rear) {
            ll u = q[font++];
            for (ll i = g[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] = g[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] = g[u];
                ll mindist = n;
                for(ll j = g[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;
    }
}
struct plant{
    ll L,t;
    int id;
    bool operator < (const plant &pp)const{
        return t<pp.t;
    }
}p[205];
vector<int>lnk[Vmax];
int V[Vmax];
int rnk[Vmax];
int main(){
    int T;
    int k,tmp;
    scanf("%d",&T);
    for (int cas = 1; cas <= T; cas++) {
        int n,m; ll L;
        scanf("%d%d%lld",&n,&m,&L);
        
        for (int i=1; i<=n; i++) {
            scanf("%lld %lld",&p[i].L,&p[i].t);
            p[i].id = i ;
        }
        sort(p+1, p+1+n);   //将所有工厂按建造时间排序
        
        for (int i=1; i<=n; i++) {
            tmp = p[i].id;
            rnk[tmp] = i;
        }
        
        for (int i=1; i<=m; i++) {
            lnk[i].clear();
            scanf("%d",V+i);
            scanf("%d",&k);
            while (k--) {
                scanf("%d",&tmp);
                lnk[i].push_back(rnk[tmp]); //映射到现在工厂的下标
            }
            sort(lnk[i].begin(), lnk[i].end()); //对于第i个商店，使商店需要的工厂按建造时间排序
        }
        
        /*二分找到最优的时间*/
        int l = 1 ,r = n;
        ll tt = -1, ans = 0, sum = 0, prof;
        while (l<=r) {
            int mid = ( l + r ) >> 1;
            ISAP::init(0, n+m+1, (n+m)+2);
            
            sum = 0;
            for (int i=1; i<=m; i++) {
                if (lnk[i].back()>mid) continue;    //建造当前商店所需要的建造时间最长的工厂大于当前选择的工厂就跳过
                ISAP::adde(0, i, V[i]);
                sum += V[i];
            }
            
            for (int i=1; i<=m; i++) {
                if (lnk[i].back()>mid) continue;    //建造当前商店所需要的建造时间最长的工厂大于当前选择的工厂就跳过
                int sz = (int)lnk[i].size();
                for (int j=0; j<sz; j++) {
                    ISAP::adde(i, m+lnk[i][j], INF);
                }
            }
            
            for (int i=1; i<=mid; i++) {
                ISAP::adde(i+m, 1+n+m, p[i].L);
            }
            
            ans = sum - ISAP::maxflow();    //正权顶点之和减去最大流
            if (ans < L) {
                l = mid+1;
            }
            else if (ans > L){
                r = mid-1, tt = p[mid].t, prof = ans;
            }
            else{
                tt = p[mid].t, prof = ans;
                break;
            }
        }
        
        printf("Case #%d: ",cas);
        if (tt!=-1)
            printf("%lld %lld\n",tt, prof);
        else
            printf("impossible\n");
    }
    return 0;
}