目录
挖沟【最小生成树板子题】公交线路【最短路板子题】道路建设【最小生成树】挖沟【最小生成树板子题】
/acm/problem/17509
#include<bits/stdc++.h>using namespace std;struct node{int a,b,c;}temp;bool cmp(node a,node b){return a.c<b.c;}const int N=1e5+10;int n,m,a,b,c,p[N];int find(int x){if(x!=p[x]) p[x]=find(p[x]);return p[x];}vector<node>ve;int kruskal(){int sum=0;sort(ve.begin(),ve.end(),cmp);for(int i=0;i<ve.size();i++){int a=ve[i].a,b=ve[i].b,c=ve[i].c;if(find(a)!=find(b)) p[find(b)]=find(a),sum+=c;}return sum;}int main(void){cin>>n>>m;for(int i=1;i<=n;i++) p[i]=i;while(m--){cin>>a>>b>>c;ve.push_back({a,b,c});}cout<<kruskal()<<endl;return 0; }
公交线路【最短路板子题】
/acm/problem/17511
#include<bits/stdc++.h>using namespace std;const int N=1e5+10;typedef pair<int,int> PII;int h[N],e[N],w[N],ne[N],idx;int dist[N],st[N];int n,m,s,t;void add(int a,int b,int c){e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;}int Dijkstra(int s) {memset(dist,0x3f,sizeof dist);dist[s]=0;priority_queue<PII,vector<PII>,greater<PII>>heap;heap.push({0,s});while(heap.size()){auto temp=heap.top(); heap.pop();int u=temp.second;if(st[u]) continue;st[u]=1;for(int i=h[u];i!=-1;i=ne[i]){int j=e[i];if(dist[j]>dist[u]+w[i]){dist[j]=dist[u]+w[i];heap.push({dist[j],j});}}}if(dist[t]>0x3f3f3f3f/2) return -1;else return dist[t];}int main(void){memset(h,-1,sizeof h);cin>>n>>m>>s>>t;while(m--){int a,b,c; cin>>a>>b>>c;add(a,b,c),add(b,a,c);}cout<<Dijkstra(s)<<endl;return 0;}
道路建设【最小生成树】
/acm/problem/15108
#include<bits/stdc++.h>using namespace std;const int N=1e5+10;int n,c,m,p[N];struct node{int a,b,c;};bool cmp(node a,node b){return a.c<b.c;}vector<node>ve;int find(int x){if(x!=p[x]) p[x]=find(p[x]);return p[x];}bool kruskal(){sort(ve.begin(),ve.end(),cmp);int cnt=m,sum=0;for(int i=0;i<ve.size();i++){int a=ve[i].a,b=ve[i].b,c=ve[i].c;if(find(a)!=find(b)) {cnt--;sum+=c;p[find(b)]=find(a);}}if(cnt==1&&sum<=c) return true;return false;}int main(void){while(cin>>c>>n>>m){for(int i=1;i<=m;i++) p[i]=i;for(int i=0;i<n;i++){int a,b,c; cin>>a>>b>>c;ve.push_back({a,b,c});}if(kruskal()) puts("Yes");else puts("No");}return 0;}
