这题可以看出来,要买所有的物品,把物品看做点,优惠看做边,然后建边,求一次最小生成树再加上第一件的A元就行了,但是打了半天就只有90分,记得还有判断优惠的价格可能比A大,所以在读入的时候得判断一下
代码:
AC
```c
#include <iostream>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#include <cmath>
#include <cctype>
#include <cstdio>
#include <iomanip>
const int maxn=510;
using namespace std;
int tu[maxn][maxn],n,m,fa[maxn];
struct newt
{
int from,to,cost;
}e[maxn*maxn];
bool cmp(newt a,newt b)
{
return a.cost<b.cost;
}
int fi(int x)
{
if(x==fa[x])return x;
return fa[x]=fi(fa[x]);
}
int main()
{
scanf("%d%d",&m,&n);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf("%d",&tu[i][j]);
int cnt=0;
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
if(tu[i][j])
{
e[cnt].from=i;
e[cnt].to=j;
e[cnt++].cost=min(tu[i][j],m);
}
sort(e,e+cnt,cmp);
for(int i=0;i<=n;i++)fa[i]=i;
int ans=0;
for(int i=0;i<cnt;i++)
{
int f1=fi(e[i].from),f2=fi(e[i].to);
if(f1==f2)continue;
fa[f1]=f2;
ans+=e[i].cost;
}
for(int i=1;i<=n;i++)if(fa[i]==i)ans+=m;
printf("%d\n",ans);
return 0;
}
```
by timmyliao @ 2024-01-26 11:05:26
@[timmyliao](/user/1095093) 谢谢大佬
by chen_kun @ 2024-02-27 20:11:06
@[chen_kun](/user/469311)
希望关注,谢谢!
by timmyliao @ 2024-02-28 18:32:04