最小树形图
最小树形图模板题，朱-刘算法。
题解：http://blog.csdn.net/shuangde800/article/details/8039359
这位大神代码写的非常通俗易懂，而且这种代码风格也很值得学习……面向对象？= =听说这样封装起来可以避免using namespace std;出现的奇葩错误
写错的地方：一开始找最小前驱边的时候 把 “!inc[i]"的叹号丢了……
//POJ 3164
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;++i)
#define F(i,j,n) for(int i=j;i<=n;++i)
#define D(i,j,n) for(int i=j;i>=n;--i)
using namespace std;
void read(int &v){
v=; int sign=; char ch=getchar();
while(ch<''||ch>''){ if (ch=='-') sign=-; ch=getchar();}
while(ch>=''&&ch<=''){ v=v*+ch-''; ch=getchar();}
v*=sign;
}
/******************tamplate*********************/
const int N=;
const int INF=~0u>>;
template<typename Type>
class Directed_MST{
public:
void init(int _n){
n=_n;
ans=;
memset(vis,,sizeof vis);
memset(inc,,sizeof inc);
F(i,,n){
w[i][i]=INF;
F(j,i+,n) w[i][j]=w[j][i]=INF;
}
}
void insert(int x,int y,Type _w){
if (w[x][y]>_w) w[x][y]=_w;
}
Type directed_mst(int x){
#ifdef debug
F(i,,n){
F(j,,n)
if (w[i][j]==INF) printf(" INF ");
else printf("%.2f ",w[i][j]);
printf("\n");
}
#endif
// step1 判断能否形成最小树形图，直接dfs遍历
dfs(x);
F(i,,n) if(!vis[i]) return -; // 如果可以形成最小树形图，继续
// step2
memset(vis,,sizeof vis);
while(){
//1.找最小前驱边
F(i,,n) if (i!=x && !inc[i]){
w[i][i]=INF, pre[i]=i;
F(j,,n)
if(!inc[j] && w[j][i]<w[pre[i]][i])
pre[i]=j;
}
//2.判断是否有环
int i;
for(i=;i<=n;++i) if (i!=x && !inc[i]){
int j=i,cnt=;
while(j!=x && pre[j]!=i && cnt<=n) j=pre[j],++cnt;
if (j==x || cnt>n) continue;
break;
} //没有找到环，找到答案
if (i>n){
F(i,,n)
if (i!=x && !inc[i]) ans+=w[pre[i]][i];
return ans;
}
//有环，进行收缩
int j=i;
memset(vis,,sizeof vis);
do{
ans+=w[pre[j]][j],j=pre[j],vis[j]=inc[j]=true;
}while(j!=i);
inc[i]=false;//!!!!环缩成了点i,点i依然存在 //收缩
F(k,,n) if(vis[k])
F(j,,n) if(!vis[j]){
if (w[i][j]>w[k][j]) w[i][j]=w[k][j];
if (w[j][k]<INF && w[j][k]-w[pre[k]][k] < w[j][i])
w[j][i]=w[j][k]-w[pre[k]][k];
}
}
return ans;
} private:
void dfs(int x){
vis[x]=;
F(i,,n) if (!vis[i] && w[x][i]<INF)
dfs(i);
}
private:
Type ans;
int n;
int pre[N];
bool vis[N],inc[N];
Type w[N][N];
};
struct node{
double x,y;
double operator - (const node&now)const{
return sqrt( (x-now.x)*(x-now.x)+(y-now.y)*(y-now.y) );
}
}a[N]; Directed_MST<double>G; int main(){
int n,m,x,y;
while(scanf("%d%d",&n,&m)!=EOF){
G.init(n);
F(i,,n) scanf("%lf%lf",&a[i].x,&a[i].y); F(i,,m){
scanf("%d%d",&x,&y);
if (x==y) continue;
G.insert(x,y,a[x]-a[y]);
}
double ans=G.directed_mst();
if (ans<) puts("poor snoopy");
else printf("%.2f\n",ans);
}
return ;
}