emmm,其实也没什么,很简单的模版题. 提示了一个性质,取出生成树后,剩下的区域将不可能封闭. 不是很晦涩,但是也不是一定知道. aizu真好啊,日本真好啊,真好啊真好啊.
/* xzppp */ #include <iostream> #include <vector> #include <cstdio> #include <string.h> #include <algorithm> #include <queue> #include <map> #include <string> #include <cmath> #include <set> #include <iomanip> using namespace std; #define FFF freopen("in.txt","r",stdin);freopen("out.txt","w",stdout); #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define MP make_pair #define PB push_back typedef long long LL; typedef unsigned long long ULL; typedef pair<int,int > pii; typedef pair<double,double > pdd; typedef pair<double,int > pdi; const int MAXN = 1e4+17; const int MAXM = 20; const int MAXV = 1e4+17; const int INF = 0x7fffffff; const int MOD = 1e9+7; pdd all[MAXV]; vector<pdi > G[MAXV]; double s; bool vis1[MAXV]; void dfs(int x) { vis1[x]=1; for (int i = 0; i < G[x].size(); ++i) { if(!vis1[G[x][i].second]) { s+=G[x][i].first; } } for (int i = 0; i < G[x].size(); ++i) { if(!vis1[G[x][i].second]) { dfs(G[x][i].second); } } } bool vis[MAXV]; double minc[MAXV]; double prim(int x) { for (int i = 0; i < MAXV; ++i) { minc[i] = 0; vis[i] = 0; } double res = 0; priority_queue<pdi> q; q.push(MP(0,x)); while(!q.empty()) { int v = q.top().second; double temp = q.top().first; q.pop(); if(vis[v]) continue; vis[v] = 1; res += temp; for (int i = 0; i < G[v].size(); ++i) { double d = G[v][i].first; int to = G[v][i].second; if(!vis[to]&&minc[to]<d) { q.push(MP(d,to)); minc[to] = d; } } } return res; } int main() { #ifndef ONLINE_JUDGE //FFF #endif int n,m; cin>>n>>m; for (int i = 0; i < n; ++i) { double x,y; scanf("%lf%lf",&x,&y); all[i].first = x; all[i].second = y; } for (int i = 0; i < m; ++i) { int u,v; scanf("%d%d",&u,&v); u--;v--; double dis = sqrt((all[u].first-all[v].first)*(all[u].first-all[v].first) +(all[u].second-all[v].second)*(all[u].second-all[v].second)); G[u].push_back(MP(dis,v)); G[v].push_back(MP(dis,u)); } double ans = 0; for (int i = 0; i < n; ++i) { if(!vis1[i]) { s = 0; dfs(i); double left = prim(i); ans += s-left; } } cout<<fixed<<setprecision(4)<<ans<<endl; return 0; }