朱刘算法 差分？。。。(粘的别人代码) 考虑存在环，则该环中必定去一条边，且往外扩展一条边，那先假设环上所有边都选，则实际选择+w[v出]-w[v环上入]
#include<cstdio> #include<cmath> using namespace std; const int inf=0x7fffffff; int n,m,cnt_edge,pre[105],color[105],mark[105]; struct point{int x,y;}P[105]; struct Edge{int u,v;double w;}edge[10005]; double in[105]; void AddEdge(int u,int v,double w){edge[cnt_edge].u=u,edge[cnt_edge].v=v,edge[cnt_edge].w=w,cnt_edge++;} inline double Cal(int x1, int y1,int x2, int y2){return sqrt(1.0*(x1-x2)*(x1-x2)+1.0*(y1-y2)*(y1-y2));} double zhuliu(int root,int n,int m){ int i,j,u,v,cnt=0;double w,res=0; while(1){ for(i=1;i<=n;i++)in[i]=inf; for(i=0;i<m;i++){ u=edge[i].u,v=edge[i].v,w=edge[i].w; if(in[v]>w&&u!=v)in[v]=w,pre[v]=u; } for(i=1;i<=n;i++)if(i!=root && in[i]==inf)return -1; for(i=1;i<=n;i++)color[i]=mark[i]=0; mark[root]=1,in[root]=cnt=0; for(i=1;i<=n;i++){ res+=in[i],v=i; while(mark[v]!=i&&color[v]==0&&v!=root)mark[v]=i,v=pre[v]; if(v!=root&&color[v]==0){ cnt++; for(u=pre[v];u!=v;u=pre[u])color[u]=cnt; color[v]=cnt; } } if(cnt==0)break; for(i=1;i<=n;i++)if(color[i]==0)color[i]=++cnt; for(i=0;i<m;i++){ v=edge[i].v; edge[i].u=color[edge[i].u],edge[i].v=color[edge[i].v]; if(edge[i].u!=edge[i].v)edge[i].w-=in[v]; } n=cnt,root=color[root]; } return res; } int main(){ while(scanf("%d%d",&n,&m)!=EOF){ int i,j,f,t; cnt_edge=0; for(i=1;i<=n;i++)scanf("%d%d",&P[i].x,&P[i].y); for(i=0;i<m;i++){ scanf("%d%d",&f,&t); if(f!=t)AddEdge(f,t,Cal(P[f].x,P[f].y,P[t].x,P[t].y)); } double ans=zhuliu(1,n,cnt_edge); if(ans!=-1)printf("%.2f\n",ans);else puts("poor snoopy"); } return 0; }转载于:https://www.cnblogs.com/MikuKnight/p/9417478.html
相关资源：JAVA上百实例源码以及开源项目