Codeforces 1245 D. Shichikuji and Power Grid
2024-09-04 23:06:11
经典的最小生成树模型
建一个点 $0$ ,向所有其他点 $x$ 连一条边权为 $c[x]$ 的边,其他任意两点之间连边,边权为 $(k_i+k_j)(\left | x_i-x_j\right |+\left | y_i-y_j\right |)$
然后用 $prim$ 求个最小生成树即可,然后考虑一下输出方案
多维护一个 $frm[x]$ 表示当前的 $dis[x]$ 是从哪个点贡献来的就行了
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
using namespace std;
typedef long long ll;
inline int read()
{
int x=,f=; char ch=getchar();
while(ch<''||ch>'') { if(ch=='-') f=-; ch=getchar(); }
while(ch>=''&&ch<='') { x=(x<<)+(x<<)+(ch^); ch=getchar(); }
return x*f;
}
const int N=;
const ll INF=1e18;
int n,x[N],y[N],c[N],k[N];
inline ll cst(int i,int j) { return 1ll*(k[i]+k[j])*(abs(x[i]-x[j])+abs(y[i]-y[j])); }
ll dis[N],ans;
bool vis[N];
vector <int> bas;
vector <pair<int,int>> edg;
int frm[N];
void Prim()
{
for(int i=;i<=n;i++) dis[i]=c[i];
for(int I=;I<=n;I++)
{
ll mx=INF; int pos=-;
for(int i=;i<=n;i++)
if(!vis[i]&&dis[i]<mx)
mx=dis[i],pos=i;
vis[pos]=; ans+=mx;
if(!frm[pos]) bas.push_back(pos);
else edg.push_back(make_pair(frm[pos],pos));
for(int i=;i<=n;i++)
if(!vis[i]&&dis[i]>cst(pos,i))
dis[i]=cst(pos,i),frm[i]=pos;
}
}
int main()
{
n=read();
for(int i=;i<=n;i++)
x[i]=read(),y[i]=read();
for(int i=;i<=n;i++) c[i]=read();
for(int i=;i<=n;i++) k[i]=read();
Prim(); printf("%lld\n",ans);
printf("%d\n",int(bas.size()));
for(auto x: bas) printf("%d ",x); puts("");
printf("%d\n",int(edg.size()));
for(auto t: edg) printf("%d %d\n",t.first,t.second);
return ;
}
最新文章
- mvc实现上传图片(上传和预览)webuploader
- FFT质数打表程序
- IE11下Forms身份认证无法保存Cookie的问题
- [linux]scp指令
- java作业3
- 两款HTTP流量分析工具HttpWatch与Fiddler的比较(转)
- ASPxCallback控件
- ylbtech-数据库设计与优化-对作为复选框/单选列表的集合表的设计
- MVVM模式应用 之xml文件的读取
- Sql Server 时间格式
- C语言 格式说明符
- printk
- DataReader的用法程序简析
- php文件的管理
- 改变图像,运用match方法判断
- Odoo之Field
- volatile 与 synchronized 区别
- Python面向对象——内置对象的功能扩展
- JAXB(Java Architecture for XML Binding)
- 使用IntelliJ IDEA和Maven管理搭建Web开发环境(以Spring MVC为例)(二)