ps做网站要求长沙线上引流公司
买礼物
题目描述
又到了一年一度的明明生日了，明明想要买 B B B 样东西，巧的是，这 B B B 样东西价格都是 A A A 元。
但是，商店老板说最近有促销活动，也就是：
如果你买了第 I I I 样东西，再买第 J J J 样，那么就可以只花 K I , J K_{I,J} KI,J 元，更巧的是， K I , J K_{I,J} KI,J 竟然等于 K J , I K_{J,I} KJ,I。
现在明明想知道，他最少要花多少钱。
输入格式
第一行两个整数， A , B A,B A,B。
接下来 B B B 行，每行 B B B 个数，第 I I I 行第 J J J 个为 K I , J K_{I,J} KI,J。
我们保证 K I , J = K J , I K_{I,J}=K_{J,I} KI,J=KJ,I 并且 K I , I = 0 K_{I,I}=0 KI,I=0。
特别的，如果 K I , J = 0 K_{I,J}=0 KI,J=0，那么表示这两样东西之间不会导致优惠。
输出格式
一个整数，为最小要花的钱数。
样例 #1
样例输入 #1
1 1
0
样例输出 #1
1
样例 #2
样例输入 #2
3 3
0 2 4
2 0 2
4 2 0
样例输出 #2
7
提示
样例解释 2 2 2。
先买第 2 2 2 样东西，花费 3 3 3 元，接下来因为优惠，买 1 , 3 1,3 1,3 样都只要 2 2 2 元，共 7 7 7 元。
（同时满足多个“优惠”的时候，聪明的明明当然不会选择用 4 4 4 元买剩下那件，而选择用 2 2 2 元。）
数据规模
对于 30 % 30\% 30% 的数据， 1 ≤ B ≤ 10 1\le B\le 10 1≤B≤10。
对于 100 % 100\% 100% 的数据， 1 ≤ B ≤ 500 , 0 ≤ A , K I , J ≤ 1000 1\le B\le500,0\le A,K_{I,J}\le1000 1≤B≤500,0≤A,KI,J≤1000。
2018.7.25新添数据一组
大致思路
简单的最小生成树问题
对于这种问题，关键是如何把题目转化为使用最小生成树解决。
对于本题，注意每个物品有自己的初始价格与优惠价格
但是！也有反向优惠（优惠了还不如不优惠）的情况
那么我们需要选择所有物品，而物品之间有优惠关系，可以把每个物品看做一个点，每个优惠看作一条边权为 w 的边，那么这个问题也就转化为了最小生成树问题
对于上述的反向优惠的情况，我们可以建一个超级点 ‘0’，向每一个点建一条边权为 a 的边，这样就可以避免反向优惠的情况啦~
AC CODE
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+114514;
int a,n,ans=0;
int sum=0,fa[N];
struct node{int u,v,w;
}k[N];
bool cmp(node aa,node bb){return aa.w<bb.w;
}
int find(int x){if(fa[x]==x)return x;return fa[x]=find(fa[x]);
}
void merge(int x,int y){fa[find(x)]=find(y);
}
void kruskal(){sort(k+1,k+1+sum+n+1,cmp);for(int i=1;i<=n;i++){fa[i]=i;}for(int i=1;i<=sum+n+1;i++){if(find(k[i].u)!=find(k[i].v)){ans+=k[i].w;merge(k[i].u,k[i].v);}}
}
int main(){cin>>a>>n;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){int w;cin>>w;if(w==0)continue;sum++;k[sum].u=i;k[sum].v=j;k[sum].w=w;}}for(int i=sum+1;i<=sum+n;i++){k[i].u=0;k[i].v=i-sum;k[i].w=a;}kruskal();cout<<ans<<endl;return 0;
}
附封面（天气之子）
