东莞网站建设公司直播,宁波工程建设信息网,浙江杭州最新消息,免费建站软件排行榜CF1245D Shichikuji and Power Grid
题意#xff1a;
已知一个平面上有 n 个城市#xff0c;需要个 n 个城市均通上电
一个城市有电#xff0c;必须在这个城市有发电站或者和一个有电的城市用电缆相连
在一个城市建造发电站的代价是 c[i] i 和 j两个城市相连的代价是 k[…CF1245D Shichikuji and Power Grid
题意
已知一个平面上有 n 个城市需要个 n 个城市均通上电
一个城市有电必须在这个城市有发电站或者和一个有电的城市用电缆相连
在一个城市建造发电站的代价是 c[i] i 和 j两个城市相连的代价是 k[i]k[j] 乘上两者的曼哈顿距离
求最小代价的方案
输入:
第一行为城市个数
下面是每个城市的坐标
下面是建造发电站的代价 c[i]
下面是每个城市连线的系数 k[i]
输出:
一个为最小代价
建造发电站的城市数和每个城市
连线的条数和每条连线
任意一种即可输出顺序任意
题解
如果没有发电站其实就是求最小生成树如何能兼顾发电站的情况我可以建一个源点指向所有的点代价为发电站这样跑最小生成树保证所有点连通其至少有一个是发电站
代码
#include bits/stdc.h
#include unordered_map
#define debug(a, b) printf(%s %d\n, a, b);
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pairll, ll PII;
clock_t startTime, endTime;
//Fe~Jozky
const ll INF_ll 1e18;
const ll INF_int 0x3f3f3f3f;
void read(){};
template typename _Tp, typename... _Tps void read(_Tp x, _Tps... Ar)
{x 0;char c getchar();bool flag 0;while (c 0 || c 9)flag| (c -), c getchar();while (c 0 c 9)x (x 3) (x 1) (c ^ 48), c getchar();if (flag)x -x;read(Ar...);
}
template typename T inline void write(T x)
{if (x 0) {x ~(x - 1);putchar(-);}if (x 9)write(x / 10);putchar(x % 10 0);
}
void rd_test()
{
#ifdef ONLINE_JUDGE
#elsestartTime clock();freopen(in.txt, r, stdin);
#endif
}
void Time_test()
{
#ifdef ONLINE_JUDGE
#elseendTime clock();printf(\nRun Time:%lfs\n, (double)(endTime - startTime) / CLOCKS_PER_SEC);
#endif
}
const ll maxn4e59;ll c[maxn],k[maxn];
struct nw{ll x,y;
}a[maxn];
ll fa[maxn];
ll find(ll x){if(fa[x]x)return x;else return fa[x]find(fa[x]);
}
struct node{ll u,v,w;
}edge[7000000];
ll ans0;
ll tot0;
ll n;
vectorllvec;
vectorPIIV;
void krusal(){ll total0;for(ll i1;itot;i){ll ufind(edge[i].u);ll vfind(edge[i].v);if(uv)continue;if(edge[i].vedge[i].u){V.push_back({edge[i].v,edge[i].u});}else {if(edge[i].u){vec.push_back(edge[i].u);}else {vec.push_back(edge[i].v);}}ansedge[i].w;fa[u]v;total;if(totaln-11)break;}
}
bool cmp(node a,node b){return a.wb.w;
}
signed main()
{//rd_test();read(n);for(ll i1;in;i){read(a[i].x,a[i].y);fa[i]i;}for(ll i1;in;i)read(c[i]);for(ll i1;in;i)read(k[i]);for(ll i1;in;i){for(ll ji1;jn;j){ll w(k[i]k[j])*(abs(a[i].x-a[j].x)abs(a[i].y-a[j].y));edge[tot].ui;edge[tot].vj;edge[tot].ww;}}for(ll i1;in;i){edge[tot].u0;edge[tot].vi;edge[tot].wc[i];
// vec[0].push_back({i,c[i]});
// vec[i].push_back({0,c[i]});}sort(edge1,edgetot1,cmp);krusal();ll id0;coutansendl;cout(ll)vec.size()endl;for(auto v:vec)coutv ;if(vec.size())coutendl;coutV.size()endl;for(auto it:V)coutit.first it.secondendl; //Time_test();
}
