hiho一下第119周网络流五·最大权闭合子图

92 阅读 0 评论 61 点赞

我是靠谱客的博主英俊橘子，这篇文章主要介绍hiho一下第119周网络流五·最大权闭合子图，现在分享给大家，希望可以做个参考。

时间限制: 10000ms

单点时限: 1000ms

内存限制: 256MB

描述

周末，小Hi和小Ho所在的班级决定举行一些班级建设活动。

根据周内的调查结果，小Hi和小Ho一共列出了N项不同的活动(编号1..N)，第i项活动能够产生a[i]的活跃值。

班级一共有M名学生(编号1..M)，邀请编号为i的同学来参加班级建设活动需要消耗b[i]的活跃值。

每项活动都需要某些学生在场才能够进行，若其中有任意一个学生没有被邀请，这项活动就没有办法进行。

班级建设的活跃值是活动产生的总活跃值减去邀请学生所花费的活跃值。

小Hi和小Ho需要选择进行哪些活动，来保证班级建设的活跃值尽可能大。

比如有3项活动，4名学生：

第1项活动产生5的活跃值，需要编号为1、2的学生才能进行；

第2项活动产生10的活跃值，需要编号为3、4的学生才能进行；

第3项活动产生8的活跃值，需要编号为2、3、4的学生才能进行。

编号为1到4的学生需要消耗的活跃值分别为6、3、5、4。

假设举办活动集合为{1}，需要邀请的学生集合为{1,2}，则得到的班级活跃值为5-9 = -4。

假设举办活动集合为{2}，需要邀请的学生集合为{3,4}，则得到的班级活跃值为10-9 = 1。

假设举办活动集合为{2,3}，需要邀请的学生集合为{2,3,4}，则得到的班级活跃值为18-12 = 6。

假设举办活动集合为{1,2,3}，需要邀请的学生集合为{1,2,3,4}，则得到的班级活跃值为23-18 = 5。

小Hi和小Ho总是希望班级活跃值越大越好，因此在这个例子中，他们会选择举行活动2和活动3。

提示：最大权闭合子图

输入

第1行：两个正整数N,M。1≤N≤200，1≤M≤200

第2行：M个正整数，第i个数表示邀请编号为i的学生需要花费的活跃值b[i]，1≤b[i]≤1,000

第3..N+2行：第i行表示编号为i的活动情况。首先是2个整数a,k，a表示该活动产生的活跃值，k表示该活动需要的学生人数。接下来k个整数列举该活动需要的学生编号。1≤a≤1,000，1≤k≤M

输出

第1行：1个整数，最大可以产生的班级活跃值

样例输入

复制代码

样例输出

根据http://hihocoder.com/problemset/problem/1398上面的解释已经很详细了

按最大权闭合子图来构图，跑一下最小割就能得到答案了

构图只需要处理容量数组即可

复制代码

#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <iostream>
#include <queue>
#include <set>
#include <vector>
#include<stack>
using namespace std;
#include <fstream>
const int N=408;
const int inf=0x3f3f3f3f;
int min(int a,int b)
{
return a<b?a:b;
}
int max_flow;//max_flow是最大流
int mp[N][N];// mp[i][j]是每条边的容量,flow[i][j]是每条边的流量
int pre[N];//res[]是每个点的剩余流量,pre[]是每个点的父亲
int level[N];//记录距离标号
int gap[N];//gap常数优化
//入口参数vs源点，vt汇点
int SAP(int vs,int vt)
{
memset(pre,-1,sizeof(pre));
memset(level,0,sizeof(level));
memset(gap,0,sizeof(gap));
gap[0]=vt;
int v,u=pre[vs]=vs,maxflow=0,aug=inf;
while(level[vs]<vt)
{
//寻找可行弧
for(v=1; v<=vt; v++)
{
if(mp[u][v]>0&&level[u]==level[v]+1)
{
break;
}
}
if(v<=vt)
{
pre[v]=u;
u=v;
if(v==vt)
{
aug=inf;
//寻找当前找到的一条路径上的最大流
for(int i=v; i!=vs; i=pre[i])
{
if(aug>mp[pre[i]][i])aug=mp[pre[i]][i];
}
maxflow+=aug;
//更新残留网络
for(int i=v; i!=vs; i=pre[i])
{
mp[pre[i]][i]-=aug;
mp[i][pre[i]]+=aug;
}
u=vs;//从源点开始继续搜
}
}
else
{
//找不到可行弧
int minlevel=vt;
//寻找与当前点相连接的点中最小的距离标号
for(v=1; v<=vt; v++)
{
if(mp[u][v]>0&&minlevel>level[v])
{
minlevel=level[v];
}
}
gap[level[u]]--;//(更新gap数组）当前标号的数目减1；
if(gap[level[u]]==0)break;//出现断层
level[u]=minlevel+1;
gap[level[u]]++;
u=pre[u];
}
}
return maxflow;
}
int pay[205];
int pro[205];
vector<int> pp[205];
int L;
int n,m;
int
bin( )
{
int st=n+m+1,ed=n+m+2;
memset(mp,0,sizeof mp);
int sum=0;
for (int i=1; i<=n; i++)
{
mp[st][i]=pro[i];
for (int j=0; j<pp[i].size(); j++)
mp[i][pp[i][j]+n]=inf;
sum+=pro[i];
}
for (int i=1; i<=m; i++)
mp[n+i][ed]=pay[i];
int ans=SAP(st,ed);
return sum-ans;
}
int main()
{
int k,tmp;
scanf("%d%d",&n,&m);
for (int i=1; i<=m; i++) scanf("%d",&pay[i] );
for (int i=1; i<=n; i++)
{
pp[i].clear();
scanf("%d",&pro[i]);
scanf("%d",&k);
for (int j=1; j<=k; j++)
{
scanf("%d",&tmp);
pp[i].push_back(tmp);
}
}
printf("%dn",bin());
return 0;
}

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 <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <iostream>
#include <queue>
#include <set>
#include <vector>
#include<stack>
using namespace std;
#include <fstream>
const int N=408;
const int inf=0x3f3f3f3f;
int min(int a,int b)
{
return a<b?a:b;
}
int max_flow;//max_flow是最大流
int mp[N][N];// mp[i][j]是每条边的容量,flow[i][j]是每条边的流量
int pre[N];//res[]是每个点的剩余流量,pre[]是每个点的父亲
int level[N];//记录距离标号
int gap[N];//gap常数优化
//入口参数vs源点，vt汇点
int SAP(int vs,int vt)
{
memset(pre,-1,sizeof(pre));
memset(level,0,sizeof(level));
memset(gap,0,sizeof(gap));
gap[0]=vt;
int v,u=pre[vs]=vs,maxflow=0,aug=inf;
while(level[vs]<vt)
{
//寻找可行弧
for(v=1; v<=vt; v++)
{
if(mp[u][v]>0&&level[u]==level[v]+1)
{
break;
}
}
if(v<=vt)
{
pre[v]=u;
u=v;
if(v==vt)
{
aug=inf;
//寻找当前找到的一条路径上的最大流
for(int i=v; i!=vs; i=pre[i])
{
if(aug>mp[pre[i]][i])aug=mp[pre[i]][i];
}
maxflow+=aug;
//更新残留网络
for(int i=v; i!=vs; i=pre[i])
{
mp[pre[i]][i]-=aug;
mp[i][pre[i]]+=aug;
}
u=vs;//从源点开始继续搜
}
}
else
{
//找不到可行弧
int minlevel=vt;
//寻找与当前点相连接的点中最小的距离标号
for(v=1; v<=vt; v++)
{
if(mp[u][v]>0&&minlevel>level[v])
{
minlevel=level[v];
}
}
gap[level[u]]--;//(更新gap数组）当前标号的数目减1；
if(gap[level[u]]==0)break;//出现断层
level[u]=minlevel+1;
gap[level[u]]++;
u=pre[u];
}
}
return maxflow;
}
int pay[205];
int pro[205];
vector<int> pp[205];
int L;
int n,m;
int
bin( )
{
int st=n+m+1,ed=n+m+2;
memset(mp,0,sizeof mp);
int sum=0;
for (int i=1; i<=n; i++)
{
mp[st][i]=pro[i];
for (int j=0; j<pp[i].size(); j++)
mp[i][pp[i][j]+n]=inf;
sum+=pro[i];
}
for (int i=1; i<=m; i++)
mp[n+i][ed]=pay[i];
int ans=SAP(st,ed);
return sum-ans;
}
int main()
{
int k,tmp;
scanf("%d%d",&n,&m);
for (int i=1; i<=m; i++) scanf("%d",&pay[i] );
for (int i=1; i<=n; i++)
{
pp[i].clear();
scanf("%d",&pro[i]);
scanf("%d",&k);
for (int j=1; j<=k; j++)
{
scanf("%d",&tmp);
pp[i].push_back(tmp);
}
}
printf("%dn",bin());
return 0;
}