太空飞行计划

有n个实验,每个实验有一定的收益,同时每个实验需要一定的仪器,仪器需要一定的代价,问最多收益。
解 先假设所有实验收益都得到,然后就有2种损失,要么损失掉这个实验的收益(即不需要买仪器),或者损失掉仪器的价格(获得该实验的收益)。源点往实验连实验的收益,仪器往汇点连仪器的价格,实验往仪器连inf(防止被割掉),求最小割,减一下。


#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
const ll MAXN = 1000;
const ll maxm = 100000;
struct Edge{
	ll from, to, cap, flow;
	Edge(){
	}
	Edge(ll from, ll to, ll cap, ll flow):from(from), to(to), cap(cap), flow(flow){}	
};
struct Edge1
{
    ll from, to; ll dist;       //起点,终点,距离
    Edge1(ll from, ll to, ll dist):from(from), to(to), dist(dist) {}
};
struct Dinic{
	ll n, m, s, t;
	vector<Edge>edges;
	vector<ll>G[MAXN];
	ll d[MAXN];
	ll cur[MAXN];
	ll vis[MAXN];
	void init(ll n, ll s, ll t)
	{
		this->n = n;this->s = s;this->t = t;
		edges.clear();
		for(ll i = 0;i <= n;++i) G[i].clear();
	}
	
	void add_edge(ll from, ll to, ll cap)
	{
		edges.push_back( Edge(from, to, cap, 0) );
		edges.push_back( Edge(to, from, 0, 0) );
		m = edges.size();
		G[from].push_back(m-2);
		G[to].push_back(m-1); 
	}
	
	bool bfs(){
		memset(vis, 0, sizeof(vis));
		queue<ll>Q;
		Q.push(s);
		d[s] = 0;
		vis[s] = true;
		while(!Q.empty())
		{
			ll x = Q.front();
			Q.pop();
			for(ll i = 0;i < G[x].size();++i)
			{
				Edge& e = edges[G[x][i]];
				if(!vis[e.to] && e.cap > e.flow)
				{
					vis[e.to] = true;
					d[e.to] = d[x] + 1;
					Q.push(e.to);
				}
			}		
		}
		return vis[t];
	}
	ll dfs(ll x,ll a)
	{
		if(x == t || a == 0)return a;
		ll flow = 0, f;
		for(ll& i = cur[x];i < G[x].size();++i)
		{
			Edge& e = edges[G[x][i]];
			if(d[x] + 1 == d[e.to] && (f = dfs( e.to, min(a, e.cap-e.flow)))>0)
			{
				e.flow += f;
				edges[G[x][i]^1].flow -= f;
				flow += f;
				a -= f;
				if(a == 0)break; 
			}
		}
		return flow;
	}
	ll maxflow()
	{
		ll flow = 0;
		while(bfs())
		{
			memset(cur, 0, sizeof(cur));
			flow += dfs(s,inf);
		}
		return flow;
	}
}gao;//刘汝佳网络流dinic板子
int val[55];
int cost[55];
char c[1005];
vector<int>q[55];
int main()
{
	int m,n;
	scanf("%d%d",&m,&n);
	int sum=0;
	gao.init(m+n+2,m+n+1,m+n+2);
	for(int i=1;i<=m;i++){
		scanf("%d",&val[i]);
		sum+=val[i];
		memset(c,0,sizeof(c));
		cin.getline(c,1000);
		int ulen=0;
		int num;
		while(sscanf(c+ulen,"%d",&num)==1){
			q[i].push_back(num);
			if(num==0)ulen++;
			else while(num){
				num/=10;
				ulen++;
			}
			ulen++;
		}
	}
	for(int i=1;i<=n;i++){
		scanf("%d",&cost[i]);
	}
	for(int i=1;i<=m;i++){
		for(int j=0;j<q[i].size();j++){
			gao.add_edge(i,q[i][j]+m,inf);
		}
	}
	for(int i=1;i<=m;i++){
		gao.add_edge(n+m+1,i,val[i]);
	}
	for(int i=m+1;i<=n+m;i++){
		gao.add_edge(i,n+m+2,cost[i-m]);
	}
	int ans=sum-gao.maxflow();
	for(int i=1;i<=m;i++){
		if(gao.vis[i])printf("%d ",i);
	}
	printf("\n");
	for(int i=m+1;i<=n+m;i++){
		if(gao.vis[i])printf("%d ",i-m);
	}
	printf("\n");
	printf("%d\n",ans);
}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注