传送门：poj6187 Destroy Walls
图中只要没环即可。
一开始，这题怎么也没想明白，有的大佬题解里说到了平面图和对偶图，在了解了这两个图后再来看这个题，简直豁然开朗！
啊哈哈！可能也没有直接的关系。
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<map>
using namespace std;
const int INF=0x3f3f3f3f;
struct Edge{int s,e,w; //起点，终点，权值 Edge(int s_,int e_,int w_):s(s_),e(e_),w(w_){}Edge(){}bool operator <(const Edge &e)const{return w>e.w; }
};
int n,m,ans=0;
vector<Edge> E;
vector<int> par;int fi(int x){if(par[x]!=x) return par[x]=fi(par[x]);return x;
}void join(int x,int y){int fx=fi(x),fy=fi(y);if(fx!=fy) par[fy]=fx;
}void Kruskal(){sort(E.begin(),E.end());int cnt=0;for(int i=0;i<E.size();i++){if(fi(E[i].s)!=fi(E[i].e)){join(E[i].s,E[i].e); }else{cnt++;ans+=E[i].w;}//if(cnt==n-1) break;}printf("%d %d\n",cnt,ans);
}int main(){while(cin>>n>>m){E.clear();par.clear();int x,y;par.push_back(0);for(int i=1;i<=n;i++){par.push_back(i);scanf("%d%d",&x,&y);}ans=0;int u,v,w;for(int i=0;i<m;i++){scanf("%d%d%d",&u,&v,&w);E.push_back(Edge(u,v,w));}Kruskal();}
}