题目链接
最大权闭合图模型,参考
具体做法是从源点向每个实验连一条流量为这个实验的报酬的边,从每个实验向这个实验需要的所有器材各连一条流量为(INF)的边,再从每个器材向汇点连一条流量为这个器材的费用的边。
然后跑出最小割(即最大流),用所有的报酬和减去这个最小割就行。
不知道为什么我的(Dinic)写的挺简洁的,但是慢的出奇。大家都是(0ms)就我(33ms)。
至于输出方案,判断一下最后一次找增广路有没有走到这个点就行了。
#include <cstdio>
#include <queue>
using namespace std;
#define INF 2147483647
inline int read(int &p){
int s = 0, w = 1;
char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-')w = -1;ch = getchar();}
while(ch >= '0' && ch <= '9') s = s * 10 + ch - '0',ch = getchar();
p = s * w;
return ch != '
' && ch != '
';
}
const int MAXN = 1000010;
struct Edge{
int next, from, to, rest;
}e[MAXN];
int head[MAXN], num = 1;
inline void Add(int from, int to, int flow){
e[++num] = (Edge){ head[from], from, to, flow }; head[from] = num;
e[++num] = (Edge){ head[to], to, from, 0 }; head[to] = num;
}
int flow[MAXN], pre[MAXN], dfn[MAXN];
int value[MAXN], cost[MAXN], servant;
int n, m, s, t, a, b, now, Time, sum, ans;
queue <int> q;
int RoadExist(){
while(q.size()) q.pop();
flow[s] = INF; pre[t] = 0; q.push(s); dfn[s] = ++Time;
while(q.size()){
now = q.front(); q.pop();
for(int i = head[now]; i; i = e[i].next)
if(e[i].rest && dfn[e[i].to] != Time)
dfn[e[i].to] = Time, flow[e[i].to] = min(flow[now], e[i].rest), q.push(e[i].to), pre[e[i].to] = i;
}
return pre[t];
}
int dinic(){
int ans = 0;
while(RoadExist()){
ans += flow[t];
now = t;
while(now != s){
e[pre[now]].rest -= flow[t];
e[pre[now] ^ 1].rest += flow[t];
now = e[pre[now]].from;
}
}
return ans;
}
int x[MAXN], y[MAXN];
int main(){
s = 99999; t = 100000;
read(n); read(m);
for(int i = 1; i <= n; ++i){
read(value[i]); Add(s, i, value[i]); sum += value[i];
while(read(servant)) Add(i, servant + 500, INF);
Add(i, servant + 500, INF);
}
for(int i = 1; i <= m; ++i)
read(cost[i]);
for(int i = 1; i <= m; ++i)
Add(i + 500, t, cost[i]);
ans = dinic();
for(int i = 1; i <= n; ++i)
if(dfn[i] == Time) printf("%d ", i);
puts("");
for(int i = 1; i <= m; ++i)
if(dfn[i + 500] == Time) printf("%d ", i);
puts("");
printf("%d
", sum - ans);
return 0;
}