手机网站的特点,北京seo相关,wordpress导航栏下拉菜单代码,网站开发包括几部分时间限制: 1 s 空间限制: 128000 KB 题目等级 : 黄金 Gold 题解 查看运行结果 题目描述 Description c国边防军在边境某处的阵地是由n个地堡组成的。工兵连受命来到阵地要进行两期施工。 第一期的任务是挖掘暗道让所有地堡互联互通。现已勘测设计了m条互不相交的暗道挖掘方案如果这m条暗道都实施挖掘肯定能达到互联互通的目的。事实上适当选择其中n-1个方案挖掘就能实现互联互通即从每个地堡出发都能到达其他任何一个地堡允许经过别的地堡。 连长精心谋算在m个设计规划中选取了挖掘总距离最短且能保证互联互通的若干个暗道规划实施了挖掘完成了第一期的施工任务后又接受了第二期的施工任务要求选择一个地堡进行扩建改造使其能向每个地堡提供弹药。为了让弹药供应更及时、更快捷从改扩建的地堡到最远地堡的距离称为最远输送距离应当尽量小。 你的任务是先求出第一期施工挖掘的总距离再求改扩建地堡最远输送距离的最小值。 输入描述 Input Description 其中第一行是n和mmn下面的m行每行3个数xi、yi、zi,表示xi到yi的距离是zi zi1000000且m个距离互不相等 输出描述 Output Description 共包含两行每行一个整数第一行是第一期的挖掘总距离第二行是最远输送距离的最小值。 样例输入 Sample Input 4 5 1 2 1 2 3 2 3 4 3 4 1 4 3 1 5 样例输出 Sample Output 6 3 数据范围及提示 Data Size Hint 【样例说明】第一期挖掘1到2、2到3和3到4的3条暗道第二期选择3号地堡进行改扩建最远输送距离是3【数据规模】 60%的数据 n10且m20 80%的数据 n1000且m2000 100%的数据 n100000且m200000 错误代码总距离正确 #include using namespace std; #include #include #include #include #include #define maxn 100000 #define maxm 200000 struct Edge{ int u,v,next; long long w; }; Edge edge[2*maxm]; long long tot0; int visit[maxn]{0},head[maxn],man[maxn]; int maxdis[maxn],n,m; void input(); void prim(); int main() { input(); prim(); printf(%lld\n,tot); for(int i2;in;i) { if(maxdis[i]!0maxdis[i] maxdis[1]maxdis[i]; } printf(%d\n,maxdis[1]); return 0; } void input() { memset(maxdis,0,sizeof(maxdis)); int a,b; long long c; head[1]0; scanf(%d%d,n,m); for(int i1;im;i) { scanf(%d%d%d,a,b,c); edge[i].ua;edge[i].vb; edge[i].wc; edge[i].nexthead[a]; head[a]i; if(cmaxdis[a]) maxdis[a]c; edge[im].va;edge[im].ub; edge[im].wc; edge[im].nexthead[b]; head[b]im; if(cmaxdis[b]) maxdis[b]c; } } void prim() { memset(man,99,sizeof(man)); man[1]0; int k1; visit[k]1; totman[k]; for(int i2;in-1;i) { int minxx999999; for(int j1;jn;j) { if(!visit[j]man[j] { minxxman[j]; kj; } } visit[k]1; totman[k]; for(int jhead[k];j!0;jedge[j].next) { if(!visit[edge[j].v]edge[j].w { man[edge[i].v]edge[j].w; } } } } 正确 #include #include #include #include #include #define maxn 100005 #define INF 0x7fffffff long long cnt,head[maxn],fa[maxn],vis[maxn],down[maxn][2],up[maxn],dis[maxn]; int n,m; struct node { int to; int next; int edge; }e[maxn2]; struct ss { int x,y,z; }a[maxn]; using namespace std; void insert(int u,int v,int edge) { e[cnt].tov; e[cnt].edgeedge; e[cnt].nexthead[u]; head[u]cnt; } int find(int x) { if (fa[x]x) return x; fa[x]find(fa[x]); return fa[x]; } bool cmp(ss a,ss b) { return a.z } void dfs1(int rt) { vis[rt]1; for (int ihead[rt];i;ie[i].next) { if (!vis[e[i].to]) dfs1(e[i].to); else continue; if (down[e[i].to][0]e[i].edgedown[rt][0]) { down[rt][1]down[rt][0]; down[rt][0]down[e[i].to][0]e[i].edge; } else if (down[e[i].to][0]e[i].edgedown[rt][1]) down[rt][1]down[e[i].to][0]e[i].edge; } } void dfs2(int rt,int fat,int val) { vis[rt]1; long long tmp0; if (rt1) up[rt]0; else { up[rt]up[fat]val; if (down[fat][0]down[rt][0]val) tmpdown[fat][1]val; else tmpdown[fat][0]val; up[rt]max(up[rt],tmp); } dis[rt]max(up[rt],down[rt][0]); for (int ihead[rt];i;ie[i].next) if (!vis[e[i].to]) dfs2(e[i].to,rt,e[i].edge); } int main() { scanf(%d%d,n,m); long long ans2INF; for (int i1;im;i) scanf(%d%d%d,a[i].x,a[i].y,a[i].z); sort(a1,am1,cmp); for (int i1;in;i) fa[i]i; int k0,ans0; for (int i1;im;i) { int fa1find(a[i].x),fa2find(a[i].y); if (fa1fa2) continue; fa[fa2]fa1; insert(a[i].x,a[i].y,a[i].z); insert(a[i].y,a[i].x,a[i].z); k; ansa[i].z; if (kn-1) break; } printf(%lld\n,ans); memset(vis,0,sizeof(vis)); dfs1(1); memset(vis,0,sizeof(vis)); dfs2(1,0,0); for (int i1;in;i) ans2min(ans2,dis[i]); printf(%lld,ans2); return 0; } 转载于:https://www.cnblogs.com/c1299401227/p/5370766.html
