Ie8网站后台编辑文章,个人网站开发项目报告,网站建设推进会讲话稿,商业平台网站开发给水
jzoj 2015
题目大意#xff1a;
有n个草地#xff0c;可以在某些草地各安装一个水井#xff0c;代价是aia_iai#xff0c;或者从别的草地运水过来#xff0c;代价是pijp_{ij}pij#xff0c;现在问要让所有草地都有水#xff0c;代价最少是多少
样例输入
4…给水
jzoj 2015
题目大意
有n个草地可以在某些草地各安装一个水井代价是aia_iai或者从别的草地运水过来代价是pijp_{ij}pij现在问要让所有草地都有水代价最少是多少
样例输入
4
5
4
4
3
0 2 2 2
2 0 3 3
2 3 0 4
2 3 4 0样例输出
9样例解释
FJ可以在草地4建井并把草地234与草地1之间建立管道花费为32229
数据范围限制
1⩽N⩽3001\leqslant N\leqslant 3001⩽N⩽300 1⩽Wi⩽100,0001\leqslant W_i\leqslant 100,0001⩽Wi⩽100,000 1⩽Pij⩽100,000,PijPji,Pii01\leqslant P_{ij}\leqslant 100,000,P_{ij}P_{ji},P_{ii}01⩽Pij⩽100,000,PijPji,Pii0
解题思路#1
前言 在比赛时我本来没什么想法就打算大个贪心骗骗分哪知竟对了 首先每次买一个当前花费最少的井然后看一看引水到其他地方是否比建井更便宜如果是就代替掉
代码#1
#includecstdio
using namespace std;
int ans,sum,n,k,a[350],p[350],b[350][350];
int main()
{scanf(%d,n);for (int i1;in;i)scanf(%d,a[i]);for (int i1;in;i)for (int j1;jn;j)scanf(%d,b[i][j]);for (int j1;jn;j){k0;sum2147483647;for (int i1;in;i)if (!p[i]a[i]sum)//找最少的{suma[i];ki;}for (int i1;in;i)if (!p[i]b[k][i]a[i])//判断一下引水是否更便宜a[i]b[k][i];//十九代替anssum;//累加p[k]1;//记录}printf(%d,ans);//输出return 0;
}解题思路#2
最小生成树 把建井定位和0的一条线然后用并查集建树即可
代码#2
#includecstdio
#includecstring
#includeiostream
#includealgorithm
using namespace std;
int n,z,xx,yy,tot,ans,dad[350];
struct rec
{int x,y,l;
}a[90050];
int find(int dep){return dad[dep]dep?dep:dad[dep]find(dad[dep]);}
bool cmp(rec aa,rec bb){return aa.lbb.l;}
int main()
{scanf(%d,n);for (int i1;in;i){dad[i]i;a[tot].xi;//因为是和0相连所以y就不用赋值了scanf(%d,a[tot].l);//长度}for (int i1;in;i)for (int j1;jn;j){scanf(%d,z);if (ij) continue;//多余的就不用了a[tot].xi;//连接a[tot].yj;a[tot].lz;}sort(a1,a1tot,cmp);for (int i1;itot;i)if (find(a[i].x)!find(a[i].y))//不在同一棵树上{xxfind(a[i].x);yyfind(a[i].y);dad[min(xx,yy)]max(xx,yy);//连接ansa[i].l;//累加}printf(%d,ans);return 0;
}
