洛谷P2762 太空飞行计划问题 笔记

传送门

神奇的题目。

正解就是源点向实验连边，边权为收益。然后仪器向汇点连边，边权为代价。

然后答案就是所有实验收益之和-最小割。

考虑证明。首先所有实验收益之和显然对应了做所有的实验。
然后考虑割掉一条边。如果割掉的是源点->实验，那么就是不做这个实验。如果割了仪器->汇点，那么就是买下这个仪器。

显而易见，实验该有的仪器都要有，对应到图中就是要做的实验对应过去的所有仪器都和汇点断了边。 这恰恰等同于源点与汇点的不连通。于是此时求出的最小割就是最小代价。最后将收益之和减去这个代价就是答案。

code

//writer:Oier_szc

#include <bits/stdc++.h>
//#include <windows.h>
#define TS cerr<<"I AK IOI"<<endl;
#define cr(x) cerr<<x<<endl;
#define cr2(x,y) cerr<<x<<" "<<y<<endl;
#define cr3(x,y,z) cerr<<x<<" "<<y<<" "<<z<<endl;
#define int long long
using namespace std;
const int N=55,M=3e3+5,INF=2e9,mod=1e9+7;
int m,n,s,t,ans=0;
int p[N],c[N];
int head[N<<1],tot=1;
struct edge
{
	int ne,to,w;
}e[M<<1];
void add(int u,int v,int w)
{
	e[++tot]={head[u],v,w};
	head[u]=tot;
	e[++tot]={head[v],u,0};
	head[v]=tot;
}
int dis[N<<1],cur[N<<1];
bool bfs()
{
	for(int i=s;i<=t;++i)
	{
		dis[i]=-1;
		cur[i]=head[i];
	}
	queue<int> q;
	q.push(s),dis[s]=1;
	while(!q.empty())
	{
		int now=q.front(),to;
		q.pop();
		for(int i=head[now];i;i=e[i].ne)
		{
			to=e[i].to;
			if(e[i].w&&dis[to]==-1)
			{
				dis[to]=dis[now]+1;
				if(to==t) return true;
				q.push(to);
			}
		}
	}
	return false;
}
int dfs(int u,int flow)
{
	if(u==t) return flow;
	int used=0,to;
	for(int i=cur[u];i;i=e[i].ne)
	{
		cur[u]=i,to=e[i].to;
		if(e[i].w&&dis[to]==dis[u]+1)
		{
			int x=dfs(to,min(flow,e[i].w));
			flow-=x,used+=x;
			e[i].w-=x,e[i^1].w+=x;
			if(!flow) break;
		}
	}
	if(!used) dis[u]=-1;
	return used;
}
int Dinic()
{
	int res=0;
	while(bfs()) res+=dfs(s,INF);
	return res;
}
signed main()
{
	scanf("%lld%lld",&m,&n);
	s=0,t=m+n+1;
	int re;
	for(int i=1;i<=m;++i)
	{
		scanf("%lld",&p[i]);
		add(s,i,p[i]),ans+=p[i];
		while(getchar()==' ')
		{
			scanf("%lld",&re);
			add(i,m+re,INF);
		}
	}
	for(int i=1;i<=n;++i)
	{
		scanf("%lld",&c[i]);
		add(m+i,t,c[i]);
	}
	ans-=Dinic();
	for(int i=1;i<=m;++i)
	{
		if(dis[i]!=-1) printf("%lld ",i);
	}
	printf("\n");
	for(int i=1;i<=n;++i)
	{
		if(dis[m+i]!=-1) printf("%lld ",i);
	}
	printf("\n%lld",ans);
	return 0;
}