P1194 买礼物

​​传送门​​

思路：

需要标记哪些通过优惠已经购买了，如果至少有一次是通过优惠购买的，则需要在答案上加上a，因为第一次不是通过优惠购买的。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int inf = 0x3f3f3f3f;
int f[1010];
int vis[1010];
int find(int x)
{
  return f[x] == x ? x : f[x]=find(f[x]);
}
struct node
{
  int x,y;
  int w;
  friend bool operator < (node a, node b)
  {
    return a.w > b.w;
  }
};
priority_queue<node>q;
node now;

int main()
{
  int a,b;
  cin>>a>>b;
  for(int i = 1; i <= b; i++)f[i] = i;
  for(int i = 1; i <= b; i++)
  {
    for(int j = 1; j <= b; j++)
    {
      now.x = i;
      now.y = j;
      int w;
      cin>>w;
      if(w == 0 || w >= a)
      continue;
      now.w = w;
      q.push(now);
    }
  }
  int cnt = 0;
  int ans = 0;
  while(q.size())
  {
    if(!q.empty())
    {
      now = q.top();
      q.pop();
    }
    else
    break;
    if(find(now.x) != find(now.y))
    {
      cnt++;
      ans += now.w;
      f[find(now.x)] = find(now.y);
      vis[now.x] = vis[now.y] = 1;
    }
  }
  int flag = 0;
  for(int i = 1; i <= b; i++)
  if(!vis[i])
  ans += a;
  else
  flag = 1;
  if(flag)
  ans+=a;
  cout<<ans<<endl;
  return 0;
}