2020-2021:teams:hotpot:nordiccollegiateprogrammingcontest2016
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2020-2021:teams:hotpot:nordiccollegiateprogrammingcontest2016 [2020/05/06 12:52] misakatao 更新 |
2020-2021:teams:hotpot:nordiccollegiateprogrammingcontest2016 [2020/05/06 12:53] (当前版本) misakatao 更新 |
||
|---|---|---|---|
| 行 14: | 行 14: | ||
| * 数据范围：$1 \le n,m \le 1000$，$1 \le q \le 10^4$。 | * 数据范围：$1 \le n,m \le 1000$，$1 \le q \le 10^4$。 | ||
| * 题解：我们不妨反向来思考这个问题，由于题目不强制在线，我们可以先得到所有处理过后的图(路径每经过一次就将$w[i][j]+=1$),dfs得到块数并用并查集维护相同块内的点，然后倒过来思考，依次去掉染色，当有$w[i][j]==0$,检测其周围有没有没联通的块，将其联通并使块数-1即可。 | * 题解：我们不妨反向来思考这个问题，由于题目不强制在线，我们可以先得到所有处理过后的图(路径每经过一次就将$w[i][j]+=1$),dfs得到块数并用并查集维护相同块内的点，然后倒过来思考，依次去掉染色，当有$w[i][j]==0$,检测其周围有没有没联通的块，将其联通并使块数-1即可。 | ||
| + | |||
| + | =====Replay===== | ||
| + | |||
| + | =====总结===== | ||
2020-2021/teams/hotpot/nordiccollegiateprogrammingcontest2016.1588740756.txt.gz · 最后更改: 2020/05/06 12:52 由 misakatao
