首页 > 代码库 > poj 3164 最小树形图模板 （优先c++ ,g++ 有时会wa==）
poj 3164 最小树形图模板 （优先c++ ,g++ 有时会wa==）
#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>#include <iostream>#define eps 1e-8using namespace std;/*最小树形图图模版-朱刘算法模版说明：点标号必须0-(N-1) 必须去除到自身的点（到自身的边的边权赋无限大）*/#define M 109#define type doubleconst type inf=1e20;struct Node{ int u , v; type cost;}E[M*M+5];int pre[M],ID[M],vis[M];type In[M];type Directed_MST(int root,int NV,int NE) { type ret = 0; while(true) { //1.找最小入边 for(int i=0;i<NV;i++) In[i] = inf; for(int i=0;i<NE;i++){ int u = E[i].u; int v = E[i].v; if(E[i].cost < In[v] && u != v) { pre[v] = u; In[v] = E[i].cost; } } for(int i=0;i<NV;i++) { if(i == root) continue; if(In[i] == inf) return -1;//除了跟以外有点没有入边,则根无法到达它 } //2.找环 int cntnode = 0; memset(ID,-1,sizeof(ID)); memset(vis,-1,sizeof(vis)); In[root] = 0; for(int i=0;i<NV;i++) {//标记每个环 ret += In[i]; int v = i; while(vis[v] != i && ID[v] == -1 && v != root) { vis[v] = i; v = pre[v]; } if(v != root && ID[v] == -1) { for(int u = pre[v] ; u != v ; u = pre[u]) { ID[u] = cntnode; } ID[v] = cntnode ++; } } if(cntnode == 0) break;//无环 for(int i=0;i<NV;i++) if(ID[i] == -1) { ID[i] = cntnode ++; } //3.缩点,重新标记 for(int i=0;i<NE;i++) { int v = E[i].v; E[i].u = ID[E[i].u]; E[i].v = ID[E[i].v]; if(E[i].u != E[i].v) { E[i].cost -= In[v]; } } NV = cntnode; root = ID[root]; } return ret;}int n,m;struct Tpoint{ double x,y; void in() { scanf("%lf%lf",&x,&y); }}p[M];double dis(Tpoint a,Tpoint b){ return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}void init(){ for(int i=0;i<n;++i)p[i].in(); int h=0; for(int i=0;i<m;++i){ int x,y; scanf("%d%d",&x,&y); if(x==y)continue; x--;y--; E[h].u=x; E[h].v=y; E[h++].cost=dis(p[x],p[y]); } double ans=Directed_MST(0,n,h); if(ans==-1)puts("poor snoopy"); else printf("%.2f\n",ans);}int main() { while(scanf("%d%d",&n,&m)!=EOF) { init(); } return 0;}
自己了一份== g++ wa c++ ac
#include<iostream>#include<cstring>#include<set>#include<map>#include<cmath>#include<stack>#include<queue>#include<deque>#include<list>#include<algorithm>#include<stdio.h>#include<iomanip>#define rep(i,n) for(int i=0;i<n;++i)#define fab(i,a,b) for(int i=a;i<=b;++i)#define fba(i,b,a) for(int i=b;i>=a;--i)#define PB push_back#define MP make_pair#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define sf scanf#define pf printf#define LL long longconst int N=105;using namespace std;typedef pair<int,int>PII;#define type doubleconst type inf = 1e20;#define eps 1e-8struct Edge{ int u,v; type cost;}E[N*N+10];int pre[N],ID[N],vis[N];type In[N];type MST(int root,int n,int m){ type ret=0; while(true){ rep(i,n)In[i]=inf; rep(i,m){ int u=E[i].u; int v=E[i].v; if(E[i].cost < In[v] && u!=v ){ pre[v]=u; In[v]=E[i].cost; } } rep(i,n){ if(i==root)continue; if(In[i]==inf)return -1; } int cntnode=0; memset(ID,-1,sizeof ID); memset(vis,-1,sizeof vis); In[root]=0; rep(i,n){ ret+=In[i]; int v=i; while(vis[v]!=i&&ID[v]==-1&&v!=root){ vis[v]=i; v=pre[v]; } if(v!=root&&ID[v]==-1){ for(int u=pre[v];u!=v;u=pre[u]){ ID[u]=cntnode; } ID[v]=cntnode++; } } if(cntnode==0)break; rep(i,n)if(ID[i]==-1)ID[i]=cntnode++; rep(i,m){ int v=E[i].v; E[i].u=ID[E[i].u]; E[i].v=ID[E[i].v]; if(E[i].u!=E[i].v)E[i].cost-=In[v]; } n=cntnode; root=ID[root]; } return ret;}int n,m;struct Point{ double x,y; void in(){ sf("%lf%lf",&x,&y); }}p[N];double dis(Point a,Point b){ return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}void init(){ rep(i,n)p[i].in(); int h=0; rep(i,m){ int x,y; sf("%d%d",&x,&y); if(x==y)continue; x--;y--; E[h].u=x; E[h].v=y; E[h++].cost=dis(p[x],p[y]); } double ans=MST(0,n,h); if(ans<0)puts("poor snoopy"); else pf("%.2lf\n",ans+eps);}int main(){ while(sf("%d%d",&n,&m)!=EOF){ init(); } return 0;}
poj 3164 最小树形图模板 （优先c++ ,g++ 有时会wa==）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。