hdu5855二分+最大流

Posted by Cww97 on 2016-08-17

版权声明:本文为博主原创文章,未经博主允许不得转载。原文所在http://blog.csdn.net/cww97 https://blog.csdn.net/cww97/article/details/52234221
二分最大时间,最大流收益

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
#include<queue>
#include<cstdio>
#include<vector>
#include<string>
#include<cstring>
#include<iostream>
using namespace std;
typedef long long LL;
const int INF = 0x3f3f3f3f;
const int N=433;
struct Planet {
int pay;LL t;Planet() {};
}pl[N];
bool need[N][N];
int rem[N],profit[N],cnt[N];
LL L;

struct Edge{
int from,to,cap,flow;
Edge(int u,int v,int c,int f):from(u),to(v),cap(c),flow(f){}
};
int s,t,n,m,top;
vector<Edge>edges;//0=s,1~n工厂,n+1~n+m商店,n+m+1=t
vector<int>G[N];//邻接表
bool vis[N];//use when bfs
int d[N],cur[N];//dist,now edge
void AddEdge(int from,int to,int cap){
edges.push_back(Edge(from,to,cap,0));
edges.push_back(Edge(to,from, 0 ,0));
top=edges.size();
G[from].push_back(top-2);
G[ to ].push_back(top-1);
}

bool BFS(){
memset(vis,0,sizeof(vis));
queue<int>Q;
Q.push(s);d[s]=0;vis[s]=1;
while (!Q.empty()){
int x=Q.front();Q.pop();
for (int i=0;i<G[x].size();i++){
Edge &e=edges[G[x][i]];
if (vis[e.to]||e.cap<=e.flow)continue;
vis[e.to]=1;
d[e.to]=d[x]+1;
Q.push(e.to);
}
}
return vis[t];
}

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

int Maxflow(int s,int t){
int flow=0;
while(BFS()){
memset(cur,0,sizeof(cur));
flow+=DFS(s,INF);
}
return flow;
}

int check(LL MaxTime){
edges.clear(); //init
for (int i=0;i<=n+m+1;i++)G[i].clear();
memset(cnt,0,sizeof(cnt));
s = 0,t = n+m+1;
for (int i=1;i<=n;i++){
AddEdge(i,t,pl[i].pay);
if (pl[i].t<=MaxTime)
for (int j=1;j<=m;j++)
if (need[j][i]) cnt[j]++;
}
int ans = 0;
for (int i=1;i<=m;i++)if (cnt[i]==rem[i]){
ans += profit[i];
AddEdge(s,n+i,profit[i]);
for (int j=1;j<=n;j++)
if (need[i][j])AddEdge(n+i,j,INF);
}
int flow = Maxflow(s,t);
return ans-flow;
}

int main(){
//freopen("fuck.in","r",stdin);
//freopen("fuck.out","w",stdout);
int T,x;
scanf("%d",&T);
for (int cas=1;cas<=T;cas++){
printf("Case #%d: ",cas);
scanf("%d%d%I64d",&n,&m,&L);
memset(need,0,sizeof(need));
for (int i=1;i<=n;i++)
scanf("%d%I64d",&pl[i].pay,&pl[i].t);
for (int i=1;i<=m;i++){
scanf("%d%d",&profit[i],&rem[i]);
for (int j=1;j<=rem[i];j++){
scanf("%d",&x);
need[i][x] = true;
}
}
LL l=0,r = 0X3f3f3f3f3f3f3f3f ,ans = -1;
for (;l<r;){
LL mid = (l+r)>>1;
int cur = check(mid);
if (cur >= L){ans=mid;r=mid;}
else l = mid + 1;
}
if (ans == -1) puts("impossible");
else printf("%I64d %d\n",ans,check(ans));
}
return 0;
}