逐个击破
题目
Description
三大战役的平津战场上，傅作义集团在以北平、天津为中心，东起唐山西至张家口的铁路线上摆起子一字长蛇阵，并企图在溃败时从海上南逃或向西逃窜。为了就地歼敌不让其逃走，***制定了先切断敌人东洒两头退路然后再逐个歼灭敌人的战略方针。 秉承伟大军事家的战略思想，作为一个有智慧的军长你，遇到了一个类似的战场局面： 现在有N个城市，其中K个被敌方军团占领了，N个城市间有N-1条公路相连，破坏其中某条公路的代价是已知的，现在，告诉你K个敌方军团所在的城市，以及所有公路破坏的代价，请你算出花费最少的代价将这K个地方军团互相隔离开，以便第二步逐个击破敌人。
Input
第一行包含两个正整数n和k。 第二行包含k个整数，表示哪个城市别敌军占领。 接下来n-1行，每行包含三个正整数a,b,c，表示从a城市到b城市有一条公路，以及破坏的代价c。 城市的编号从0开始计数。
Output
包含一个整数，表示最少花费的代价。
Sample Input
3 3 0 1 2 0 1 1 1 2 2
Sample Output
3
Data Constraint
2<=n<=100000 2<=k<=n 1<=c<=1000000
题解
题意
有n个点，其中有k个点是黑色，剩下点是白色 给出n-1条边，现在要割去某些边使得黑点与黑点之间不相连，问最小代价
分析
逆向思维 构造一棵合法的最大生成树 用总代价减去即可 树的边与边连不连取决于两个集合内黑点的数量，如果相加小于等于1就可以连
Code
#include<bits/stdc++.h>
using namespace std
;
struct node
{
int x
,y
,z
;
}a
[100005];
int n
,k
,x
,xx
,yy
,f
[100005],gz
[100005],b
[100005];
long long s
,ans
;
bool cmp(node x
,node y
)
{
return x
.z
>y
.z
;
}
int find(int x
)
{
if (f
[x
]!=x
) f
[x
]=find(f
[x
]);
return f
[x
];
}
int read()
{
int res
=0;char ch
=getchar();
while (ch
<'0'||ch
>'9') ch
=getchar();
while (ch
>='0'&&ch
<='9') res
=(res
<<1)+(res
<<3)+(ch
-'0'),ch
=getchar();
return res
;
}
int main()
{
n
=read();k
=read();
for (int i
=1;i
<=k
;++i
)
x
=read(),b
[x
]=1;
s
=0;
for (int i
=1;i
<n
;++i
)
a
[i
].x
=read(),a
[i
].y
=read(),a
[i
].z
=read(),s
+=a
[i
].z
;
sort(a
+1,a
+n
,cmp
);
for (int i
=0;i
<=n
;++i
)
f
[i
]=i
;
for (int i
=1;i
<n
;++i
)
{
xx
=find(a
[i
].x
);yy
=find(a
[i
].y
);
if (b
[xx
]+b
[yy
]<=1)
{
b
[yy
]=b
[xx
]+b
[yy
];
f
[xx
]=yy
;
ans
+=a
[i
].z
;
}
}
printf("%lld\n",s
-ans
);
return 0;
}
