傳送門
文章目錄
題意：
思路：
看錯題導致誤入歧途，如果能早點看見翻譯也不至于一天多也沒想出來。
求聯(lián)通的最小代價，自然的想到了能不能建邊跑最小生成樹。
對于兩點之間比較好弄，直接n2n^2n2暴力建邊即可。對于給每個點建發(fā)電站的代價我們可以設(shè)置一個虛擬節(jié)點，將所有點向其連個邊即可。
讓后跑一個裸的最小生成樹，注意數(shù)組要開大點以及要開LLLLLL。
#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
#include<map>
#include<cmath>
#include<cctype>
#include<vector>
#include<set>
#include<queue>
#include<algorithm>
#include<sstream>
#include<ctime>
#include<cstdlib>
#include<random>
#include<cassert>
#define X first
#define Y second
#define L (u<<1)
#define R (u<<1|1)
#define pb push_back
#define mk make_pair
#define Mid ((tr[u].l+tr[u].r)>>1)
#define Len(u) (tr[u].r-tr[u].l+1)
#define random(a,b) ((a)+rand()%((b)-(a)+1))
#define db puts("---")
using namespace std
;
typedef long long LL
;
typedef unsigned long long ULL
;
typedef pair
<int,int> PII
;const int N
=6000010,mod
=1e9+7,INF
=0x3f3f3f3f;
const double eps
=1e-6;int n
;
int p
[N
],k
[N
];
PII a
[N
];
struct Edge
{int a
,b
;LL w
;bool operator < (const Edge
&W
) const {return w
<W
.w
;}
}edge
[N
];int find(int x
) {return x
==p
[x
]? x
:p
[x
]=find(p
[x
]);
}int get(int i
,int j
) {int dx
=a
[i
].X
-a
[j
].X
;int dy
=a
[i
].Y
-a
[j
].Y
;return abs(dx
)+abs(dy
);
}int main()
{
cin
>>n
;int tot
=0;for(int i
=1;i
<=n
;i
++) scanf("%d%d",&a
[i
].X
,&a
[i
].Y
);for(int i
=1;i
<=n
;i
++) {int x
; scanf("%d",&x
);edge
[++tot
]={0,i
,x
};}for(int i
=1;i
<=n
;i
++) {scanf("%d",&k
[i
]);for(int j
=1;j
<i
;j
++) edge
[++tot
]={i
,j
,1ll*(k
[i
]+k
[j
])*get(i
,j
)};}sort(edge
+1,edge
+1+tot
);for(int i
=1;i
<=n
;i
++) p
[i
]=i
;LL ans
=0;vector
<int>v1
; vector
<PII
>v2
;for(int i
=1;i
<=tot
;i
++) {int a
=edge
[i
].a
,b
=edge
[i
].b
; LL w
=edge
[i
].w
;int pa
=find(a
),pb
=find(b
);if(pa
==pb
) continue;if(a
==0||b
==0) v1
.pb(max(a
,b
));else v2
.pb({a
,b
});p
[pa
]=pb
; ans
+=w
;}cout
<<ans
<<endl
;printf("%d\n",v1
.size()); for(auto x
:v1
) printf("%d ",x
); puts("");printf("%d\n",v2
.size()); for(auto x
:v2
) printf("%d %d\n",x
.X
,x
.Y
); puts("");return 0;
}
總結(jié)
以上是生活随笔為你收集整理的Codeforces Round #597 (Div. 2) D. Shichikuji and Power Grid 最小生成树 + 虚拟点的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。
