http://poj.org/problem?id=3164
第一次做最小树形图,看着别人的博客写,还没弄懂具体的什么意思。
1 #include <cstdio> 2 #include <cstring> 3 #include <cmath> 4 #include <algorithm> 5 #define maxn 1000 6 using namespace std; 7 const int inf=1<<28; 8 9 int n,m; 10 double g[maxn][maxn]; 11 bool vis[maxn]; 12 int cicl[maxn]; 13 int pre[maxn]; 14 struct node 15 { 16 double x,y; 17 }p[maxn]; 18 19 double sqr(int x) 20 { 21 return x*x; 22 } 23 24 double dis(int a,int b) 25 { 26 return sqrt(sqr(p[a].x-p[b].x)+sqr(p[a].y-p[b].y)); 27 } 28 29 void dfs(int s) 30 { 31 if(vis[s]) return ; 32 vis[s]=true; 33 for(int i=1; i<=n; i++) 34 { 35 if(g[s][i]<inf) 36 { 37 dfs(i); 38 } 39 } 40 } 41 42 bool deal() 43 { 44 dfs(1); 45 for(int i=1; i<=n; i++) 46 { 47 if(!vis[i]) return false; 48 } 49 return true; 50 } 51 52 double solve() 53 { 54 double ans=0; 55 int i; 56 memset(cicl,0,sizeof(cicl)); 57 while(1) 58 { 59 for(i=2; i<=n; i++) 60 { 61 if(cicl[i]) continue; 62 g[i][i]=inf; 63 pre[i]=i; 64 for(int j=1; j<=n; j++) 65 { 66 if(cicl[j]) continue; 67 if(g[j][i]<g[pre[i]][i]) 68 { 69 pre[i]=j; 70 } 71 } 72 } 73 int j; 74 for(i=2; i<=n; i++) 75 { 76 if(cicl[i]) continue; 77 j=i; 78 memset(vis,false,sizeof(vis)); 79 while(!vis[j]&&j!=1) 80 { 81 vis[j]=true; 82 j=pre[j]; 83 } 84 if(j==1) continue; 85 i=j; 86 ans+=g[pre[i]][i]; 87 for(j=pre[i]; j!=i; j=pre[j]) 88 { 89 ans+=g[pre[j]][j]; 90 cicl[j]=1; 91 } 92 for(j=1; j<=n; j++) 93 { 94 if(cicl[j]) continue; 95 if(g[j][i]<inf) 96 { 97 g[j][i]-=g[pre[i]][i]; 98 } 99 } 100 for(j=pre[i]; j!=i; j=pre[j]) 101 { 102 for(int k=1; k<=n; k++) 103 { 104 if(cicl[k]) continue; 105 if(g[j][k]<inf) 106 { 107 g[i][k]=min(g[i][k],g[j][k]); 108 } 109 if(g[k][j]<inf) 110 { 111 g[k][i]=min(g[k][i],g[k][j]-g[pre[j]][j]); 112 } 113 } 114 } 115 break; 116 } 117 if(i>n) 118 { 119 for(j=2; j<=n; j++) 120 { 121 if(cicl[j]) continue; 122 ans+=g[pre[j]][j]; 123 } 124 break; 125 } 126 } 127 return ans; 128 } 129 130 int main() 131 { 132 while(scanf("%d%d",&n,&m)!=EOF) 133 { 134 for(int i=0; i<=n; i++) 135 { 136 for(int j=0; j<=n; j++) 137 { 138 g[i][j]=inf; 139 } 140 } 141 for(int i=1; i<=n; i++) 142 { 143 scanf("%lf%lf",&p[i].x,&p[i].y); 144 } 145 for(int i=0; i<m; i++) 146 { 147 int s,t; 148 scanf("%d%d",&s,&t); 149 g[s][t]=dis(s,t); 150 } 151 memset(vis,false,sizeof(vis)); 152 if(!deal()) 153 { 154 printf("poor snoopy\n"); 155 } 156 else printf("%.2lf\n",solve()); 157 } 158 return 0; 159 }