给出平面上一些点，和连接它们的带权有向边，求把所有点连起来的最小总权值。
分析
由于这里边是有向的(unidirectional)，所以这是经典的最小树形图问题，可以说是最小树形图的模板题。
代码
这个写法是我乱想的。最近写图啊树啊都喜欢开一个结构体～
这个代码在poj上交，如果用g++的话会WA，因为奇怪的poj需要用%f输出浮点数。更奇怪的是c++直接编译错误，不想说了。
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=202;
const double inf=1e100;
bool bian[maxn][maxn];
struct node {
double x,y;
} a[maxn];
double dist(node &a,node &b) {
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
struct edge {
int v;
double w;
int nxt;
};
struct graph {
edge e[maxn*maxn];
int h[maxn],tot,n,from[maxn],tic[maxn],tim,root,sta[maxn],top;
double in[maxn],mi[maxn];
bool vis[maxn],able[maxn];
void clear() {
memset(h,0,sizeof h);
tot=0;
}
void add(int u,int v,double w) {
e[++tot]=(edge){v,w,h[u]};
h[u]=tot;
}
void dfs(int x) {
vis[x]=true;
for (int i=h[x],v=e[i].v;i;i=e[i].nxt,v=e[i].v) if (able[v]) {
if (v!=root && in[v]>e[i].w) in[v]=e[i].w,from[v]=x;
if (!vis[v]) dfs(v);
}
}
bool circle() {
memset(tic,0,sizeof tic),tim=0;
for (int i=1;i<=n;++i) if (able[i]) {
++tim;
top=0;
for (int j=i;j;j=from[j]) if (!tic[j]) tic[j]=tim,sta[++top]=j; else if (tic[j]==tim) {
for (int k=1;k<=n;++k) if (tic[k]==tim) tic[k]=0;
do {
tic[sta[top--]]=tim;
} while (sta[top+1]!=j);
return true;
}
}
return false;
}
bool work(double &ret) {
memset(vis,0,sizeof vis);
fill(in+1,in+n+1,inf);
dfs(root);
for (int i=1;i<=n;++i) if (able[i] && !vis[i]) {
ret=-1;
return false;
}
bool cc=circle();
if (cc) {
for (int i=1;i<=n;++i) if (able[i] && i!=root && tic[i]==tim) ret+=in[i];
} else {
for (int i=1;i<=n;++i) if (able[i] && i!=root) ret+=in[i];
}
return cc;
}
void reduce() {
fill(mi+1,mi+n+1,inf);
for (int i=1;i<=n;++i) if (able[i] && tic[i]!=tim) {
double w=inf;
for (int j=h[i],v=e[j].v;j;j=e[j].nxt,v=e[j].v) if (tic[v]==tim) w=min(w,e[j].w-in[v]);
if (w!=inf) add(i,n+1,w);
}
for (int i=1;i<=n;++i) if (able[i] && tic[i]==tim) for (int j=h[i],v=e[j].v;j;j=e[j].nxt,v=e[j].v) if (able[v] && tic[v]!=tim) mi[v]=min(mi[v],e[j].w);
for (int i=1;i<=n;++i) if (able[i] && tic[i]!=tim && mi[i]!=inf) add(n+1,i,mi[i]);
for (int i=1;i<=n;++i) if (tic[i]==tim) able[i]=false;
++n;
if (!able[root]) root=n;
}
double MGT(int _n) {
memset(able,true,sizeof able),n=_n,root=1;
double ret=0;
while (work(ret)) {
reduce();
}
return ret;
}
} A;
int main() {
#ifndef ONLINE_JUDGE
freopen("test.in","r",stdin);
freopen("my.out","w",stdout);
#endif
int n,m;
while (~scanf("%d%d",&n,&m)) {
A.clear();
memset(bian,0,sizeof bian);
for (int i=1;i<=n;++i) scanf("%lf%lf",&a[i].x,&a[i].y);
for (int i=1;i<=m;++i) {
int u,v;
scanf("%d%d",&u,&v);
if (u==v || bian[u][v]) continue;
bian[u][v]=true;
double d=dist(a[u],a[v]);
A.add(u,v,d);
}
double ans=A.MGT(n);
if (ans<0) puts("poor snoopy"); else printf("%.2lf\n",ans);
}
return 0;
}