1062:昂贵的聘礼：网络流技压群雄！

程序员文章站 2024-03-23 15:42:10

...

题目大意

题目链接
不愧是中文题b(￣▽￣)d，
1062:昂贵的聘礼：网络流技压群雄！

思路分析

拿到题求最小费用，物品和物品存在单向依赖，而且还有地位的限制，情况比较复杂，想到的第一种方法是网络流，不过很难在边上把对等级的限制体现出来，所以对等级限制我的处理方法是

枚举所有的等级区间，比如酋长是k，最大限制为m，那么我们跑 $m+1$ 次最小费用流，每次搜索的区间是 $[i,i+m]|i\in[k-m,k]$ ，搜索某个区间的时候，我们只加入满足这个等级限制的边。

好了最重要的问题，如何建图？显然所有边的容量都是1，保证不重复走。

对酋长的物品，全价购买就是从s连一条cost=0到物品0，然后从该物品连一条花费为全价购买的边到t
对酋长的替代品i，如果替代品的拥有着的等级在遍历的区间内，我们从s连一条花费为拥有替代品后的价格的边到i。比如如果你能够替我弄到大祭司的皮袄，我可以只要8000金币，那么我们从s连一条cost=8000的边到皮袄。
对其他物品i，全价购买就是从该物品到t的花费全价的边。她有替代品j，还需要补差价p，那么我们从i连一条花费为p的边到j。
各个等级区间最小费用流的最小值即答案。

不算很慢
1062:昂贵的聘礼：网络流技压群雄！

#include<iostream>
#include<string.h>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;

#define MAX 105
#define ll int
#define inf 1111111111

struct edge {
	ll to, cap, rev, cost;
	edge(ll a = 0, ll b = 0, ll c = 0, ll d = 0) { to = a, cap = b, rev = c, cost = d; }
};
vector<edge> G[MAX];
vector<pair<int, int> > v[MAX];//存放输入进来的物品数目和替代品信息
ll pre1[MAX], pre2[MAX], vis[MAX], dist[MAX], minf[MAX], mincost = 0, maxflow = 0;

void addEdge(ll from, ll to, ll cap, ll cost) {
	G[from].push_back(edge(to, cap, G[to].size(), cost));
	G[to].push_back(edge(from, 0, G[from].size() - 1, -cost));
}

//检查j物品拥有者的地位是否处于[l,r]区间之内
bool checkLevel(ll j, ll l, ll r) {
	ll level = v[j][0].second;
	if (level < l || level>r)return false;
	else return true;
}

bool spfa(ll s, ll t) {
	fill(dist, dist + MAX, inf);
	memset(vis, 0, sizeof(vis));
	queue<ll> q; q.push(s); dist[s] = 0; vis[s] = 1; minf[s] = inf;
	while (!q.empty()) {
		ll id = q.front(); q.pop(); vis[id] = 0;
		for (int i = 0; i < G[id].size(); i++) {
			edge e = G[id][i];
			if (e.cap > 0 && dist[e.to] > dist[id] + e.cost) {
				dist[e.to] = dist[id] + e.cost;
				pre1[e.to] = id, pre2[e.to] = i;
				minf[e.to] = min(minf[id], e.cap);
				if (!vis[e.to]) {
					vis[e.to] = 1;
					q.push(e.to);
				}
			}
		}
	}
	return dist[t] != inf;
}

void update(ll s, ll t) {
	int x = t;
	while (x != s) {
		ll Vid = pre1[x], Eid = pre2[x];
		G[Vid][Eid].cap -= minf[x];
		G[x][G[Vid][Eid].rev].cap += minf[x];
		x = Vid;
	}
	maxflow += minf[t];
	mincost += minf[t] * dist[t];
}

void minFlow(ll s, ll t) {
	spfa(s, t);
	update(s, t);
}

int main() {
	ll m, n; cin >> m >> n;//地位限制和物品总数
	ll P, L, X, a, b, res = inf;
	for (int i = 0; i < n; i++) {
		cin >> P >> L >> X;//价格，地位，替代品总数
		v[i].push_back(make_pair(P, L));//v的第一个元素是价格和地位
		while (X--) {
			cin >> a >> b;
			v[i].push_back(make_pair(a - 1, b));
		}
	}

	//建图
	//0：n-1 物品节点
	//n：起始节点  n+1：终止节点

	ll s = n, t = n + 1, level = v[0][0].second;
	
	for (int k = level - m; k <= level; k++) {
		mincost = 0;
		for (int i = 0; i < MAX; i++)G[i].clear();

		//先处理酋长的物品
		addEdge(s, 0, 1, 0); addEdge(0, t, 1, v[0][0].first);//第一个点没有后置条件
		for (int i = 1; i < v[0].size(); i++) {//酋长的所有替代品都要s->i
			ll id = v[0][i].first, p = v[0][i].second, level;//替代品编号 和价格
			if (checkLevel(id, k, k + m))addEdge(s, id, 1, p); //地位符合要求，源点向替代品连边
		}
		//只加入地位在 [k,k+m]之间的边
		for (int i = 1; i < n; i++) {
			ll price = v[i][0].first, level = v[i][0].second;
			if (level<k || level>k + m) continue;//等级不符合条件
			addEdge(i, t, 1, price);  //不需要替代，直接用钱买
			for (int j = 1; j < v[i].size(); j++) {
				ll id = v[i][j].first; price = v[i][j].second;
				if (checkLevel(id, k, k + m))addEdge(i, id, 1, price);//满足条件的替代品建图
			}
		}
		minFlow(s, t);
		res = min(res, mincost);
	}
	cout << res << endl;
}

然后呢你会发现，我们这个网络流其实流量不是很重要，每次也只找最短的一条增广路径，本质上就是一个spfa的最短路径,ԾㅂԾ,，~~但是我乐意用网络流~~

相关标签： ACM图论/网络流网络

上一篇： MYSQL之explain详解

下一篇： MYSQL主从复制

1062:昂贵的聘礼：网络流技压群雄！

题目大意

思路分析

1062:昂贵的聘礼：网络流技压群雄！

POJ 1062 昂贵的聘礼 (Dijkstra算法)