最小树形图

  1 //POJ 3164  2 #include<cmath>  3 #include<cstdio>  4 #include<cstring>  5 #include<cstdlib>  6 #include<iostream>  7 #include<algorithm>  8 #define rep(i,n) for(int i=0;i<n;++i)  9 #define F(i,j,n) for(int i=j;i<=n;++i) 10 #define D(i,j,n) for(int i=j;i>=n;--i) 11 using namespace std; 12 void read(int &v){ 13     v=0; int sign=1; char ch=getchar(); 14     while(ch<‘0‘||ch>‘9‘){ if (ch==‘-‘) sign=-1; ch=getchar();} 15     while(ch>=‘0‘&&ch<=‘9‘){ v=v*10+ch-‘0‘; ch=getchar();} 16     v*=sign; 17 } 18 /******************tamplate*********************/ 19 const int N=110; 20 const int INF=~0u>>2; 21 template<typename Type> 22 class Directed_MST{ 23     public: 24     void init(int _n){ 25         n=_n; 26         ans=0; 27         memset(vis,0,sizeof vis); 28         memset(inc,0,sizeof inc); 29         F(i,0,n){ 30             w[i][i]=INF; 31             F(j,i+1,n) w[i][j]=w[j][i]=INF; 32         } 33     } 34     void insert(int x,int y,Type _w){ 35         if (w[x][y]>_w) w[x][y]=_w; 36     } 37     Type directed_mst(int x){ 38 #ifdef debug 39         F(i,1,n){ 40             F(j,1,n)  41                 if (w[i][j]==INF) printf(" INF "); 42                 else printf("%.2f ",w[i][j]); 43             printf("\n"); 44         } 45 #endif 46         // step1 判断能否形成最小树形图，直接dfs遍历 47         dfs(x); 48         F(i,1,n) if(!vis[i]) return -1; 49          50         // 如果可以形成最小树形图，继续 51         // step2 52         memset(vis,0,sizeof vis); 53         while(1){ 54             //1.找最小前驱边 55             F(i,1,n) if (i!=x && !inc[i]){ 56                 w[i][i]=INF, pre[i]=i; 57                 F(j,1,n)  58                     if(!inc[j] && w[j][i]<w[pre[i]][i]) 59                         pre[i]=j; 60             } 61             //2.判断是否有环 62             int i; 63             for(i=1;i<=n;++i) if (i!=x && !inc[i]){ 64                 int j=i,cnt=0; 65                 while(j!=x && pre[j]!=i && cnt<=n) j=pre[j],++cnt; 66                 if (j==x || cnt>n) continue; 67                 break; 68             } 69                  70             //没有找到环，找到答案 71             if (i>n){ 72                 F(i,1,n) 73                     if (i!=x && !inc[i]) ans+=w[pre[i]][i]; 74                 return ans; 75             } 76             //有环，进行收缩 77             int j=i; 78             memset(vis,0,sizeof vis); 79             do{ 80                 ans+=w[pre[j]][j],j=pre[j],vis[j]=inc[j]=true; 81             }while(j!=i); 82             inc[i]=false;//!!!!环缩成了点i,点i依然存在 83              84             //收缩 85             F(k,1,n) if(vis[k]) 86                 F(j,1,n) if(!vis[j]){ 87                     if (w[i][j]>w[k][j]) w[i][j]=w[k][j]; 88                     if (w[j][k]<INF && w[j][k]-w[pre[k]][k] < w[j][i]) 89                         w[j][i]=w[j][k]-w[pre[k]][k]; 90                 } 91         } 92         return ans; 93     } 94  95     private: 96     void dfs(int x){ 97         vis[x]=1; 98         F(i,1,n) if (!vis[i] && w[x][i]<INF) 99             dfs(i);100     }101     private:102     Type ans;103     int n;104     int pre[N];105     bool vis[N],inc[N];106     Type w[N][N];107 };108 struct node{109     double x,y;110     double operator - (const node&now)const{111         return sqrt( (x-now.x)*(x-now.x)+(y-now.y)*(y-now.y) );112     }113 }a[N];114 115 Directed_MST<double>G;116 117 int main(){118     int n,m,x,y;119     while(scanf("%d%d",&n,&m)!=EOF){120         G.init(n);121         F(i,1,n) scanf("%lf%lf",&a[i].x,&a[i].y);122         123         F(i,1,m){124             scanf("%d%d",&x,&y);125             if (x==y) continue;126             G.insert(x,y,a[x]-a[y]);127         }128         double ans=G.directed_mst(1);129         if (ans<0) puts("poor snoopy");130         else printf("%.2f\n",ans);131     }132     return 0;133 }