题解:首先源点向每个实验建边,流量为经费的值,实验向器材建边,值为无限大,器材向终点建边,值为价值
然后跑一遍最大流就能跑出所谓的最大闭合图的点值之和.
代码如下:
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define hi puts("hi");
#define inf 0x3f3f3f3f
using namespace std; int v[],w[],head[],next[],deep[],first[],cur[];
int n,m,s,t,cnt; void init()
{
cnt=-; //
memset(head,-,sizeof(head));
memset(next,-,sizeof(next));
} void add(int from,int to,int cost)
{
cnt++;
next[cnt]=head[from]; //
v[cnt]=to;
w[cnt]=cost;
head[from]=cnt;
} void add_edge(int from,int to,int cost)
{
add(from,to,cost);
add(to,from,);
} int bfs(int s,int t)
{
queue<int> q;
memset(deep,,sizeof(deep));
deep[s]=;
q.push(s);
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i=head[u]; i!=-; i=next[i])
{
if(w[i]>&&(!deep[v[i]]))
{
deep[v[i]]=deep[u]+;
q.push(v[i]);
}
}
}
if(!deep[t])
{
return ;
}
return ;
} int dfs(int u,int t,int dist)
{
if(u==t)
{
return dist;
}
for(int i=head[u]; i!=-; i=next[i])
{
if(w[i]&&(deep[v[i]]==deep[u]+)) //!!!
{
int di=dfs(v[i],t,min(dist,w[i]));
if(di>)
{
w[i]-=di;
w[i^]+=di;
return di;
}
}
}
return ;
} int dinic(int s,int t)
{
int ans=;
while(bfs(s,t))
{
while(int d=dfs(s,t,inf))
{
ans+=d;
}
}
return ans;
} int main()
{
init();
scanf("%d%d",&m,&n);
int sum=;
s=;
t=n+m+;
int x;
char c;
for(int i=; i<=m; i++)
{
scanf("%d",&x);
sum+=x;
add_edge(s,n+i,x);
while()
{
scanf("%d%c",&x,&c);
add_edge(n+i,x,inf);
if(c=='\n'||c=='\r')
{
break;
}
}
}
for(int i=; i<=n; i++)
{
scanf("%d",&x);
add_edge(i,t,x);
}
sum-=dinic(s,t);
for(int i=;i<=m;i++)
{
if(deep[i+n])
{
printf("%d ",i);
}
}
printf("\n");
for(int i=;i<=n;i++)
{
if(deep[i])
{
printf("%d ",i);
}
}
printf("\n");
printf("%d\n",sum);
}