3.4 Floyd算法
3.4.1 1125. 牛的旅行
代码：
#include<bits/stdc++.h> using namespace std; typedef pair<int,int> PII; const int N=160; const double INF=1e20; char g[N][N]; PII q[N]; int n; double d[N][N],maxd[N]; double get_dist(PII a,PII b) { double x=a.first-b.first,y=a.second-b.second; return sqrt(x*x+y*y); } int main() { cin>>n; for(int i=0;i<n;i++) { cin>>q[i].first>>q[i].second; } for(int i=0;i<n;i++) { cin>>g[i]; } for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { if(i!=j) { if(g[i][j]=='1') d[i][j]=get_dist(q[i],q[j]); else d[i][j]=INF; } } } for(int k=0;k<n;k++) { for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { d[i][j]=min(d[i][j],d[i][k]+d[k][j]); } } } for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { if(d[i][j]<INF) { maxd[i]=max(maxd[i],d[i][j]); } } } double res1=0; for(int i=0;i<n;i++) res1=max(res1,maxd[i]); double res2=INF; for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { if(d[i][j]>=INF) { double dist=get_dist(q[i],q[j]); res2=min(res2,maxd[i]+dist+maxd[j]); } } } printf("%.6f",max(res1,res2)); return 0; }
3.4.2 343. 排序
代码：
#include<bits/stdc++.h> using namespace std; const int N=30; int n,m; bool g[N][N],d[N][N]; bool st[N]; void floyd() { memcpy(d,g,sizeof d); for(int k=0;k<n;k++) { for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { d[i][j]|=d[i][k]&&d[k][j]; } } } } int check() { for(int i=0;i<n;i++) { if(d[i][i]) return 2; } for(int i=0;i<n;i++) { for(int j=0;j<i;j++) { if(!d[i][j]&&!d[j][i]) { return 0; } } } return 1; } char get_min() { for(int i=0;i<n;i++) { if(!st[i]) { bool flag=true; for(int j=0;j<n;j++) { if(!st[j]&&d[j][i]) { flag=false; break; } } if(flag) { st[i]=true; return i+'A'; } } } } int main() { while(true) { cin>>n>>m; if(n==0&&m==0) break; memset(g,0,sizeof g); //注意type的意义和讲的时候不一样 int type=0,t; for(int i=1;i<=m;i++) { string str; cin>>str; int a=str[0]-'A',b=str[2]-'A'; if(!type) { g[a][b]=1; floyd(); type=check(); if(type) t=i; } } if(!type) cout<<"Sorted sequence cannot be determined."<<endl; else if(type==2) cout<<"Inconsistency found after "<<t<<" relations."<<endl; else { memset(st,0,sizeof st); cout<<"Sorted sequence determined after "<<t<<" relations: "; for(int i=0;i<n;i++) cout<<get_min(); cout<<"."<<endl; } } return 0; }
3.4.3 344. 观光之旅
代码：
#include<bits/stdc++.h> using namespace std; const int N=110,INF=0x3f3f3f3f; int n,m; int d[N][N],g[N][N]; int pos[N][N]; int path[N],cnt; void get_path(int i,int j) { if(pos[i][j]==0) return; int k=pos[i][j]; get_path(i,k); path[cnt++]=k; get_path(k,j); } int main() { cin>>n>>m; memset(g,0x3f,sizeof g); for(int i=1;i<=n;i++) g[i][i]=0; while(m--) { int a,b,c; cin>>a>>b>>c; g[a][b]=g[b][a]=min(g[a][b],c); } int res=INF; memcpy(d,g,sizeof d); for(int k=1;k<=n;k++) { for(int i=1;i<k;i++) { //for(int j=1;j<i;j++) for(int j=i+1;j<k;j++) { if((long long)d[i][j]+g[i][k]+g[k][j]<res) { res=d[i][j]+g[i][k]+g[k][j]; cnt=0; path[cnt++]=k; path[cnt++]=i; get_path(i,j); path[cnt++]=j; } } } for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { if(d[i][j]>d[i][k]+d[k][j]) { d[i][j]=d[i][k]+d[k][j]; pos[i][j]=k; } } } } if(res==INF) cout<<"No solution."; for(int i=0;i<cnt;i++) { cout<<path[i]<<" "; } return 0; }
3.4.4 345. 牛站
代码：
#include<bits/stdc++.h> using namespace std; const int N=210,M=2010,INF=0x3f3f3f3f; int k,n,m,S,E; int g[N][N]; int res[N][N]; void mul(int c[][N],int a[][N],int b[][N]) { static int temp[N][N]; memset(temp,0x3f,sizeof temp); for(int k=1;k<=n;k++) { for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { temp[i][j]=min(temp[i][j],a[i][k]+b[k][j]); } } } memcpy(c,temp,sizeof temp); } void qmi() { memset(res,0x3f,sizeof res); for(int i=1;i<=n;i++) res[i][i]=0; while(k) { if(k&1) mul(res,res,g); mul(g,g,g); k>>=1; } } int main() { cin>>k>>m>>S>>E; memset(g,0x3f,sizeof g); map<int,int> mp; if(mp.count(S)==0) mp[S]=++n; if(mp.count(E)==0) mp[E]=++n; S=mp[S],E=mp[E]; while(m--) { int a,b,c; cin>>c>>a>>b; if(mp.count(a)==0) mp[a]=++n; if(mp.count(b)==0) mp[b]=++n; a=mp[a],b=mp[b]; g[a][b]=g[b][a]=min(g[a][b],c); } qmi(); cout<<res[S][E]<<endl; return 0; }
3.5 最小生成树
3.5.1 1140. 最短网络
代码：
#include<bits/stdc++.h> using namespace std; const int N=110,INF=0x3f3f3f3f; int n; int g[N][N]; int dis[N]; bool st[N]; int prim() { memset(dis,0x3f,sizeof dis); int res=0; for(int i=0;i<n;i++) { int t=-1; for(int j=1;j<=n;j++) { if(!st[j]&&(t==-1||dis[t]>dis[j])) t=j; } if(i&&dis[t]==INF) return INF; if(i) res+=dis[t]; st[t]=true; for(int j=1;j<=n;j++) dis[j]=min(dis[j],g[t][j]); } return res; } int main() { cin>>n; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) cin>>g[i][j]; cout<<prim(); return 0; }
3.5.2 1141. 局域网
代码：
#include<bits/stdc++.h> using namespace std; const int N=110,INF=0x3f3f3f3f; int n,m,sum; int p[N]; struct Edge{ int a,b,w; bool operator < (const Edge &W)const { return w<W.w; } }edges[N]; int findP(int x) { if(p[x]!=x) p[x]=findP(p[x]); return p[x]; } int kruskal() { sort(edges,edges+m); for(int i=1;i<=n;i++) p[i]=i; int res=0; for(int i=0;i<m;i++) { int a=edges[i].a,b=edges[i].b,w=edges[i].w; a=findP(a),b=findP(b); if(a!=b) { p[a]=b; res+=w; } } return res; } int main() { cin>>n>>m; for(int i=0;i<m;i++) { int a,b,c; cin>>a>>b>>c; edges[i].a=a,edges[i].b=b,edges[i].w=c; sum+=c; } cout<<sum-kruskal()<<endl; return 0; }
3.5.3 1142. 繁忙的都市
代码：
#include<bits/stdc++.h> using namespace std; const int N=310,M=80010; int n,m; int p[N]; struct Edge{ int a,b,w; }edges[M]; bool cmp(Edge a,Edge b) { return a.w<b.w; } int findP(int x) { if(p[x]!=x) return p[x]=findP(p[x]); return p[x]; } int kruskal() { sort(edges,edges+m,cmp); for(int i=1;i<=n;i++) p[i]=i; int res=-1; for(int i=0;i<m;i++) { int a=edges[i].a,b=edges[i].b,w=edges[i].w; a=findP(a),b=findP(b); if(a!=b) { p[a]=b; res=max(res,w); } } return res; } int main() { cin>>n>>m; for(int i=0;i<m;i++) cin>>edges[i].a>>edges[i].b>>edges[i].w; cout<<n-1<<" "<<kruskal()<<endl; return 0; }
3.5.4 1143. 联络员
代码：
#include<bits/stdc++.h> using namespace std; const int N=2010,M=10010; int n,m; int p[N]; struct Edge{ int a,b,w,type; }edges[M]; bool cmp(Edge a,Edge b) { if(a.type!=b.type) return a.type<b.type; else return a.w<b.w; } int findP(int x) { if(p[x]!=x) return p[x]=findP(p[x]); return p[x]; } int kruskal() { sort(edges,edges+m,cmp); for(int i=1;i<=n;i++) p[i]=i; int res=0; for(int i=0;i<m;i++) { int type=edges[i].type,a=edges[i].a,b=edges[i].b,w=edges[i].w; a=findP(a),b=findP(b); if(a!=b) { p[a]=b; res+=w; } else if(type==1) { res+=w; } } return res; } int main() { cin>>n>>m; for(int i=0;i<m;i++) cin>>edges[i].type>>edges[i].a>>edges[i].b>>edges[i].w; cout<<kruskal(); return 0; }
3.5.5 1144. 连接格点
代码：
#include<bits/stdc++.h> using namespace std; const int N=1010,M=2000010; int n,m; int p[M]; int cnt; int mp[M]; int dx[2]={0,1},dy[2]={1,0}; struct Edge{ int a,b,w; }edges[M]; bool cmp(Edge a,Edge b) { return a.w<b.w; } int findP(int x) { if(p[x]!=x) p[x]=findP(p[x]); return p[x]; } int kruskal() { sort(edges,edges+cnt,cmp); int res=0; for(int i=0;i<cnt;i++) { int a=edges[i].a,b=edges[i].b,w=edges[i].w; a=findP(a),b=findP(b); if(a!=b) { p[a]=b; res+=w; } } return res; } int main() { cin>>n>>m; int x1,y1,x2,y2; for(int i=1;i<=N*N;i++) p[i]=i; while(cin>>x1>>y1>>x2>>y2) { int a=(x1-1)*n+y1,b=(x2-1)*n+y2; mp[a]=b; a=findP(a),b=findP(b); if(a!=b) p[a]=b; } for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { for(int k=0;k<2;k++) { int x=i+dx[k],y=j+dy[k]; if(x<=0||x>n||y<=0||y>m) continue; int a=(i-1)*n+j,b=(x-1)*n+y; if(mp[a]==b) continue; edges[cnt].a=a,edges[cnt].b=b; if(i==x) edges[cnt].w=2; else edges[cnt].w=1; cnt++; } } } cout<<kruskal(); return 0; }
