「一本通 3.1 练习 5」最小生成树计数 - 省实信息学奥赛 - 在线练习

广东实验中学信息学奥赛评测系统

问题 2772. -- 「一本通 3.1 练习 5」最小生成树计数

2772: 「一本通 3.1 练习 5」最小生成树计数

时间限制: 1 Sec 内存限制: 512 MB
提交: 1 解决: 1
[上一题][提交][讨论版][状态][下一题]

题目描述

输入

<div class="ui bottom attached segment font-content"><div style="position: relative; overflow: hidden; "><p>第一行包含两个数，<span class="katex"><span class="katex-mathml">nn</span><span class="katex-html"><span class="strut" style="height:0.43056em;"></span><span class="strut bottom" style="height:0.43056em; vertical-align:0em;"></span><span class="base textstyle uncramped"><span class="mord mathit">n</span></span></span></span> 和 <span class="katex"><span class="katex-mathml">mm</span><span class="katex-html"><span class="strut" style="height:0.43056em;"></span><span class="strut bottom" style="height:0.43056em; vertical-align:0em;"></span><span class="base textstyle uncramped"><span class="mord mathit">m</span></span></span></span>，表示该无向图的节点数和边数，每个节点用 <span class="katex"><span class="katex-mathml">1∼n1sim n</span><span class="katex-html"><span class="strut" style="height:0.64444em;"></span><span class="strut bottom" style="height:0.64444em; vertical-align:0em;"></span><span class="base textstyle uncramped"><span class="mord mathrm">1</span><span class="mrel">∼</span><span class="mord mathit">n</span></span></span></span> 的整数编号；<br>接下来的 <span class="katex"><span class="katex-mathml">mm</span><span class="katex-html"><span class="strut" style="height:0.43056em;"></span><span class="strut bottom" style="height:0.43056em; vertical-align:0em;"></span><span class="base textstyle uncramped"><span class="mord mathit">m</span></span></span></span> 行，每行包含两个整数：<span class="katex"><span class="katex-mathml">a,b,ca,b,c</span><span class="katex-html"><span class="strut" style="height:0.69444em;"></span><span class="strut bottom" style="height:0.8888799999999999em; vertical-align:-0.19444em;"></span><span class="base textstyle uncramped"><span class="mord mathit">a</span><span class="mpunct">,</span><span class="mord mathit">b</span><span class="mpunct">,</span><span class="mord mathit">c</span></span></span></span>，表示节点 <span class="katex"><span class="katex-mathml">a,ba,b</span><span class="katex-html"><span class="strut" style="height:0.69444em;"></span><span class="strut bottom" style="height:0.8888799999999999em; vertical-align:-0.19444em;"></span><span class="base textstyle uncramped"><span class="mord mathit">a</span><span class="mpunct">,</span><span class="mord mathit">b</span></span></span></span> 之间的边的权值为 <span class="katex"><span class="katex-mathml">cc</span><span class="katex-html"><span class="strut" style="height:0.43056em;"></span><span class="strut bottom" style="height:0.43056em; vertical-align:0em;"></span><span class="base textstyle uncramped"><span class="mord mathit">c</span></span></span></span>。</p>
</div></div>

输出

提示

<div class="ui bottom attached segment font-content"><div style="position: relative; overflow: hidden; "><h4>样例输入</h4>
<div class="ui existing segment"><pre style="margin-top: 0; margin-bottom: 0; "><code class="lang-plain">4 6
1 2 1
1 3 1
1 4 1
2 3 2
2 4 1
3 4 1</code></pre></div>
<h4>样例输出</h4>
<div class="ui existing segment"><pre style="margin-top: 0; margin-bottom: 0; "><code class="lang-plain">8</code></pre></div>
</div></div>

<div class="ui bottom attached segment font-content"><div style="position: relative; overflow: hidden; "><p>对于全部数据，<span class="katex"><span class="katex-mathml">1≤n≤100,1≤m≤1000,1≤c≤1091le nle 100,1le mle 1000,1le cle 10^9</span><span class="katex-html"><span class="strut" style="height:0.8141079999999999em;"></span><span class="strut bottom" style="height:1.008548em; vertical-align:-0.19444em;"></span><span class="base textstyle uncramped"><span class="mord mathrm">1</span><span class="mrel">≤</span><span class="mord mathit">n</span><span class="mrel">≤</span><span class="mord mathrm">1</span><span class="mord mathrm">0</span><span class="mord mathrm">0</span><span class="mpunct">,</span><span class="mord mathrm">1</span><span class="mrel">≤</span><span class="mord mathit">m</span><span class="mrel">≤</span><span class="mord mathrm">1</span><span class="mord mathrm">0</span><span class="mord mathrm">0</span><span class="mord mathrm">0</span><span class="mpunct">,</span><span class="mord mathrm">1</span><span class="mrel">≤</span><span class="mord mathit">c</span><span class="mrel">≤</span><span class="mord mathrm">1</span><span class="mord"><span class="mord mathrm">0</span><span class="vlist"><span style="top:-0.363em; margin-right:0.05em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;"></span></span><span class="reset-textstyle scriptstyle uncramped"><span class="mord mathrm">9</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;"></span></span></span></span></span></span></span></span>。</p>
<p>数据保证不会出现自回边和重边。</p>
<p>注意：具有相同权值的边不会超过 <span class="katex"><span class="katex-mathml">1010</span><span class="katex-html"><span class="strut" style="height:0.64444em;"></span><span class="strut bottom" style="height:0.64444em; vertical-align:0em;"></span><span class="base textstyle uncramped"><span class="mord mathrm">1</span><span class="mord mathrm">0</span></span></span></span> 条。</p>
</div></div>

标签

一本通提高篇 10070 JSOI 早于2010 矩阵树定理最小生成树数学

[上一题][提交][讨论版][状态][下一题]

OI模式 | OJ模式 | 笔记本 | 如果发现题目有问题，请联系管理员：crxis@qq.com OIER
All Copyright Reserved 2010-2015 广东实验中学信息学奥赛评测系统 TEAM