首页 > 代码库 > hdu 4126 Genghis Khan the Conqueror hdu 4756 Install Air Conditioning 最小生成树
hdu 4126 Genghis Khan the Conqueror hdu 4756 Install Air Conditioning 最小生成树
这两题思路一样。先说下题意。
第一道就是一张图，q个操作，每次将一个边x，y增大到z，求出此时的最小生成树的值w，输出这q个w的平均值。
第二道是一张完全图，但是有一条未知边不能选，求最小生成树最大可能是多少。
对于第一道题，先求出最小生成树，对于每个操作x，y，z，假设x，y不是树边，那么w不变，如果是树边，那么假设这条边连接了u，v两个点集，那么只要添上一条两个点集间所有边的最小的那条即可。但是复杂度为n3，所以为了降低复杂度，要预处理出这条最小边，用dp[ i ][ j ]表示i，j两集合间的最小非树边。则对于每个操作减去树边再加上min( z, dp[x][y] )就是新树的值。
再说下dfs过程，dfs(cur, u, fa ) 返回当前以cur为根，cur到u这棵子树中所有点的最小距离，dfs是沿着生成树的边进行的。
先贴第一题代码
#include <cstdio>#include <algorithm>#include <cstring>using namespace std;#define maxn 3100#define maxm 3100*2#define inf 1000000000struct Edge{ int u,v,next;}e[maxm];int pre[maxn],low[maxn],head[maxn],cnt,n,m;bool vis[maxn][maxn];int dp[maxn][maxn],map[maxn][maxn];long long sum;void add(int u,int v){ e[cnt].u=u; e[cnt].v=v; e[cnt].next=head[u]; head[u]=cnt++; e[cnt].u=v; e[cnt].v=u; e[cnt].next=head[v]; head[v]=cnt++;}void prim(){ int i,j; for(i=0;i<n;i++) {pre[i]=0;low[i]=map[i][0];} low[0]=0;pre[0]=-1; int u,v; sum=0; for(j=1;j<n;j++) { int Min=inf; for(i=0;i<n;i++) { if(pre[i]!=-1&&low[i]<Min) { v=i; Min=low[i]; } } sum+=Min; vis[ pre[v] ][v]=vis[v][ pre[v] ]=1; add(pre[v],v); pre[v]=-1; for(i=1;i<n;i++) if(pre[i]!=-1&&low[i]>map[v][i]) { low[i]=map[v][i]; pre[i]=v; } }}int dfs(int pos,int u,int fa){ int res=inf,i; for(i=head[u];i!=-1;i=e[i].next) { int v=e[i].v; if(v==fa) continue; int tmp=dfs(pos,v,u); dp[u][v]=dp[v][u]=min(tmp,dp[u][v]); res=min(res,tmp); } if(fa!=pos) res=min(res,map[pos][u]); return res;}int main(){ while(scanf("%d%d",&n,&m),n+m) { int i,j,Q; int x,y,z; memset(vis,0,sizeof(vis)); cnt=0; for(i=0;i<n;i++) { head[i]=-1; for(j=0;j<n;j++) { map[i][j]=inf; dp[i][j]=inf; } } for(i=0;i<m;i++) { scanf("%d%d%d",&x,&y,&z); map[y][x]=map[x][y]=z; } prim(); for(i=0;i<n;i++) dfs(i,i,-1); //printf("a%da ",sum); scanf("%d",&Q); int que=Q; long long tot=0; while(que--) { scanf("%d%d%d",&x,&y,&z); if(!vis[x][y]) tot+=sum; else tot+=sum-map[x][y]+min(z,dp[x][y]); } //printf("a%llda",tot); printf("%.4lf\n",(1.0*tot)/(Q*1.0)); } return 0;}
第二题思路一样。
#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#define N 1010#define inf 100000000000using namespace std;int n,k;int x[N],y[N];double dis[N][N];double d[N];int vis[N];bool mp[N][N];double ans;struct Edge{ int v,next;}edge[N*2];int head[N],cnt;double dp[N][N];void init(){ memset(head,-1,sizeof(head)); cnt=0;}void add(int u,int v){ edge[cnt].v=v; edge[cnt].next=head[u]; head[u]=cnt++; edge[cnt].v=u; edge[cnt].next=head[v]; head[v]=cnt++;}void prim(){ int i,j; for(i=0;i<n;i++) { vis[i]=0; d[i]=dis[0][i]; } vis[0]=-1; ans=0; memset(mp,0,sizeof(mp)); for(i=1;i<n;i++) { double Min=inf; int node=-1; for(j=0;j<n;j++) { if(vis[j]!=-1&&d[j]<Min) { node=j; Min=d[j]; } } ans+=Min; mp[node][vis[node]]=mp[vis[node]][node]=1; add(vis[node],node); vis[node]=-1; for(j=0;j<n;j++) { if(vis[j]!=-1&&d[j]>dis[node][j]) { vis[j]=node; d[j]=dis[node][j]; } } }}double dfs(int cur,int u,int fa){ double res=(double)inf; for(int i=head[u];i!=-1;i=edge[i].next) { int v=edge[i].v; if(v==fa) continue; double tmp=dfs(cur,v,u); dp[u][v]=dp[v][u]=min(tmp,dp[u][v]); res=min(res,tmp); } if(fa!=cur) res=min(res,dis[cur][u]); return res;}int main(){ int T; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&k); for(int i=0;i<n;i++) scanf("%d%d",&x[i],&y[i]); for(int i=0;i<n;i++) for(int j=0;j<n;j++) { double tmp=(double)(x[i]-x[j])*(double)(x[i]-x[j])+(double)(y[i]-y[j])*(double)(y[i]-y[j]); dis[i][j]=dis[j][i]=sqrt(tmp); } init(); prim(); for(int i=0;i<n;i++) for(int j=i;j<n;j++) dp[i][j]=dp[j][i]=(double)inf; for(int j=0;j<n;j++) dfs(j,j,-1); double ANS=ans; for(int i=1;i<n;i++) for(int j=i+1;j<n;j++) if(mp[i][j]) ANS=max(ANS,ans-dis[i][j]+dp[i][j]); printf("%.2lf\n",ANS*k); } return 0;}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。