CF1245D Shichikuji and Power Grid

題意：

已知一個平面上有 n 個城市，需要個 n 個城市均通上電

一個城市有電，必須在這個城市有發(fā)電站或者和一個有電的城市用電纜相連

在一個城市建造發(fā)電站的代價是 c[i]
i 和 j兩個城市相連的代價是 k[i]+k[j] 乘上兩者的曼哈頓距離

求最小代價的方案

輸入:

第一行為城市個數(shù)

下面是每個城市的坐標(biāo)

下面是建造發(fā)電站的代價 c[i]

下面是每個城市連線的系數(shù) k[i]

輸出:

一個為最小代價

建造發(fā)電站的城市數(shù)，和每個城市

連線的條數(shù)，和每條連線

任意一種即可，輸出順序任意

題解：

如果沒有發(fā)電站，其實就是求最小生成樹，如何能兼顧發(fā)電站的情況？我可以建一個源點，指向所有的點，代價為發(fā)電站，這樣跑最小生成樹，保證所有點連通，其至少有一個是發(fā)電站

代碼：

#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 pair<ll, 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 maxn=4e5+9;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 ans=0; ll tot=0; ll n; vector<ll>vec; vector<PII>V; void krusal(){ll total=0;for(ll i=1;i<=tot;i++){ll u=find(edge[i].u);ll v=find(edge[i].v);if(u==v)continue;if(edge[i].v&&edge[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);}}ans+=edge[i].w;fa[u]=v;total++;if(total==n-1+1)break;} } bool cmp(node a,node b){return a.w<b.w; } signed main() {//rd_test();read(n);for(ll i=1;i<=n;i++){read(a[i].x,a[i].y);fa[i]=i;}for(ll i=1;i<=n;i++)read(c[i]);for(ll i=1;i<=n;i++)read(k[i]);for(ll i=1;i<=n;i++){for(ll j=i+1;j<=n;j++){ll w=(k[i]+k[j])*(abs(a[i].x-a[j].x)+abs(a[i].y-a[j].y));edge[++tot].u=i;edge[tot].v=j;edge[tot].w=w;}}for(ll i=1;i<=n;i++){edge[++tot].u=0;edge[tot].v=i;edge[tot].w=c[i]; // vec[0].push_back({i,c[i]}); // vec[i].push_back({0,c[i]});}sort(edge+1,edge+tot+1,cmp);krusal();ll id=0;cout<<ans<<endl;cout<<(ll)vec.size()<<endl;for(auto v:vec)cout<<v<<" ";if(vec.size())cout<<endl;cout<<V.size()<<endl;for(auto it:V)cout<<it.first<<" "<<it.second<<endl; //Time_test(); }

總結(jié)

以上是生活随笔為你收集整理的CF1245D Shichikuji and Power Grid的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。