BZOJ 2260 商店购物（最小树形图）

不会最小树形图的出门左转

其实如果确定每种商品第一件的购买顺序，那么剩下的商品肯定是以最优惠价格购买的。

如何确定各种商品第一件购买时的最小价值呢？

考虑如果购买了\(a_i\)这种商品，那么就能以\(c_i\)的价格购买\(b_i\)这种商品，考虑从\(a_i\)往\(b_i\)连权值为\(c_i\)的有向边。

初始建一个额外的\(S\)点往所有点i连权值为\(v_i\)的有向边。

然后用朱刘算法求一遍最小树形图就行了。

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cmath>

#include<algorithm>

using namespace std;

#define int long long

const double INF=1e9;

const int N=110;

const int M=10100;

int n,m,r,tru[N];

double ans,mn[N],c[N],num[N];

struct edge{

	int u,v;

	double w;

}e[M];

int cnt,id[N],top[N],fa[N];

bool work(){

	while(2333){

		memset(id,0,sizeof(id));

		memset(top,0,sizeof(top));

		for(int i=1;i<=n;i++)mn[i]=INF;

		for(int i=1;i<=m;i++)

			if(e[i].u!=e[i].v&&e[i].w<mn[e[i].v])

				fa[e[i].v]=e[i].u,mn[e[i].v]=e[i].w;

		mn[r]=0;fa[r]=0;

		for(int i=1;i<=n;i++)if(mn[i]==INF)return false;

		int u;

		for(int i=1;i<=n;i++){

			ans+=mn[i];

			for(u=i;u!=r&&top[u]!=i&&!id[u];u=fa[u])top[u]=i;

			if(u!=r&&!id[u]){

				id[u]=++cnt;

				for(int v=fa[u];v!=u;v=fa[v])id[v]=cnt;

			}

		}

		if(!cnt)return true;

		for(int i=1;i<=n;i++)if(!id[i])id[i]=++cnt;

		for(int i=1;i<=m;i++){

			double last=mn[e[i].v];

			e[i].u=id[e[i].u];e[i].v=id[e[i].v];

			if(e[i].u!=e[i].v)e[i].w-=last;

		}

		n=cnt;

		r=id[r];

		cnt=0;

	}

}

int read(){

	int sum=0,f=1;char ch=getchar();

	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

	while(ch>='0'&&ch<='9'){sum=sum*10+ch-'0';ch=getchar();}

	return sum*f;

}

signed main(){

	int tot=read();n=0;

	for(int i=1;i<=tot;i++){

		scanf("%lf",&c[++n]);

		num[n]=read()-1;

		if(num[n]<0){n--;continue;}

		tru[i]=n;

	}

	m=read();

	r=++n;

	for(int i=1;i<=n-1;i++)e[m+i].u=r,e[m+i].v=i,e[m+i].w=c[i];

	for(int i=1;i<=m;i++){

		int u=read(),v=read();

		double w;

		scanf("%lf",&w);

		if(tru[v]==0||tru[u]==0)continue;

		e[i].u=tru[u];e[i].v=tru[v];e[i].w=w;

		c[tru[v]]=min(c[tru[v]],w);

	}

	m+=n-1;

	for(int i=1;i<=n-1;i++)ans+=num[i]*c[i];

	if(work())printf("%.2lf",ans);

	else printf("-1");

	return 0;

}

巴特西

BZOJ 2260 商店购物（最小树形图）

最新文章

热门文章