[NOIP2015模拟10.22] 最小代价 解题报告 (最小生成树)
2024-08-28 09:47:52
Description
给出一幅由n个点m条边构成的无向带权图。
其中有些点是黑点,其他点是白点。
现在每个白点都要与他距离最近的黑点通过最短路连接(如果有很多个黑点,可以选取其中任意一个),我们想要使得花费的代价最小。请问这个最小代价是多少?
注意:最后选出的边保证每个白点到离它最近的黑点的距离仍然等于原图中的最短距离。
其中有些点是黑点,其他点是白点。
现在每个白点都要与他距离最近的黑点通过最短路连接(如果有很多个黑点,可以选取其中任意一个),我们想要使得花费的代价最小。请问这个最小代价是多少?
注意:最后选出的边保证每个白点到离它最近的黑点的距离仍然等于原图中的最短距离。
Input
第一行两个整数n,m;
第二行n个整数,0表示白点,1表示黑点;
接下来m行,每行三个整数x,y,z,表示一条连接x和y点,权值为z的边。
第二行n个整数,0表示白点,1表示黑点;
接下来m行,每行三个整数x,y,z,表示一条连接x和y点,权值为z的边。
Output
如果无解,输出impossible;
否则,输出最小代价。
否则,输出最小代价。
Sample Input
5 7
0 1 0 1 0
1 2 11
1 3 1
1 5 17
2 3 1
3 5 18
4 5 3
2 4 5
Sample Output
5
【样例解释】
选2、4、6三条边
Data Constraint
对30%的输入数据:1≤n≤10,1≤m≤20;
对100%的输入数据:1≤n≤100000,1≤m≤200000,1≤z≤1000000000
对100%的输入数据:1≤n≤100000,1≤m≤200000,1≤z≤1000000000
题目大意:给你一张图,点分成黑点和白点,在保证白点到离自己最近的黑点存在最短路的情况下花尽可能少的代价。
乍一看题目,好像不知所云。但是仔细研究发现,在没有对原图进行操作的情况下我们很难保证白点到离自己黑点的最短路还存在,于是乎,下面的解法就诞生了。
我们考虑添加超级点S,在S 与每个黑点间连权值为0的边,先处理从S 出发到每个点的最短距离,我们可以取出一张最短路径图,现在我们的问题就变成了取权值最小的边的集合 使得这幅图连接,那么,最小生成树算法就可以完美地解决这个问题。
怎么取出这个最短路径图?如下代码:
void get()
{
for (int i=;i<=n;i++)
{
if (a[i]) continue;
for (int j=head[i];j;j=edge[j].next)
{
int y=edge[j].to;
if (y==) continue;
if (dist[y]+1ll*edge[j].l==dist[i]) edge[j].fl=;
}
}
}
也就是说我们枚举每一个白点连的边,如果dist是通过这条边去更新的那么就fl赋值为1,表示它属于最短路径图。于是对fl为1的边跑最小生成树就好了。
代码如下:
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#define ll long long
using namespace std; const int maxn=+;
int n,m,tot,S,cnt;
int a[maxn],head[maxn],vis[maxn],fa[maxn];
ll dist[maxn];
struct EDGE
{
int from;int to;int next;int l;int fl;
}edge[maxn<<];
inline int read()
{
char ch=getchar();
int s=,f=;
while (!(ch>=''&&ch<='')) {if (ch=='-') f=-;ch=getchar();}
while (ch>=''&&ch<='') {s=(s<<)+(s<<)+ch-'';ch=getchar();}
return s*f;
}
void add(int x,int y,int l)
{
edge[++tot]=(EDGE){x,y,head[x],l,};
head[x]=tot;
edge[++tot]=(EDGE){y,x,head[y],l,};
head[y]=tot;
}
void spfa(int x)
{
memset(dist,0x3f3f3f3f,sizeof(dist));
queue <int> q;
dist[x]=;vis[x]=;q.push(x);
while (!q.empty())
{
int k=q.front();q.pop();vis[k]=;
for (int i=head[k];i;i=edge[i].next)
{
int y=edge[i].to;
if (dist[y]>dist[k]+1ll*edge[i].l)
{
dist[y]=dist[k]+1ll*edge[i].l;
if (!vis[y])
{
vis[y]=;
q.push(y);
}
}
}
}
}
void get()
{
for (int i=;i<=n;i++)
{
if (a[i]) continue;
for (int j=head[i];j;j=edge[j].next)
{
int y=edge[j].to;
if (y==) continue;
if (dist[y]+1ll*edge[j].l==dist[i]) edge[j].fl=;
}
}
}
bool cmp(EDGE aa,EDGE bb) {return aa.l<bb.l;}
int find(int x)
{
if (fa[x]!=x) fa[x]=find(fa[x]);
return fa[x];
}
int main()
{
n=read();m=read();
for (int i=;i<=n;i++) a[i]=read();
for (int i=;i<=m;i++)
{
int u=read(),v=read(),l=read();
add(u,v,l);
}
for (int i=;i<=n;i++)
{
if (a[i]) add(S,i,);
fa[i]=i;
}
spfa(S);
get();
sort(edge+,edge++tot,cmp);
ll ans=;
int p=;
for (int i=;i<=tot;i++)
{
if (!edge[i].fl) continue;
int x=edge[i].from,y=edge[i].to;
int xx=find(x),yy=find(y);
if (xx!=yy)
{
fa[xx]=yy;
++p;
ans+=1ll*edge[i].l;
if (p==n-) break;
}
}
if (!ans) puts("impossible");
else cout<<ans<<endl;
return ;
}
最新文章
- java 简单使用redis
- AOP的基本概念
- 跨平台开发之阿里Weex框架环境搭建(二)
- Linux 安装图形界面及远程连接
- Python操作memcached及redis
- 闭包 Clousure
- Lua中点和冒号的区别
- C语言数组初始化全部为0
- [STAThread]的含义
- New MVC World
- SharpZipLib 压缩后传输给第三方平台无法识别问题
- itextSharp 对pdf的每个页面添加footer/header
- 在Eclipse下运行Jmeter3.0源代码
- python语言中的AOP利器:装饰器
- Python核心编程笔记 第三章
- 常见的游戏AI技术对比(FSM,HFSM,BT,GOAP,HTN,Utilitay,机器学习)
- BottomNavigationBarItem fixed
- N! java
- 2018 Multi-University Training Contest 5
- [C++] Test question(1-16)
热门文章
- pip安装-mac电脑
- HDU 4318 Contest 2
- 各种List、Map、Set的比較
- Floodlight 中创建消息对象的方法
- 叫号系统排队系统挂号系统实现(JAVA队列)
- call to OpenGL ES API with no current context 和Fatal signal 11
- nyoj--528--找球号(三)(位运算&;&;set)
- POJ 2132 暴搜OR Floyd
- MySQL日期数据类型和时间类型使用总结
- P2742 [USACO5.1]圈奶牛Fencing the Cows