P2700 逐个击破最小生成树

本文主要是介绍P2700 逐个击破最小生成树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

现在有N个城市，其中K个被敌方军团占领了，N个城市间有N-1条公路相连，破坏其中某条公路的代价是已知的，现在，告诉你K个敌方军团所在的城市，以及所有公路破坏的代价，请你算出花费最少的代价将这K个地方军团互相隔离开，以便第二步逐个击破敌人。

输入输出格式

输入格式：

第一行包含两个正整数n和k。

第二行包含k个整数，表示哪个城市别敌军占领。

接下来n-1行，每行包含三个正整数a,b,c，表示从a城市到b城市有一条公路，以及破坏的代价c。城市的编号从0开始。

输出格式：

输出一行一个整数，表示最少花费的代价。

输入输出样例

输入样例#1：复制

输出样例#1：复制

说明

【数据范围】

10%的数据：2≤n≤10；

100%的数据：2≤n≤100000，2≤k≤n，1≤c≤1000000。

要求的是拆掉最短的路使得给出的点分割

很容易想到用最小生成树来做

但是正面做很难处理比如 1-2-3-4 假如1和4是要分隔的点很难确定该怎么拆边

可以把这题反过来看：要求的是拆掉最短的路使得给出的点分隔反过来就是所有路的权值-（假设一开始都没有连接）连上最大的路使得给出的点是分隔状态（其实就是把所有不“关键”路连上留下的是关键路的最小权值）

显然要从大到小排列 “最大”生成树

#include<bits/stdc++.h>
using namespace std;
//input by bxd
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repp(i,a,b) for(int i=(a);i>=(b);i--)
#define RI(n) scanf("%d",&(n))
#define RII(n,m) scanf("%d%d",&n,&m)
#define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k)
#define RS(s) scanf("%s",s);
#define LL long long
#define pb push_back
#define fi first
#define REP(i,N)  for(int i=0;i<(N);i++)
#define CLR(A,v)  memset(A,v,sizeof A)
///
#define inf 0x3f3f3f3f
#define N 100000+5
int f[N];
int vis[N];
int n;
int find1(int x)
{return f[x]==x?x:find1(f[x]);
}
struct node
{int s,e,v;
}edge[N];bool cmp(node a,node b)
{return a.v>b.v;
}
long long kruskal(void )
{long long ans=0;sort(edge+1,edge+n-1,cmp);rep(i,1,n-1){int a=find1(edge[i].s);int b=find1(edge[i].e);int c=edge[i].v;if(vis[a]&&vis[b])continue;if(!vis[a]&&!vis[b]){ans+=c;f[a]=b;continue;}//剩下的最后两种情况ans+=c;f[a]=b;vis[find1(a)]=1;}return ans;
}int main()
{int m;RII(n,m);rep(i,0,n)f[i]=i;while(m--){int x;RI(x);vis[x]=1;}long long sum=0;rep(i,1,n-1){RIII(edge[i].s,edge[i].e,edge[i].v);sum+=edge[i].v;}printf("%lld",sum-kruskal());
}