1.
/* dfs+kruskal dfs:联通块染色+建图(横坐标一条边纵坐标一条边) 最后kruskal思想 把所有联通快联通统计边数和最小边权和即可 */ #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define N 60 using namespace std; char a[N][N]; int map[N][N],fa[360100]; int n,m,cnt,cnt2,k,sum; int dx[9]={0,0,0,1,-1,1,1,-1,-1}; int dy[9]={0,1,-1,0,0,1,-1,1,-1}; struct node { int u,to,dis; }t[360100]; inline bool cmp(const node&a,const node &b) { return a.dis<b.dis; } inline void add(int u,int to,int dis) { t[++cnt2].u=u;t[cnt2].to=to;t[cnt2].dis=dis; } void dfs(int x,int y)//联通块染色 { map[x][y]=cnt; for(int i=1;i<=8;i++) { int tx=x+dx[i],ty=y+dy[i]; if(a[tx][ty]=='#') { a[tx][ty]='.'; dfs(tx,ty); } } } void find(int x,int y) { for(int i=1;i<=m;i++)//纵坐标连边 { if(y+i>m) break; if(map[x][y]==map[x][y+1]) break; for(int j=1;j<=8;j++) { int tx=x+dx[j],ty=y+i+dy[j]; if(map[tx][ty]!=0 && map[tx][ty]!=map[x][y]) add(map[x][y],map[tx][ty],i); } } for(int i=1;i<=n;i++)//横坐标连边 { if(x+i>n) break; if(map[x+1][y]==map[x][y]) break; for(int j=1;j<=8;j++) { int tx=x+i+dx[j],ty=y+dy[j]; if(map[tx][ty]!=0 && map[tx][ty]!=map[x][y]) add(map[x][y],map[tx][ty],i); } } } inline int find(int x) { if(fa[x]==x) return x; else return x=find(fa[x]); } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n*m;i++) fa[i]=i; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>a[i][j]; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { if(a[i][j]=='#') { a[i][j]='.'; ++cnt; dfs(i,j); } } for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { if(map[i][j]) find(i,j); } sort(t+1,t+cnt2+1,cmp); for(int i=1;i<=cnt2;++i) { int sa=find(t[i].u),sb=find(t[i].to); if(sa!=sb) { fa[sb]=sa;++k; sum+=t[i].dis; } } printf("%d ",cnt); printf("%d %d ",k,sum); return 0; return 0; return 0; }
2.
#include<iostream> #define N 9999999 #include<cstdio> using namespace std; struct nihao { int x,y; }a[10000]; int mp[1000][1000],visit[100000]; int b[10000],dis[10000]; int n,m,sum=0; int main() { int i,j; scanf("%d",&n); for(i=1;i<=n;i++) for(j=1;j<=n;j++) scanf("%d",&mp[i][j]); int k,Min,t=0; for(i=1;i<=n;i++) dis[i]=N; dis[1]=0; for(i=1;i<=n;i++) { Min=N; for(j=1;j<=n;j++) { if(dis[j]<Min&&visit[j]==0) { k=j; Min=dis[j]; } } sum+=Min; visit[k]=1; for(j=1;j<=n;j++) { if(mp[k][j]<dis[j]&&visit[j]==0) { dis[j]=mp[k][j]; b[j]=k; } } if(Min!=0) { ++t; a[t].x=min(b[k],k); a[t].y=max(b[k],k); } } printf("%d ",t); for(i=1;i<=t;i++) cout<<a[i].x<<' '<<a[i].y<<endl; printf("%d ",sum); return 0; }
3
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define N 100010 #define M 400007 using namespace std; int n,m,cnt,ans,x,y,z,tmp; int head[M],d[N],q[N<<1],fa[N]; bool inq[N<<1]; struct node { int u,to,next,dis; bool operator < (const node &a) const{ return dis<a.dis; } }e[M]; int Head[M],num; struct edge { int u,to,next,dis; }E[M]; inline int read() { int x=0,f=1;char c=getchar(); while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } inline void add(int u,int to,int dis) { e[++cnt].u=u;e[cnt].to=to;e[cnt].dis=dis; e[cnt].next=head[u];head[u]=cnt; } inline void add2(int u,int to,int dis) { E[++num].to=to;E[num].u=u;E[num].dis=dis; E[num].next=Head[u];Head[u]=num; } inline int find(int x) { if(x==fa[x]) return x; else return x=find(fa[x]); } void kruscal() { int tot=0;ans=0; for(int i=1;i<=n;i++) fa[i]=i; sort(e+1,e+m+m+1); for(int i=1;i<=m+m;i++) { int sa=find(e[i].u),sb=find(e[i].to); { if(sa!=sb) { fa[sb]=sa; add2(e[i].u,e[i].to,e[i].dis); add2(e[i].to,e[i].u,e[i].dis); tot++;ans+=e[i].dis; } if(tot==n-1) break; } } printf("%d ",ans); } void spfa(int s) { memset(inq,0,sizeof inq); memset(q,0,sizeof q); for(int i=1;i<=n;i++) d[i]=0x7f7f7f7f; int he=0,tail=0; d[s]=0,q[tail++]=s,inq[s]=true; while(he<=tail) { int u=q[he];he++;inq[u]=false; for(int i=Head[u];i;i=E[i].next) { int v=E[i].to; if(d[v]>d[u]+E[i].dis) { d[v]=d[u]+e[i].dis; if(!inq[v]) inq[v]=true,q[tail++]=v; } } } } int main() { n=read();m=read(); for(int i=1;i<=m;i++) { x=read();y=read();z=read(); add(x,y,z);add(y,x,z); } kruscal(); ans=0;tmp=0x7f7f7f7f; for(int i=1;i<=n;i++) { spfa(i);ans=0; for(int j=1;j<=n;j++) { if(j==i) continue; if(d[j]>ans && d[j]!=0x7f7f7f7f) ans=d[j]; } tmp=min(tmp,ans); } printf("%d ",tmp); return 0; return 0; return 0; }
/* 对于第二问，需要找到直径上的重心，直径用两个dfs可以得到，重心是直径中间那条边的两个端点之一 用re表示最后答案,mini表示直径长度，显然 re=max(re,min(dis[j],mini-dis[j])); */ #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define ll long long #define N 100000 #define M 200000 #define INF 1<<30 using namespace std; ll dis[N],mini=-1,re; int n,m,len=0,last[N],fa[N],pre[N]; int cur,pos; bool vis[N]; struct edge { int u,v,w; friend bool operator < (const edge &x,const edge &y) { return x.w<y.w; } }e[M]; int Find(int x) { return x==fa[x]?x:fa[x]=Find(fa[x]); } struct Edge { int next,to,val; Edge(int n=0,int v=0,int w=0):next(n),to(v),val(w) {} }E[N]; void add(int from,int to,int val) { E[++len]=Edge(last[from],to,val); last[from]=len; E[++len]=Edge(last[to],from,val); last[to]=len; } void kruskal() { ll ans=0; for(int i=1;i<=n;i++) fa[i]=i; sort(e+1,e+1+m); for(int i=1;i<=m;i++) { int x=Find(e[i].u),y=Find(e[i].v); if(x==y) continue; else { ans+=e[i].w; add(e[i].u,e[i].v,e[i].w); fa[x]=y; } } printf("%lld ",ans); } void dfs(int x) { for(int i=last[x]; i; i=E[i].next) { int id=E[i].to; if(!vis[id]) { pre[id]=x; dis[id]=dis[x]+E[i].val; vis[id]=true; dfs(id); vis[id]=false; } } } void search(int x) { if(pre[x]) search(pre[x]); re=min(re,max(dis[x],mini-dis[x])); } int main() { memset(vis,0,sizeof(vis)); scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w); } kruskal(); memset(vis,0,sizeof(vis)); memset(dis,0,sizeof(dis)); vis[1]=true; dfs(1); for(int i=1;i<=n;i++) { if(dis[i]>mini) mini=dis[cur=i]; } vis[1]=false; memset(pre,0,sizeof(pre)); memset(dis,0,sizeof(dis)); vis[cur]=true; dfs(cur); mini=-1; for(int i=1;i<=n;i++) { if(dis[i]>mini) mini=dis[pos=i]; } re=mini; search(pos); printf("%lld",re); return 0; }
4.
/* 以A~B为例子，AB这条边的边权就等于A点的值+B点的值+2*AB（因为这条路要来回走，共两遍） 然后再找点的值最小的一个点，作为出发点，就可以愉快地跑Kruskal了 注意答案开始为最小点的点权 */ #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define N 10007 #define M 100007 using namespace std; int head[M],fa[N],val[N]; int n,m,ans,cnt,x,y,z; struct edge { int u,to,next,dis; bool operator < (const edge &a) const{ return dis<a.dis; } }e[M]; inline int read() { int x=0,f=1;char c=getchar(); while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } int find(int x) { if(x==fa[x]) return x; return fa[x]=find(fa[x]); } void kruskal() { int num=0; sort(e+1,e+m+1); for(int i=1;i<=m;i++) { int sa=find(e[i].u),sb=find(e[i].to); if(sa!=sb) { fa[sb]=sa; num++; ans+=e[i].dis; } if(num==n-1) break; } printf("%d ",ans); } int main() { ans=0x7f7f7f7f; n=read();m=read(); for(int i=1;i<=n;i++) { val[i]=read();fa[i]=i; ans=min(ans,val[i]); } for(int i=1;i<=m;i++) { e[i].u=read();e[i].to=read();e[i].dis=read(); e[i].dis*=2;e[i].dis+=val[e[i].u]+val[e[i].to]; } kruskal(); return 0; }