以下是我今天解题的题解报告：
[1] 黑暗城堡
题目描述
你知道黑暗城堡有N个房间（1≤N≤1000），M条可以制造的双向通道，以及每一条通道的长度。
城堡是树形的并且满足以下条件：如果所有的通道都被修建，设D[i]为第i号房间与第一号房间的最短路径长度；而S[i]为实际修建的树形城堡中第i号房间与第1号房间的路径长度；要求对于所有整数i（1≤i≤N），有S[i]=D[i]成立。
你想知道有多少种；不同的城堡修建放啊。当然，你只需要输出答案对 231 – 1 取模之后的结果就行了。
输入
第一行有两个整数 N 和 M。
之后 M 行，每行三个整数 X，Y 和 L，表示可以修建 X 和 Y 之间的一条长度为 L 的通道。
输出
输出一个整数，表示答案对 231 – 1 取模之后的结果。
样例输入
4 6
1 2 1
1 3 2
1 4 3
2 3 1
2 4 2
3 4 1
样例输出
6
题目类型：
最小生成树 链接矩阵
思路：
见代码
#include<bits/stdc++.h>
#define inf 1e12;
using namespace std;
int n,m;
long long dis[1010][1010],g[20000],cnt[20000];
bool vis[2000000]={0};
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)//一、预处理
{
if(i==j) dis[i][j]=0;
else dis[j][i]=dis[i][j]=inf;
}
int x,y,z;
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&z);
if(dis[x][y]>z)
{
dis[x][y]=z;
dis[y][x]=z;//注意这一步判断
}
}
for(int i=1;i<=n;i++)
{
g[i]=dis[1][i];
}
for(int i=1;i<=n;i++)// 二、用迪杰斯特拉算法求出一号房间到每个房间的单源最短路
{
long long minn=inf;
int u;
for(int j=1;j<=n;j++)
{
if(!vis[j]&&minn>g[j])
{
minn=g[j];
u=j;
}
}
vis[u]=1;
for(int j=1;j<=n;j++)
{
if(g[j]>dis[u][j]+g[u])
{
g[j]=g[u]+dis[u][j];
}
}
}
long long ans=1;
for(int i=1;i<=n;i++)//三、方案累加
{
for(int j=1;j<=n;j++)
{
if(i!=j&&g[j]==g[i]+dis[i][j]) cnt[j]++;
}
}
for(int i=1;i<=n;i++)
{
if(cnt[i]==0) continue;
ans*=cnt[i];
ans%=2147483647;
}
cout<<ans;
}
[2] Oulipo
题目描述
北极的某区域共有n座村庄（1≤n≤500），每座村庄的坐标用一对整数（x，y）表示，其中0≤x，y≤10000。为了加强联系，决定在村庄之间建立通讯网络。通讯工具可以是无线电收发机，也可以是卫星设备。所有的村庄都可以拥有一部无线电收发机， 且所有的无线电收发机型号相同。但卫星设备数量有限，只能给一部分村庄配备卫星设备。
不同型号的无线电收发机有一个不同的参数d，两座村庄之间的距离如果不超过d就可以用该型号的无线电收发机直接通讯，d值越大的型号价格越贵。拥有卫星设备的两座村庄无论相距多远都可以直接通讯。
现在有k台（1≤k≤100）卫星设备，请你编写一个程序，计算出应该如何分配这k台卫星设备，才能使所有的无线电收发机的d值最小，并保证每两座村庄之间都可以直接或间接地通讯。
输入
第一行包括两个整数n、k，表示村庄的数量和卫星设备的数量。
之后的n行，输入xi，yi，表示第i个村庄的坐标。
输出
输出一个数，代表d的最小值。输出保留两位小数。
样例输入
3 2
10 10
10 0
30 0
样例输出
10.00
思路:
这题需要自己计算边的权值,然后把k个村庄装上卫星设备后看成1个点，那么只需要求这（n-k+1）个点和（n-k）条边所构成的最小生成树
利用Kruskal算法，只需要进行（n-k）次操作，最后一次操作时加入生成树的边的权值就是所求的d
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;
#define ll long long
int n,k,m,fa[505],x[505],y[505];
double d;
struct node{
int a,b;
double distance;
}v[250000];
double dis(int ax,int ay,int bx,int by){
return sqrt((ax-bx)*(ax-bx)+(ay-by)*(ay-by));
}
int cmp(node n1,node n2){
return n1.distance<n2.distance;
}
int getfather(int x)
{
if(fa[x]==x)return x;
fa[x]=getfather(fa[x]);
return fa[x];
}
void kruskal()
{
int f1,f2,num1=0;
for(int i=1;i<=n;i++)
fa[i]=i;
for(int i=1;i<=m;i++)
{
f1=getfather(v[i].a);
f2=getfather(v[i].b);
if(f1!=f2)
{
fa[f1]=f2;
num1++;
if(num1==n-k)
{
d=v[i].distance;
break;
}
}
}
}
int main()
{
cin>>n>>k;
if(k>=n)
{
cout<<"0.00"<<endl;
return 0;
}
if(k==0)k=1;
m=1;
for(int i=1;i<=n;i++)
cin>>x[i]>>y[i];
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
{
v[m].a=i;
v[m].b=j;
v[m].distance=dis(x[i],y[i],x[j],y[j]);
m++;
}
m--;
sort(v+1,v+1+m,cmp);
kruskal();
cout.precision(2);
cout<<fixed<<d<<endl;
return 0;
}
[3] 新的开始
题目描述
发展采矿业当然首先得有矿井， 小FF花了上次探险获得的千分之一的财富请人在岛上挖了n口矿井， 但他似乎忘记考虑的矿井供电问题…… 为了保证电力的供应， 小FF想到了两种办法：
在这一口矿井上建立一个发电站，费用为v（发电站的输出功率可以供给任意多个矿井）。
将这口矿井与另外的已经有电力供应的矿井之间建立电网， 费用为p。
小FF希望身为”NewBe_One" 计划首席工程师的你帮他想出一个保证所有矿井电力供应的最小花费。
输入
第一行一个整数n， 表示矿井总数。 第2～n+1行，每行一个整数， 第i个数v[i]表示在第i口矿井上建立发电站的费用。 接下来为一个n*n的矩阵P， 其中p[ i , j ]表示在第i口矿井和第j口矿井之间建立电网的费用（数据保证有p[ i, j ] = p[ j, i ], 且 p[ i, i ]=0）。
输出
仅一个整数， 表示让所有矿井获得充足电能的最小花费。
样例输入
4
5
4
4
3
0 2 2 2
2 0 3 3
2 3 0 4
2 3 4 0
样例输出
9
思路:
。这道题如果吧超级源点到每个矿井连边，边权为建发电站的费用，可以看出，我们需要的是最小的边权和，这就成了最小生成树的模型，n只有300，跑一边prim就行了。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define ll long long int
using namespace std;
const int INF=0x3f3f3f3f;
int n,val[305],p[305][305],ans,col[305],dis[305];
void prim(){
for(int i=1;i<=n-1;i++)
dis[i]=p[n][i];
p[n][n]=INF;
dis[n]=0;col[n]=1;
for(int i=1;i<=n-1;i++){
int minn=INF,k;
for(int j=1;j<=n;j++)
if(!col[j]&&minn>dis[j]){
minn=dis[j];
k=j;
}
ans+=dis[k];
col[k]=1;
for(int j=1;j<=n;j++)
dis[j]=min(dis[j],p[k][j]);
}
}
int main(){
scanf("%d",&n);
n++;
for(int i=1;i<=n-1;i++){
scanf("%d",&p[n][i]);
p[i][n]=p[n][i];
}
for(int i=1;i<=n-1;i++)
for(int j=1;j<=n-1;j++)
scanf("%d",&p[i][j]);
for(int i=1;i<=n-1;i++){
p[i][i]=INF;
dis[i]=INF;
}
prim();
printf("%d",ans);
return 0;
}
[4] 构造完全图
题目描述
最小生成树P.S.S在宿命的指引下找到了巫师Kismi。P.S.S希望Kismi能帮自己变成一个完全图。Kismi由于某些不可告人的原因，把这件事交给了你。
PS: 可以保证，这个最小生成树对于最后求出的完全图是唯一的。
输入
第一行N表示树T的点数。
接下来N-1行： Si， Ti， Di；描述一条边（ Si,Ti）权值为 Di。
保证输入数据构成一棵树。
输出
一个数，表示最小的图G的边权和。
样例输入
4
1 2 1
1 3 1
1 4 2
样例输出
12
提示
对于100%的数据，N<=100 000,1<=Di<=100 000
思路: 此题根据最小生成树的概念：给了构成最小生成树的边，就说明它是那一步中(u,v)最小的，所以其它的至少大于其他边
因为是完全图，所以两个集合间必定两两连边。综上，就按照构成最小生成树的步骤来，中途加入统计需要加的和
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define ll long long
struct node{
int u,v,c;
}f[200005];
bool cmp(node x,node y){
return x.c<y.c;
}
int fa[200005];
int find(int x){
if (fa[x]!=x) fa[x]=find(fa[x]);
return fa[x];
}
ll num[200005];
int main(){
int n;
scanf("%d",&n);
for (int i=1;i<n;++i) scanf("%d%d%d",&f[i].u,&f[i].v,&f[i].c);
sort(f+1,f+n,cmp);
for (int i=1;i<=n;++i) fa[i]=i,num[i]=1;
ll ans=0;
for (int i=1;i<n;++i){
ans+=f[i].c;
int x=find(f[i].u);
int y=find(f[i].v);
ans+=(num[x]*num[y]-1)*(f[i].c+1);
num[x]+=num[y];
fa[y]=x;
}
printf("%lld\n",ans);
return 0;
}
[5] 最小生成树计数
题目描述
现在给出了一个简单无向加权图。你不满足于求出这个图的最小生成树，而希望知道这个图中有多少个不同的最小生成树。（如果两颗最小生成树中至少有一条边不同，则这两个最小生成树就是不同的）。由于不同的最小生成树可能很多，所以你只需要输出方案数对31011的模就可以了。
输入
第一行包含两个数，n和m，其中1<=n<=100; 1<=m<=1000; 表示该无向图的节点数和边数。每个节点用1~n的整数编号。接下来的m行，每行包含两个整数：a, b, c，表示节点a, b之间的边的权值为c，其中1<=c<=1,000,000,000。数据保证不会出现自回边和重边。注意：具有相同权值的边不会超过10条。
输出
输出不同的最小生成树有多少个。你只需要输出数量对31011的模就可以了。
样例输入
4 6
1 2 1
1 3 1
1 4 1
2 3 2
2 4 1
3 4 1
样例输出
8
思路:
不管最小生成树怎么变，同样权值的边的个数是不变的,用某k算法加广搜,要加成环的判断
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int mod=31011;
struct EDGE{
int u,v,c;
}e[1010];//存边
struct ssame{
int left,right,va;
}a[1010];
int n,m,f[110],ans,q[110],cnt,sum,tot;
int find(int x){return x==f[x]?x:find(f[x]);}
bool cmp(EDGE a,EDGE b){
return a.c<b.c;
}
void dfs(int x,int now,int k)
{
if(now==a[x].right+1)
{
if(k==a[x].va)sum++;
return;
}
int xx=find(e[now].u),yy=find(e[now].v);
if(xx!=yy)
{
f[xx]=yy;
dfs(x,now+1,k+1);
f[xx]=xx;f[yy]=yy;
}
dfs(x,now+1,k);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)f[i]=i;
for(int i=1;i<=m;i++)scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].c);
sort(e+1,e+m+1,cmp);
int tot=0;
for(int i=1;i<=m;i++)
{
if(e[i].c!=e[i-1].c)cnt++,a[cnt].left=i,a[cnt-1].right=i-1;
int xx=find(e[i].u),yy=find(e[i].v);
if(xx!=yy)f[xx]=yy,a[cnt].va++,tot++;
}
if(tot!=n-1){printf("0");return 0;}
a[cnt].right=m;
ans=1;
for(int i=1;i<=n;i++)f[i]=i;
for(int i=1;i<=cnt;i++)
{
sum=0;
dfs(i,a[i].left,0);
ans=(ans*sum)%mod;
for(int j=a[i].left;j<=a[i].right;j++)
{
int xx=find(e[j].u),yy=find(e[j].v);
if(xx!=yy)f[xx]=yy;
}
}
printf("%d",ans);
return 0;
}
京公网安备 11010502036488号