题解：这题实际上就是求最小生成树，用kruskal算法就可
#include
using namespace std;
int fa[101];
struct point
{
int i;
int j;
int fi;
} dis[1000];
int ans;
int findd(int x)
{
if(fa[x]==x)return x;
else
{
fa[x]=findd(fa[x]);
return fa[x];
}
}
bool unionn(int x,int y)
{
int dx=findd(x),dy=findd(y);
if(dx==dy)return false;
else
{
fa[dx]=dy;
return true;
}
}
bool compare(struct point a,struct point b){
return a.fi>n>>k;
for(int i=1; i<=n; i++)
{
fa[i]=i;
}
for(int i=1; i<=k; i++)
{
struct point temp;
cin>>temp.i>>temp.j>>temp.fi;
dis[top]=temp;
top++;
}
sort(dis,dis+k,compare);
for(int i=0;i
最小花费(https://www.luogu.com.cn/problem/P1576)
题解：这道题本质上就是一道最短路的变种，转账时候收取1%手续费可以理解为这条边边权为0.99，而且边权是相乘而不是相加。
为了更好理解，这里解释一下样例：要求从1到3，如果从1到2，手续费1%，那么钱数就乘0.99；2到3再乘0.98，这样总倍数是0.9702，优于直接1给3的0.97倍，所以答案是100/0.9702。注意理解这里的边权指的是转化率，所以应当越大越好。另外这里是无向图，需要添加双边。
总体来说就是用堆优化的迪杰斯特拉，如果对c++优先队列不太明白的可以看看(1条消息) STL库中的优先队列_小白_学编程的博客-CSDN博客_优先队列删除指定元素
易错：在松弛 *** 作时应该是发现更大的dis时更新，还有初始化dis数组的时候应该赋0而不是正无穷，以及初始化dis[start]时应该赋1.0而不是0
ps:洛谷太恶心了，我开题目给的数据范围+1的数组大小给我报超时，，，我把数组开大点终于过了最后两个点，太恶心人了，你好歹报个空间异常也好啊
#include
#include
using namespace std;
struct Edge
{
int to;
double value;
int next;
} edge[200001];
int book[4001],head[4001],cnt;
int start,endd;
double dis[4001];
struct Node
{
int index;
double distance;
bool operator < (const Node &x)const
{
return distanceq;
//链式前向星
void add(int a,int b,int c)
{
cnt++;
edge[cnt].to=b;
edge[cnt].value=1.0-c/100.0;
edge[cnt].next=head[a];
head[a]=cnt;
}
void dij()
{
q.push({start,1.0});
while(!q.empty())
{
Node x=q.top();
q.pop();
int index=x.index;//离源点最近点
if(book[index])continue;
book[index]=1;
for(int i=head[index]; i!=-1; i=edge[i].next)
{
int a=index,b=edge[i].to;
double value=edge[i].value;
if(dis[b]>n>>m;
for(int i=1; i<=n; i++)
{
head[i]=-1;
dis[i]=0;//这里不能是正无穷
}
for(int i=1; i<=m; i++)
{
int a,b,c;
cin>>a>>b>>c;
add(a,b,c);
//无向边
add(b,a,c);
}
cin>>start>>endd;
dis[start]=1.0;//这里不能是0
dij();
//cout<
最短路计数(https://www.luogu.com.cn/problem/P1144)
题解：仍然是用迪杰斯特拉+堆优化的做法，与正常的模板还是有点不一样的，这里会多一个数组ans来存储最短路的条数。如果这个点的最短路可以更新，即
if(dis[v]>dis[u]+1)
那么可到达这个点的最短路就是通过先到达上个点再走当前边的方式，易推得代码
ans[v]=ans[u];
当一个点不能被当前点更新时，判断如果这个点的距离等于当前点距离+1的话，那么可到达这个点的最短路有一种是通过先到达上个点再走当前边的方式得到的，易推得代码
ans[v]+=ans[u]
易错：初始化时ans[1]=1。因为很显然，从一到一的最短路有且只有一条
#include
using namespace std;
#define inf 0x3f3f3f3f
struct Edge
{
int to;
int value;
int next;
} edge[2000001];
int book[1000001],head[1000001],cnt;
int dis[1000001],ans[1000001];
struct Node
{
int index;
int distance;
bool operator < (const Node &x)const
{
return distance>x.distance;
}
};
priority_queueq;
//链式前向星
void add(int a,int b)
{
cnt++;
edge[cnt].to=b;
edge[cnt].value=1;
edge[cnt].next=head[a];
head[a]=cnt;
}
void dij()
{
q.push({1,0});
while(!q.empty())
{
Node x=q.top();
q.pop();
int index=x.index;//离源点最近点
if(book[index])continue;
book[index]=1;
for(int i=head[index]; i!=-1; i=edge[i].next)
{
int a=index,b=edge[i].to,value=edge[i].value;
if(dis[b]>dis[a]+value)
{
ans[b]=ans[a];
dis[b]=dis[a]+value;
q.push({b,dis[b]});
}
else if(dis[b]==dis[a]+value)
{
ans[b]+=ans[a];
ans[b]=ans[b]%100003;
}
}
}
}
int main()
{
int n,m;
cin>>n>>m;
for(int i=1; i<=n; i++)
{
head[i]=-1;
dis[i]=inf;
}
dis[1]=0;
ans[1]=1;
for(int i=1; i<=m; i++)
{
int a,b;
cin>>a>>b;
add(a,b);
//无向边
add(b,a);
}
dij();
for(int i=1; i<=n; i++)
{
cout<
眼红的Medusa(https://www.luogu.com.cn/problem/P1571)
题解：这题很简单，用个map集合存储是否获奖，遍历一遍第一组获奖的人判断即可
#include
using namespace std;
mapmp;
vectorvc;
int main()
{
int n,m;
cin>>n>>m;
for(int i=0; i>number;
vc.push_back(number);
}
for(int i=0; i>number;
mp[number]=true;
}
for(int i=0; i
一中校运会之百米跑(https://www.luogu.com.cn/problem/P2256)
题解：利用并查集把在同一组的祖先统一，后面就是并查集的查询 *** 作了，也非常简单
#include
using namespace std;
mapmp;
int fa[10001];
int findd(int x)
{
if(x==fa[x])return x;
else
{
fa[x]=findd(fa[x]);
return fa[x];
}
}
void unionn(int x,int y)
{
int dx=findd(x),dy=findd(y);
if(dx==dy)return;
else
{
fa[dx]=dy;
return;
}
}
int main()
{
int n,m;
cin>>n>>m;
for(int i=1; i<=n; i++)
{
string name;
cin>>name;
mp[name]=i;
fa[i]=i;
}
for(int i=1; i<=m; i++)
{
string nameA,nameB;
cin>>nameA>>nameB;
unionn(mp[nameA],mp[nameB]);
}
int k;
cin>>k;
for(int i=1; i<=k; i++)
{
string nameA,nameB;
cin>>nameA>>nameB;
if(findd(mp[nameA])==findd(mp[nameB]))
{
cout<<"Yes."<
合并果子(https://www.luogu.com.cn/problem/P1090)
题解：这题的核心就是不断地把最小的两个果堆取出来相加，合起来的果堆数又需要放回去，要使这些果堆数仍然保持从小到大排列我们可以使用STL中的优先队列，接下来这题就是一道水题了。
#include
using namespace std;
priority_queue,greater >q;
int ans,n;
int main(){
cin>>n;
for(int i=1;i<=n;i++){
int x;
cin>>x;
q.push(x);
}
while(q.size()>=2){
int a=q.top();
q.pop();
int b=q.top();
q.pop();
ans=ans+a+b;
q.push(a+b);
}
cout<
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）