「bzoj4349」最小树形图 - 最小树形图

题目大意

    小C现在正要攻打科学馆腹地———计算机第三机房。而信息组的同学们已经建好了一座座堡垒，准备迎战。小C作为一种高度智慧的可怕生物，早已对同学们的信息了如指掌。
    攻打每一个人的堡垒需要一个代价，而且必须攻打若干次才能把镇守之人灭得灰飞烟灭。
    当小C在绞尽脑汁想攻打方案时，突然从XXX的堡垒中滚出来一个纸条：一个惊人的秘密被小C发现了：原来各个堡垒之间会相互提供援助，但是当一个堡垒被攻打时，他对所援助的堡垒的援助就会停止，因为他自己已经自身难保了。也就是说，小C只要攻打某个堡垒一次之后，某些堡垒就只需要花更小的代价攻击了。
    现在，要你求消灭全机房要用掉代价最小多少。

---

题目分析

和上一题一模一样。

---

代码

#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;
double ans=0,a[maxn],num[maxn];
vector<Edge>edges;

int main() {
	n=Get_Int();
	int root=n+1;
	for(int i=1; i<=n; i++) {
		int x;
		double v;
		scanf("%lf%d",&v,&x);
		edges.push_back(Edge(root,i,v));
		a[i]=v;
		num[i]=x-1;
	}
	int tmp=Get_Int();
	for(int i=1; i<=tmp; i++) {
		int x,y;
		double v;
		scanf("%d%d%lf",&x,&y,&v);
		edges.push_back(Edge(x,y,v));
		a[y]=min(a[y],v);
	}
	for(int i=1; i<=n; i++)ans+=a[i]*num[i];
	printf("%0.2lf\n",Directed_MST(n+1,edges,root)+ans);
	return 0;
}