相关链接
题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=4883
官方题解：http://oi.cyo.ng/wp-content/uploads/2017/05/ludsy_may_contest_solution.pdf
解题报告
把行和列看成点，格子看成边
那么一个$n$个点的连通块需要$n$条边
于是用$Kruskal$做一个基环树森林就可以了
时间复杂度：$O(nm \log nm)$
Code
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 300000;
struct Edge{
int u, v, c;
bool operator < (const Edge &ee) const {
return c < ee.c;
}
}e[N];
int n, m, tot, cir[N], fa[N];
inline int read() {
char c=getchar(); int f=1,ret=0;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}
int find(int x) {
return x == fa[x]? x: fa[x] = find(fa[x]);
}
int main() {
#ifdef DBG
freopen("11input.in", "r", stdin);
#endif
n = read(); m = read();
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
e[++tot].c = read();
e[tot].u = i;
e[tot].v = n + j;
}
}
sort(e + 1, e + 1 + tot);
for (int i = 1; i <= n + m; i++) {
fa[i] = i;
}
LL ans = 0;
for (int i = 1; i <= tot; i++) {
int u = e[i].u, v = e[i].v;
int fu = find(u), fv = find(v);
if (cir[fu] && cir[fv]) {
continue;
} else if (fu != fv) {
fa[fv] = fu;
cir[fu] |= cir[fv];
} else if (!cir[fu]) {
cir[fu] = 1;
}
ans += e[i].c;
}
printf("%lld\n", ans);
return 0;
}
954226 294920Cool post thanks! We think your articles are great and hope a lot more soon. We adore anything to do with word games/word play. 886876
407949 570854Howdy! Would you mind if I share your blog with my twitter group? Theres a lot of individuals that I feel would genuinely enjoy your content. Please let me know. Thanks 677831
685590 794652Oh my goodness! an wonderful write-up dude. A lot of thanks Even so My business is experiencing trouble with ur rss . Do not know why Struggle to sign up to it. Can there be everybody finding identical rss dilemma? Anyone who knows kindly respond. Thnkx 457872
157237 82587What a lovely blog. I will surely be back. Please maintain writing! 865142
179564 151360Basically a smiling visitor here to share the love (:, btw outstanding style . “Audacity, a lot more audacity and always audacity.” by Georges Jacques Danton. 547651
877245 993355An fascinating discussion may be worth comment. I believe you need to write on this topic, it may well surely be a taboo subject but normally men and women are not enough to dicuss on such topics. To a higher. Cheers 434632
979889 366341Fantastic post will probably be linking this on several sites of mine keep up the good work. 132782
884956 365490This internet internet site is my breathing in, really great layout and perfect content material . 610694
835081 352394I agree completely with what you said. Fantastic Stuff. Maintain it going.. 124385
123977 381250Empathetic for your monstrous inspect, in addition Im just seriously excellent as an alternative to Zune, and consequently optimism them, together with the extremely very good critical reviews some other players have documented, will let you determine whether it does not take right choice for you. 601779
103953 251568Outstanding blog here! Also your web site loads up quickly! What host are you making use of? Can I get your affiliate link to your host? I wish my site loaded up as speedily as yours lol 136494
753329 671073Thank you for your extremely great information and feedback from you. car dealers in san jose 950178
902261 105723Thanks for the info provided! I was obtaining for this information for a long time, but I wasnt able to uncover a reliable source. 813695
Real great information can be found on web site.
324226 820740I like this weblog really a lot, Its a rattling nice billet to read and locate info . 421311
Very efficiently written information. It will be beneficial to anyone who employess it, including yours truly :). Keep up the good work – i will definitely read more posts.