BZOJ1497 [NOI2006]最大获利

题面

http://www.lydsy.com/JudgeOnline/problem.php?id=1497

题解

​ 假设一开始已经累计了所有的获益。
​ S集合表示选.T集合表示不选。
​ S向每一个用户连一条边,边权为Ci。
​ 每一个中转站向T连边,边权为Pi,建造的费用
​ 注意到对于一个用户群,如果存在一个中转站没有,它就是属于T集合,要减去左边Ci的代价。
​ 我们从每一个用户向两个中转站连一条$inf$的边,表示这个用户和两个中转站的集合相同。
*What’s this? *

​ 除非右边的两条边都被割掉,或者左边的边被割掉,否则如果右边有一个没有割掉,左边的这条边必须割去。

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
//省略一堆头文件
#define N 55099
#define M 233333
int first[N],cur[N],q[N],dis[N],nume;
struct Edge{
int to,nxt,cap;
Edge() {}
Edge(int to,int nxt,int cap):to(to),nxt(nxt),cap(cap){}
}edge[M*2];
void Addedge(int a,int b,int c){
edge[nume] = Edge(b,first[a],c);first[a] = nume++;
edge[nume] = Edge(a,first[b],0);first[b] = nume++;
}
int front,rear,S,T;
bool bfs(){
mem(dis,-1);front = rear = 0;
dis[q[rear++] = T] = 0;
while(front<rear){
int u = q[front++];
for (int e=first[u];~e;e=edge[e].nxt){
int v = edge[e].to;
if(edge[e^1].cap && dis[v] == -1)
dis[v] = dis[u]+1,q[rear++] = v;
}
}
return dis[S]!=-1;
}
int dfs(int u,int flow){
if(u==T) return flow;
int used = 0,d;
for (int &e=cur[u];~e;e=edge[e].nxt){
int v = edge[e].to;
if(edge[e].cap && dis[v]==dis[u]-1 && (d = dfs(v,min(flow - used,edge[e].cap))))
edge[e].cap-=d,edge[e^1].cap+=d,used+=d;
if(used==flow)break;
}
return used;
}
int ans,n,m;
int main(){
n = read(),m = read();
ans = 0;
S = 0,T = n + m + 1;
int p,a,b,c;
mem(first,-1);nume = 0;
rep(i,0,n) p = read(),Addedge(m+i+1,T,p);
rep(i,0,m){
a = read()-1,b = read()-1,c = read();
Addedge(i+1,m+a+1,inf);
Addedge(i+1,m+b+1,inf);
Addedge(S,i+1,c);
ans += c;
}
while(bfs()){
int flow;
rep(i,S,T+1)cur[i]=first[i];
while(flow=dfs(S,inf))ans-=flow;
}
writeln(ans);
return 0;
}
文章目录
  1. 1. 题面
  2. 2. 题解