最近刚学的最小树形图,终于AC了。。。
朱刘算法,详细的可以到这里看 http://www.zlinkin.com/?p=63
注意一下自环就可以了
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<algorithm> 5 #include<vector> 6 #include<stack> 7 #include<queue> 8 #include<map> 9 #include<cstdlib> 10 #include<cmath> 11 using namespace std; 12 #define ll long long 13 #define pb push_back 14 //const double eps = 1e-8; 15 const int maxn = 205; 16 const int maxm = 10005; 17 int g[maxn],pre[maxn],s[maxn]; 18 double x[maxn],y[maxn]; 19 double mc[maxn]; 20 bool vis[maxn]; 21 int nume,m,n,cnt,root; 22 struct edge 23 { 24 int v,u,nxt; 25 double c; 26 } e[maxm * 2]; 27 void init() 28 { 29 memset(g,0,sizeof(g)); 30 nume = 1; 31 } 32 double dist(double x1,double y1,double x2,double y2) 33 { 34 return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)); 35 } 36 void addedge(int u,int v,double c) 37 { 38 if (u == v) return; 39 ++nume; 40 e[nume].u = u; 41 e[nume].v = v; 42 e[nume].c = c; 43 e[nume].nxt = g[u]; 44 g[u] = nume; 45 } 46 void find_mincost() 47 { 48 memset(pre,0,sizeof(pre)); 49 for (int i = 1; i <= n; i++) mc[i] = 1000000000; 50 for (int i = 1; i <= nume; i++) 51 if (e[i].v != e[i].u) 52 { 53 if (mc[e[i].v] > e[i].c && e[i].v != root) 54 { 55 mc[e[i].v] = e[i].c; 56 pre[e[i].v] = e[i].u; 57 } 58 } 59 } 60 bool dfs(int x,int y) 61 { 62 int z = pre[x]; 63 if (z == 0) return 0; 64 if (s[z] == 0) 65 { 66 s[z] = cnt; 67 if (!dfs(z,y)) s[z] = 0; 68 else return 1; 69 } 70 else return z == y; 71 return 0; 72 } 73 void flood(int x) 74 { 75 for (int i = g[x]; i; i = e[i].nxt) 76 if (!s[e[i].v]) 77 { 78 s[e[i].v] = 1; 79 flood(e[i].v); 80 } 81 } 82 bool check() 83 { 84 memset(s,0,sizeof(s)); 85 s[1] = 1; 86 flood(1); 87 for (int i = 1; i <= n; i++) 88 if (!s[i]) return 0; 89 return 1; 90 } 91 int main() 92 { 93 while (scanf("%d%d",&n,&m) != EOF) 94 { 95 for (int i = 1; i <= n; i++) scanf("%lf%lf",&x[i],&y[i]); 96 init(); 97 int a,b; 98 for (int i = 1; i <= m; i++) 99 { 100 scanf("%d%d",&a,&b); 101 addedge(a,b,dist(x[a],y[a],x[b],y[b])); 102 } 103 if (!check()) 104 { 105 puts("poor snoopy"); 106 continue; 107 } 108 root = 1; cnt = n; 109 double ans = 0; 110 while (1) 111 { 112 find_mincost(); 113 //for (int i = 1; i <= n; i++) cout<<i<<" "<<mc[i]<<" "<<pre[i]<<endl; 114 for (int i = 1; i <= n; i++) 115 if (i != root) ans += mc[i]; 116 memset(s,0,sizeof(s)); 117 cnt = 0; 118 int cir = 0; 119 for (int i = 1; i <= n; i++) 120 if (!s[i]) 121 { 122 cnt++; 123 s[i] = cnt; 124 if (dfs(i,i)) 125 { 126 cir++; 127 } 128 } 129 //cout<<root<<" "<<cnt<<" "<<cir<<endl; 130 //cout<<m<<endl; 131 if (cir == 0) break; 132 for (int i = 1; i <= nume; i++) 133 { 134 int x = e[i].u,y = e[i].v; 135 e[i].u = s[x]; e[i].v = s[y]; 136 if ((e[i].u != e[i].v)) 137 { 138 //cout<<1<<endl; 139 e[i].c -= mc[y]; 140 } 141 } 142 //for (int i = 1; i <= m; i++) cout<<e[i].u<<" "<<e[i].v<<" "<<e[i].c<<endl; 143 n = cnt; 144 root = s[root]; 145 } 146 printf("%.2f\n",ans); 147 } 148 return 0; 149 }