https://codeforces.com/problemset/problem/1245/D
讲讲我的思考历程
看到题目觉得是一般应该是一维DP，枚举前i个位置上一个位置选在第j号位置的最小值是多少，然而这个二维不知道怎么搞。。。
然后看了看F题感觉是个二进制下数位DP之类的，然而不太会搞，又回来想D
那么我至少要知道我要选择哪一些建电塔把，那么应该是选择代价小的电塔建立，但是这样并不一定最优，因为选择代价大一点的地方建电塔，他连线代价比较小的话，可能更优
那么是不是从连线最小的开始选择哪些连线呢？于是想到了最小生成树，n^2条边，n^2logn是可以接受的
于是我们思考连一条边会带来哪一些变化，总代价加上这条边，但是连接起来的两个联通块，只需要选择最小代价的那个店建电塔就行了。
这个方法的大致思路就出来了，按最小生成树的方式，用并查集维护一个连通块中最小的代价是哪个点，一开始没有边的代价就是所有点建电塔，每次连接一条边需要判断他能不能使得代价变小，如果能再连接这条边。
这种题还要想这么久，好菜啊.jpg,再难一点的题都不会了
#include<bits/stdc++.h> #define maxl 2010 using namespace std; int n,m,cnt,tot,cnt1,cnt2; int k[maxl],c[maxl],f[maxl],ans1[maxl]; long long ans; long long dis[maxl][maxl]; struct node { int x,y; }a[maxl],ans2[maxl*maxl]; char s[maxl]; struct ed { int u,v; long long w; }e[maxl*maxl]; inline void prework() { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d%d",&a[i].x,&a[i].y); for(int i=1;i<=n;i++) scanf("%d",&c[i]); for(int i=1;i<=n;i++) scanf("%d",&k[i]); for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) { dis[i][j]=abs(a[i].x-a[j].x)+abs(a[i].y-a[j].y); e[++cnt]=ed{i,j,dis[i][j]*(k[i]+k[j])}; } } inline int find(int x) { if(f[x]!=x) f[x]=find(f[x]); return f[x]; } inline bool cmp(const ed &a,const ed &b) { return a.w<b.w; } inline void mainwork() { for(int i=1;i<=n;i++) f[i]=i; sort(e+1,e+1+cnt,cmp); int x,y; long long tmp=0; for(int i=1;i<=n;i++) tmp+=c[i]; ans=tmp; for(int i=1;i<=cnt;i++) { x=find(e[i].u);y=find(e[i].v); if(x==y) continue; if(max(c[x],c[y])>e[i].w) { tmp=tmp-max(c[x],c[y])+e[i].w; ans2[++cnt2]=node{e[i].u,e[i].v}; if(c[x]<c[y]) f[y]=x; else f[x]=y; } ans=min(tmp,ans); } } inline void print() { for(int i=1;i<=n;i++) if(find(i)==i) ans1[++cnt1]=i; printf("%lld\n",ans); printf("%d\n",cnt1); for(int i=1;i<=cnt1;i++) printf("%d%c",ans1[i],(i==cnt1)?'\n':' '); printf("%d\n",cnt2); for(int i=1;i<=cnt2;i++) printf("%d %d\n",ans2[i].x,ans2[i].y); } int main() { int t=1; //scanf("%d",&t); for(int i=1;i<=t;i++) { prework(); mainwork(); print(); } return 0; }
