「bzoj2260」商店购物 - 最小树形图

题目大意

    Grant是一个个体户老板，他经营的小店因为其丰富的优惠方案深受附近居民的青睐，生意红火。小店的优惠方案十分简单有趣。Grant规定：在一次消费过程中，如果您在本店购买了精制油的话，您购买香皂时就可以享受$2.00$元/块的优惠价；如果您在本店购买了香皂的话，您购买可乐时就可以享受$1.50$元/听的优惠价……诸如此类的优惠方案就是说：如果您在本店购买了商品$A$的话，您就可以以$P$元/件的优惠价格购买商品$B$（购买的数量不限）。有趣的是，你需要购买同样一些商品，由于不同的购买顺序，Grant老板可能会叫你付不同数量的钱。比如你需要一块香皂（原价$2.50$元）、一瓶精制油（原价$10.00$元）、一听可乐(原价$1.80$元)，如果你按照可乐，精制油，香皂这样的顺序购买的话，Grant老板会问你要$13.80$元；而如果你按照精制油，香皂，可乐这样的顺序购买的话，您只需付$13.50$元。
现在该村的居民请你编写一个程序，告诉你Grant小店商品的原价，所有优惠方案及所需的商品，计算至少需要花多少钱。不允许购买任何不需要的商品，即使这样做可能使花得钱更少。

---

题目分析

发现优惠关系构成有向图。
有向图求最小生成树$\rightarrow$朱刘算法。

注意本题有坑：若优惠关系构成环，可以先购买任意一个，然后整个环上的商品都可以优惠。

---

代码

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
 
inline const int Get_Int() {
	int num=0,bj=1;
	char x=getchar();
	while(x<'0'||x>'9') {
		if(x=='-')bj=-1;
		x=getchar();
	}
	while(x>='0'&&x<='9') {
		num=num*10+x-'0';
		x=getchar();
	}
	return num*bj;
}
 
const int maxn=55;
 
struct Edge {
	int from,to;
	double dist;
	Edge(int x=0,int y=0,double v=0):from(x),to(y),dist(v) {}
};
 
 
double Directed_MST(int n,vector<Edge>edges,int root) {
	double ans=0;
	static double in[maxn];
	static int id[maxn],pre[maxn],vst[maxn];
	while(true) {
		//找最小入边
		for(int i=1; i<=n; i++)in[i]=1e18;
		for(Edge& e:edges) {
			int x=e.from,y=e.to;
			if(x==y)continue;
			if(e.dist<in[y]) {
				pre[y]=x;
				in[y]=e.dist;
			}
		}
		//找环
		memset(id,0,sizeof(id));
		memset(vst,0,sizeof(vst));
		int cnt=0;
		in[root]=0;
		for(int i=1; i<=n; i++) {
			ans+=in[i];
			int now;
			for(now=i; vst[now]!=i&&!id[now]&&now!=root; now=pre[now])vst[now]=i; //找环
			if(now!=root&&!id[now]) { //缩点
				id[now]=++cnt;
				for(int p=pre[now]; p!=now; p=pre[p])id[p]=cnt;
			}
		}
		if(cnt==0)break; //无环
		for(int i=1; i<=n; i++)
			if(!id[i])id[i]=++cnt;
		for(Edge& e:edges) {
			int &x=e.from,&y=e.to;
			if(x!=y)e.dist-=in[y];
			x=id[x];
			y=id[y];
		}
		n=cnt;
		root=id[root];
	}
	return ans;
}
 
int n,cnt=1,root=1,id[maxn];
double ans=0,a[maxn],num[maxn];
vector<Edge>edges;
 
int main() {
	n=Get_Int();
	for(int i=1; i<=n; i++) {
		int x;
		double v;
		scanf("%lf%d",&v,&x);
		if(x) {
			id[i]=++cnt;
			edges.push_back(Edge(root,cnt,v));
			a[cnt]=v;
			num[cnt]=x-1;
		}
	}
	n=cnt;
	int tmp=Get_Int();
	for(int i=1; i<=tmp; i++) {
		int x,y;
		double v;
		scanf("%d%d%lf",&x,&y,&v);
		if(!id[x]||!id[y])continue;
		edges.push_back(Edge(id[x],id[y],v));
		a[id[y]]=min(a[id[y]],v);
	}
	for(int i=2; i<=n; i++)ans+=a[i]*num[i];
	printf("%0.2lf\n",Directed_MST(n,edges,root)+ans);
	return 0;
}