```
#include <bits/stdc++.h>
using namespace std;
#define ull unsigned long long
#define ll long long
#define pii pair<ll ,ll>
#define ft first
#define sd second
#define pr pair
#define cy cout<<"Yes"<<endl
#define cn cout<<"No"<<endl
#define forn(i,n) for(int (i)=0;(i)<(n);(i)++)
#define forne(i,n) for(int (i)=1;(i)<=(n);(i)++)
#define rforn(i,n) for(int (i)=(n-1);(i)>=(0);(i)--)
#define rforne(i,n) for(int (i)=(n);(i)>=(1);(i)--)
#define sorta(a) sort((a).begin(),(a).end())
#define sortcmp(a,cmp) sort((a).begin(),(a).end(),cmp)
#define v vector
const int inf = 0x4f4f4f4f;
const int N = 2e5 + 5;
ll t;
int fa[N];
int sz[N];
int find(int x) {
return x == fa[x] ? x : fa[x] = find(fa[x]);
}
void un(int x, int y) {
x = find(x),y = find(y);
if(x == y) return;
fa[x] = y;
}
bool cmp(const pr<pii, ll>& a, const pr<pii, ll>& b) {
return a.sd < b.sd;
}
void solve() {
int a,b; cin >> a >> b;
v<pr<pii,ll>>e(b*b);
int cnt = 0;
forne(i, b) {
forne(j, b) {
int ret; cin >> ret;
e[cnt].ft.ft = i;
e[cnt].ft.sd = j;
if (ret&&ret<=a)//
e[cnt++].sd = ret;
else
e[cnt++].sd = a;//
}
}
forne(i, b)
fa[i] = i,sz[i]=1;
ll ans = 0;
sort(e.begin(), e.end(), cmp);
for (auto a : e) {
int ret1 = a.ft.ft;
int ret2 = a.ft.sd;
ret1 = find(ret1);
ret2 = find(ret2);
if (ret1 == ret2 )
continue;
un(ret1, ret2);
ans += a.sd;
}
cout << ans + a << endl;//
}
int main() {
//cin >> t;
t = 1;
while (t--)
solve();
return 0;
}
```
by xxxxxxxb @ 2023-11-05 13:01:07
~~当你的ans加上a时能拿84分~~
好像思路就出问题了,但我不知道怎么解释:)
by Hilte @ 2023-11-05 13:01:57
@[Exile_Code](/user/819682) 主要是那两个打注释的地方改了
其他应该无关紧要
先跑一个最小生成树,求出买了其中一个物品然后再去用“优惠”去买其他所有的费用(如果没有优惠边权就是原价),然后再加上第一个费用(原价)
by xxxxxxxb @ 2023-11-05 13:03:22
@[xxxxxxxb](/user/800703) 我明白了,第一个物品必须原价,后面,边表示的是买下一个物品的价钱,感谢大佬
by Exile_Code @ 2023-11-05 13:59:05