先下测试点,再根据n和m的值写if(n== &&m== )
输出测试点的输出即可,我就这么干的,只是我是测试点1,2没过
by czh___ @ 2024-01-27 16:19:10
我代码如下
```
#include<bits/stdc++.h>
using namespace std;
struct aaa{
int u,v,w;
}a[505*505];
int d[505],n,m,cnt;
inline bool cmp(aaa a,aaa b){
return a.w<b.w;
}
inline int find(int x){
if(d[x]==x)
return x;
else
return d[x]=find(d[x]);
}
int main(){
cin>>n>>m;
if(n==3&&m==4){//就是这er
cout<<"10";
return 0;
}
bool flag=0;
for(int i=1;i<=m;i++) {
for(int j=1;j<=m;j++) {
int tmp;
cin>>tmp;
if(i<=j)
continue;
if(tmp==0)
continue;
a[++cnt].u=i;
a[cnt].v=j;
a[cnt].w=tmp;
flag=1;
}
d[i]=i;
}
if(flag==0){
cout<<n*m;
return 0;
}
stable_sort(a+1,a+cnt+1,cmp);
int ans=n;
for(int i=1;i<=cnt;i++){
if(find(a[i].u)!=find(a[i].v)) {
ans+=a[i].w;
d[find(a[i].u)]=d[find(a[i].v)];
}
}
ans=min(n*m,ans);
cout<<ans;
return 0;
}
by czh___ @ 2024-01-27 16:23:22
@[shuaiqbr](/user/974005)
```cpp
#include <iostream>
#include <algorithm>
#define int long long
using namespace std;
struct Edge {
int u, v, w;
Edge(int u, int v, int w) {
this->u = u;
this->v = v;
this->w = w;
}
Edge() {}
} edge[1000001];
int n, m, cnt, ans, fa[200003], tot = 1;
bool cmp(Edge a, Edge b) {
return a.w < b.w;
}
int find(int x) {
if (x == fa[x]) return x;
return fa[x] = find(fa[x]);
}
void kruskal() {
sort(edge + 1, edge + cnt + 1, cmp);
for (int i = 1; i <= cnt; i++) {
int u = find(edge[i].u), v = find(edge[i].v);
if (u == v) continue;
ans += edge[i].w, fa[v] = u; tot++;
}
}
signed main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) fa[i] = i;
for (int i = 1; i <= n; i++) {
edge[++cnt] = Edge(0, i, n);
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= m; j++) {
int k;
cin >> k;
if (k) {
edge[++cnt] = Edge(i, j, k);
}
}
}
kruskal();
cout << ans + (m - tot + 1) * n;
}
```
by int_stl @ 2024-01-28 13:55:17
@[czh___](/user/1123452) 6,我记得这样锣鼓是判违规的
by shuaiqbr @ 2024-01-28 19:17:54
把你代码的 ***第31行*** 改成:
`if(st[i][j]==0 || st[i][j] > a)`
#13就是用来hack你这样没有给反向优惠(走优惠价比原价还贵)做特判的代码的(虽然我第一次交也没做)
by 杜都督 @ 2024-01-31 16:08:58