hdu4313Matrix(kruskal模板题，cmp倒着取边)

题目&＃xff1a;http://acm.hdu.edu.cn/showproblem.php?pid&＃61;4313

题意&＃xff1a;有n个城市&＃xff0c;有n-1条边连通&＃xff0c;其中的k个城市有破坏机器&＃xff0c;要求切断部分路&＃xff0c;使得这k个城市之间不能连通&＃xff0c;每条路对应不同的花费时间&＃xff0c;求最少花费。

思路&＃xff1a;以含“破坏机器”的城市作为根结点&＃xff0c;分为k棵树&＃xff0c;每加入一条边&＃xff0c;判断该边的两个端点所对应的祖先是不是都含“机器”&＃xff0c;若都含不连这条边直接在ans上加&＃xff0c;其他情况的只要在join函数中改下条件即可&＃xff0c;两者若其中之一含机器&＃xff0c;那么不含“机器”的点接在含“机器”的点下&＃xff0c;若都不含机器&＃xff0c;就随便接好了。

注意 1.因为要使去掉的边代价最小&＃xff0c;即越后面加入的越有可能不符合条件&＃xff0c;即需要按边从大到小排序(即cmp倒着来)。

        2.ans 是 long long &＃xff0c; kruskal() 函数的返回类型也要改为long long(一开始WA在这里)

#include
#pragma GCC optimize(3)
//#pragma GCC optimize("unroll-loops")
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune&＃61;native")
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define pb push_back
#define mkp(a,b) make_pair(a,b)
#define PII pair
#define PLL pair
#define fi first
#define se second
#define lc (d<<1) //d*2
#define rc (d<<1|1) //d*2&＃43;1
#define eps 1e-9
#define dbg(x) cerr <<#x <<" &＃61; " <#define mst(a,val) memset(a,val,sizeof(a))
#define stn(a) setprecision(a)//小数总有效位数
#define stfl setiosflags(ios::fixed)//点后位数:cout<using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const double PI&＃61;3.1415926535897932;
const int MAXN&＃61;1e5&＃43;10;
const ll mod&＃61;1e9&＃43;7;
ll inline mpow(ll a,ll b){ll ans&＃61;1;a%&＃61;mod;while(b){if(b&1)ans&＃61;(ans*a)%mod;a&＃61;(a*a)%mod,b>>&＃61;1;}return ans;}
int inline sgn(double x){return (x>-eps)-(xpriority_queue,greater > qu; //up
priority_queue,less > qd; //dn
const int inf &＃61; 0x3f3f3f3f; //9
const ll inff &＃61; 0x3f3f3f3f3f3f3f3f; //18int T;
int n,k;
int x,y,z;
int id[100010];//并查集
int pre[100010];
inline void init(int n) {for(int i&＃61;0;i<&＃61;n;i&＃43;&＃43;) pre[i]&＃61;i;}
inline int find(int x)
{int r&＃61;x,i&＃61;x,j;while(pre[r]!&＃61;r) r&＃61;pre[r];while(i!&＃61;r) {j&＃61;pre[i];pre[i]&＃61;r;i&＃61;j;}return r;
}
inline void join(int x,int y)
{int a&＃61;find(x),b&＃61;find(y);if(id[a]) pre[b]&＃61;a;else pre[a]&＃61;b;
}
//kruskal
int Ver,E;
struct Edg {int u,v,d;}edg[100010];
inline bool cmp(Edg a,Edg b) {return a.d>b.d;}
inline ll kruskal()
{sort(edg,edg&＃43;E,cmp);ll ans&＃61;0;for(int i&＃61;0;i}int main()
{fio;cin>>T;while(T--){cin>>n>>k;init(n); Ver&＃61;n; E&＃61;n-1;mst(id,0);for(int i&＃61;0;i>edg[i].u>>edg[i].v>>edg[i].d;for(int i&＃61;0;i>tmp; id[tmp]&＃61;1;}ll ans&＃61;kruskal();cout<}