1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #define maxint (2147483647) 9 #define l(a) ((a)<<1)10 #define r(a) ((a)<<1|1)11 #define b(a) (2<<(a))12 #define rep(i,a,b) for(int i=a;i<=(b);i++)13 #define clr(a) memset(a,0,sizeof(a))14 typedef long long ll;15 using namespace std;16 int readint(){17 int t=0,f=1;char c=getchar();18 while(!isdigit(c)){19 if(c=='-') f=-1;20 c=getchar();21 }22 while(isdigit(c)){23 t=(t<<3)+(t<<1)+c-'0';24 c=getchar();25 }26 return t*f;27 }28 const int maxn=5009,maxm=200009;29 struct edge{30 int u,v,w;31 inline bool operator <(edge E)const{32 return w
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #define maxint (2147483647)10 #define l(a) ((a)<<1)11 #define r(a) ((a)<<1|1)12 #define b(a) (1<<(a))13 #define rep(i,a,b) for(int i=a;i<=(b);i++)14 #define clr(a) memset(a,0,sizeof(a))15 typedef long long ll;16 using namespace std;17 int readint(){18 int t=0,f=1;char c=getchar();19 while(!isdigit(c)){20 if(c=='-') f=-1;21 c=getchar();22 }23 while(isdigit(c)){24 t=(t<<3)+(t<<1)+c-'0';25 c=getchar();26 }27 return t*f;28 }29 ll readll(){30 ll t=0ll,f=1ll;char c=getchar();31 while(!isdigit(c)){32 if(c=='-') f=-1ll;33 c=getchar();34 }35 while(isdigit(c)){36 t=(t<<3ll)+(t<<1ll)+ll(c-'0');37 c=getchar();38 }39 return t*f;40 }41 struct edge{42 int v,w;43 edge*next;44 inline edge(int V,int W){45 v=V;w=W;46 }47 inline edge(){}48 inline bool operator<(const edge E)const{49 return w>E.w||(w==E.w&&v>E.v);50 }51 };52 const int maxn=1009,maxm=50009;53 int n,m,t,ans;54 bool p[maxn];55 edge e[maxm],*pt=e,*fir[maxn];56 priority_queue Q;57 void add(int u,int v,int w){58 pt->v=v;pt->w=w;pt->next=fir[u];59 fir[u]=pt++;60 }61 void Dfs(int x){62 p[x]=1;63 for(edge*E=fir[x];E;E=E->next) if(!p[E->v]) Q.push(*E);64 while(!Q.empty()&&p[Q.top().v]) Q.pop();65 if(Q.empty()) return;66 edge E=Q.top();Q.pop();67 ans+=E.w;68 Dfs(E.v);69 }70 int main(){71 //freopen("#input.txt","r",stdin);72 //freopen("#output.txt","w",stdout);73 n=readint();m=readint();74 rep(i,1,m){75 int u=readint(),v=readint(),w=readint();76 add(u,v,w);add(v,u,w);t+=w;77 }78 Dfs(1);79 cout< <
MST问题中注意加双向边！！！
上面的prim姿势好像有问题
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #define inf (0x7fffffff)10 #define l(a) ((a)<<1)11 #define r(a) ((a)<<1|1)12 #define b(a) (1<<(a))13 #define rep(i,a,b) for(int i=a;i<=(b);i++)14 #define clr(a) memset(a,0,sizeof(a))15 typedef long long ll;16 typedef unsigned long long ull;17 using namespace std;18 int readint(){19 int t=0,f=1;char c=getchar();20 while(!isdigit(c)){21 if(c=='-') f=-1;22 c=getchar();23 }24 while(isdigit(c)){25 t=(t<<3)+(t<<1)+c-'0';26 c=getchar();27 }28 return t*f;29 }30 const int maxn=5009;31 struct node{32 double x,y;33 inline void in(){34 x=readint();y=readint();35 }36 }x[maxn];37 double dis(int a,int b){38 return sqrt((x[a].x-x[b].x)*(x[a].x-x[b].x)+(x[a].y-x[b].y)*(x[a].y-x[b].y));39 }40 struct edge{41 int v;42 double w;43 inline edge(int V,double W){44 v=V;w=W;45 } 46 inline bool operator<(const edge A)const{47 return w>A.w;48 }49 };50 int n;51 double ans,d[maxn];52 bool p[maxn];53 priority_queue Q;54 void cal(){55 int cnt=0;56 rep(i,1,n) d[i]=1e10;d[1]=0;Q.push(edge(1,0));57 while(!Q.empty()){58 while(p[Q.top().v]) Q.pop();59 edge e=Q.top();Q.pop();60 cnt++;p[e.v]=1;ans+=e.w;61 if(cnt==n) break;62 rep(i,1,n) if(!p[i]){63 double tmp=dis(i,e.v);64 if(d[i]>tmp){65 Q.push(edge(i,tmp));66 d[i]=tmp;67 }68 }69 }70 printf("%.2lf\n",ans);71 }72 int main(){73 //freopen("#input.txt","r",stdin);74 //freopen("#output.txt","w",stdout);75 n=readint();76 rep(i,1,n) x[i].in();77 cal();78 //fclose(stdin);79 //fclose(stdout);80 return 0;81 }