NKOJ 2784 (APIO 2013) 道路费用（最小生成树+缩点）

发表于 |
字数统计: 1,495字 | 阅读时长 ≈ 8min

P2784 道路费用

问题描述
这里写图片描述
输入格式

你的程序必须从标准输入读入。第一行包含三个由空格隔开的整数N，M和K。接下来的 M行描述最开始的M 条道路。这M行中的第i行包含由空格隔开的整数ai，bi和c i，表示有一条在a i和b i之间，费用为c i的双向道路。接下来的K行描述新建的K条道路。这 K行中的第i行包含由空格隔开的整数 xi和yi，表示有一条连接城镇xi和yi新道路。最后一行包含N个由空格隔开的整数，其中的第j个为pj，表示从城镇j 前往城镇 1的人数。
输入也满足以下约束条件。

  1 ≤ N ≤ 100000；
  1 ≤ K ≤ 20；

  1 ≤ M ≤ 300000；

  对每个i和j，1 ≤ ci, pj ≤ 10^6；

输出格式

你的程序必须输出恰好一个整数到标准输出，表示能获得的最大的收入。

样例输入 

5 5 1
3 5 2
1 2 3
2 3 5
2 4 4
4 3 6
1 3
10 20 30 40 50

样例输出 

400

首先，分析题目发现，本题给出的图的最小生成树是唯一的（每条边权值不同），于是我们先求出不含K条边的最小生成树A，再求出将K条边的权值设为0后的最小生成树B，容易发现，最后的目标最小生成树C中的边，一定来自A或给出的K条边中（B中除了给出的K条边外，其他边一定也在A中）。

同时观察可得，同时在A,B中出现的边一定是必须要选的边，因此我们可以利用这些边来缩点，将这些边构成的图中每一个联通块缩成一个点，这个点的人数等于该联通块所有点的人数和。

观察发现，缩点后最多存在K+1个点，由于K很小，为了求出答案，我们容易想到枚举K条边的子集，每次将选中的边先加入生成树C中，然后拿A中没用的边来跑生成树，此时的到的生成树C就是加入该子集后的目标生成树。

最后只需要枚举加入一条没选中的边，一定构成一个环，该环上每条边的权值不能大于该边的值，最后将每条边的权值取最大值，DFS算出每条边经过的人数，统计答案即可。

代码：

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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#define N 123456
#define M 1234567
#define ll long long
using namespace std;
struct node{int x,y;ll z;};
bool cmp(node a,node b)
{return a.z<b.z;}
ll n,m,k,rt,ans,P[N],V[N],F[N],NP[N],C_cnt,NP_cnt;
node edge[M],K_edge[N],C_edge[N];
bool A_mark[M],B_mark[M],C_mark[N];
ll GF(ll v)
{
	if(F[v]!=v)F[v]=GF(F[v]);
	return F[v];
}
ll TOT,LA[N],NE[N],EN[N],TY[N];
ll K_max[N],dep[N],size[N],fa[N],pre[N];
void ADD(ll x,ll y,ll z)
{
	TOT++;
	EN[TOT]=y;
	NE[TOT]=LA[x];
	TY[TOT]=z;
	LA[x]=TOT;
}
void DFS(ll x,ll f)
{
	ll i,y;
	dep[x]=dep[f]+1;
	size[x]=V[x];
	fa[x]=f;
	for(i=LA[x];i;i=NE[i])
	{
		y=EN[i];
		if(y!=f)
		{
			DFS(y,x);
			size[x]+=size[y];
			pre[y]=TY[i];
		}
	}
}
void Work(ll S)
{
	ll i,j,x,y;TOT=0;
	for(i=1;i<=NP_cnt;i++)F[i]=i,LA[i]=0;
	for(i=1;i<=C_cnt;i++)C_mark[i]=0;
	for(i=1;i<=k;i++)K_max[i]=1e9;
	for(i=1;i<=k;i++)
	if(S&(1<<i-1))
	{
		x=GF(K_edge[i].x);
		y=GF(K_edge[i].y);
		if(x==y)return;
		F[x]=y;
		ADD(K_edge[i].x,K_edge[i].y,i);
		ADD(K_edge[i].y,K_edge[i].x,i);
	}
	for(i=1;i<=C_cnt;i++)
	{
		x=GF(C_edge[i].x);
		y=GF(C_edge[i].y);
		if(x==y)continue;
		F[x]=y;
		C_mark[i]=1;
		ADD(C_edge[i].x,C_edge[i].y,0);
		ADD(C_edge[i].y,C_edge[i].x,0);
	}
	DFS(rt,0);
	for(i=1;i<=C_cnt;i++)
	{
		if(C_mark[i])continue;
		x=C_edge[i].x;
		y=C_edge[i].y;
		while(x!=y)
		{
			if(dep[x]<dep[y])swap(x,y);
			K_max[pre[x]]=min(K_max[pre[x]],C_edge[i].z);
			x=fa[x];
		}
	}
	ll tmp=0;
	for(i=1;i<=k;i++)
	if(S&(1<<i-1))
	{
		x=K_edge[i].x;
		y=K_edge[i].y;
		if(dep[x]<dep[y])swap(x,y);
		tmp+=1ll*K_max[i]*size[x];
	}
	ans=max(ans,tmp);
}
int main()
{
	ll cnt,x,y,i,j;
	scanf("%lld%lld%lld",&n,&m,&k);
	for(i=1;i<=m;i++)scanf("%lld%lld%lld",&edge[i].x,&edge[i].y,&edge[i].z);
	for(i=1;i<=k;i++)scanf("%lld%lld",&K_edge[i].x,&K_edge[i].y);
	for(i=1;i<=n;i++)scanf("%lld",&P[i]);
	sort(edge+1,edge+m+1,cmp);
	for(j=1;j<=n;j++)F[j]=j;
	i=1;cnt=0;
	while(cnt<n&&i<=m)
	{
		x=GF(edge[i].x);
		y=GF(edge[i].y);
		if(x!=y)
		{
			cnt++;
			A_mark[i]=1;
			F[x]=y;
		}
		i++;
	}
	cnt=0;i=1;
	for(j=1;j<=n;j++)F[j]=j;
	for(j=1;j<=k;j++)
	{
		x=GF(K_edge[j].x);
		y=GF(K_edge[j].y);
		if(x!=y)
		{
			cnt++;
			F[x]=y;
		}
	}
	while(cnt<n&&i<=m)
	{
		x=GF(edge[i].x);
		y=GF(edge[i].y);
		if(x!=y)
		{
			cnt++;
			B_mark[i]=1;
			F[x]=y;
		}
		i++;
	}
	for(i=1;i<=n;i++)F[i]=i;
	for(i=1;i<=m;i++)
	{
		if(A_mark[i]&&B_mark[i])
		{
			x=GF(edge[i].x);
		    y=GF(edge[i].y);
		    F[x]=y;
		}
		else if(A_mark[i])C_edge[++C_cnt]=edge[i];
	}
	for(i=1;i<=n;i++)
	{
		x=GF(i);
		if(!NP[x])NP[x]=++NP_cnt;
		NP[i]=NP[x];
		V[NP[i]]+=P[i];
	}
	rt=NP[1];
	for(i=1;i<=k;i++)
	{
		K_edge[i].x=NP[K_edge[i].x];
		K_edge[i].y=NP[K_edge[i].y];
	}
	for(i=1;i<=C_cnt;i++)
	{
		C_edge[i].x=NP[C_edge[i].x];
		C_edge[i].y=NP[C_edge[i].y];
	}
	ll S=(1<<k)-1;
	for(i=1;i<=S;i++)Work(i);
	printf("%lld",ans);
}