隐藏
「bzoj4349」最小树形图 - 最小树形图 | Bill Yang's Blog

路终会有尽头,但视野总能看到更远的地方。

0%

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

题目大意

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


题目分析

上一题一模一样。


代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#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;
}
姥爷们赏瓶冰阔落吧~