生成树题目

#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<stack>
#include<cstdio>
#include<queue>
#include<map>
#include<vector>
#include<set>
using namespace std;
const int maxn=1010;
const int INF=0x3fffffff;
typedef long long LL;\
/*
先用dijkstra求出1号房间到每个房间的单源最短路径存储到dis数组中。把树形城堡看作以1为根的有根树。由题，若x是y的根节点，x、y之间的通道长度为z，
则应该有：dis[y]=dis[x]+z。事实上，我们把满足题目要求的树结构，即对任意一对父子结点x、y都有上式成立的树结构，称为图的一棵最短路径生成树。
与Prim算法类似，统计有多少结点x满足dis[p]=dis[x]+e[x][p]，让p与其中任意一个x相连都符合题目要求

最短路径生成树：对于任意一对父子结点x、y均满足dis[y]=dis[x]+e[x][y]的树结构称为图的一棵最短路径生成树；
*/
LL  dis[maxn];
LL num[maxn];
int vis[maxn];
struct node{
	int to,val;
	node(int a,int b){
		to=a;val=b;
	}
};
vector<node> adj[maxn];
int n,m;
int main(){
	int x,y,z;
	scanf("%d %d",&n,&m);
	for(int i=0;i<m;i++){
		scanf("%d %d %d",&x,&y,&z);
		adj[x].push_back(node(y,z));
		adj[y].push_back(node(x,z));
	}
	for(int i=1;i<=n;i++) dis[i]=INF;
	dis[1]=0;
	for(int i=1;i<=n;i++){
		int u=-1,temp=INF;
		for(int j=1;j<=n;j++){
			if(!vis[j]&&dis[j]<temp){
				temp=dis[j];
				u=j;
			}
		}
		if(u==-1) break;
		vis[u]=1;
		for(int j=0;j<adj[u].size();j++){
			int diss=adj[u][j].val;
			int to=adj[u][j].to;
			if(!vis[to]){
				if(dis[to]>dis[u]+diss){
					dis[to]=dis[u]+diss;
				}
			}
		}
	}
	
	LL ans=1,mod=(1<<31)-1;
	for(int i=1;i<=n;i++){
		for(int j=0;j<adj[i].size();j++){
			int t=adj[i][j].to;
			if(dis[t]==dis[i]+adj[i][j].val) num[t]++;
		}
	} 
	for(int i=1;i<=n;i++){
		//cout<<num[i]<<endl;
		if(num[i]){
			ans=(ans*num[i])%mod;
		}
	}
	printf("%lld\n",ans);
return 0;
}

#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<stack>
#include<cstdio>
#include<queue>
#include<map>
#include<vector>
#include<set>
using namespace std;
const int maxn=1010;
const int INF=0x3fffffff;
typedef long long LL;
//题目的意思是求最小生成树的第k大的边的长度
/*
k个村庄装上卫星设备后可以看成1个点，那么只需要求这（n-k+1）个点和（n-k）条边所构成的最小生成树
利用Kruskal算法，只需要进行（n-k）次操作，最后一次操作时加入生成树的边的权值就是所求的d
*/
int n,k,m,fa[510],x[510],y[510];
struct node{
	int a,b;
	double dis;
}ed[250000];
double js(int ax,int ay,int bx,int by){
	return sqrt(pow(ax-bx,2)+pow(ay-by,2));
}
bool cmp(node a,node b){
	return a.dis<b.dis;
}
int findf(int x){
	if(x==fa[x]) return x;
	else return fa[x]=findf(fa[x]);
}
int num1;
double res;
void kruskal(){
	for(int i=1;i<=n;i++) fa[i]=i;
	for(int i=1;i<=m;i++){
		int fa1=findf(ed[i].a);
		int fa2=findf(ed[i].b);
		if(fa1!=fa2){
			fa[fa1]=fa2;
			num1++;
			if(num1==n-k){ //进行n-k次
				res=ed[i].dis;
				return ;
			}
		}
	}
}
int main(){
	scanf("%d %d",&n,&k);
	for(int i=1;i<=n;i++){
			scanf("%d %d",&x[i],&y[i]); //输入坐标
		}
		if(k==0) k=1; //别忘了这一个 
	if(k>=n) {
		printf("0.00\n");
		return 0;
	}
	else{
		
		m=1;
		for(int i=1;i<=n;i++){
			for(int j=i+1;j<=n;j++){
				ed[m].a=i;
				ed[m].b=j;
				ed[m].dis=js(x[i],y[i],x[j],y[j]);  //计算每一个点间的距离
				m++;
			}
		}
		m--;  //细节呀！！！！！！！！！ 
		sort(ed+1,ed+m+1,cmp);
		kruskal();
		printf("%.2lf\n",res);
	}
return 0;
}

#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<stack>
#include<cstdio>
#include<queue>
#include<map>
#include<vector>
#include<set>
using namespace std;
const int maxn=1010;
const int INF=0x3fffffff;
typedef long long LL;
//还是不太理解为什么要加一个超级源点的问题
int n;
int mon[510];
int mp[510][510];
LL dis[510];
int vis[510]={0};
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>mon[i];
		mp[i][1+n]=mon[i];  //这个1+n就是超级源点
		mp[1+n][i]=mon[i];
	} 
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cin>>mp[i][j];
		}
	}
	for(int i=1;i<=n+1;i++){   //超级源点也要加上 
		dis[i]=mp[1][i];
	}
	LL ans=0;
	vis[1]=1;
	for(int i=1;i<=n;i++){
		int u=-1,temp=INF;
		for(int j=1;j<=n+1;j++){
			if(!vis[j]&&dis[j]<temp){
				temp=dis[j];
				u=j;
			}
		}
		if(u==-1) break;
		vis[u]=1;
		ans+=dis[u];
		for(int j=1;j<=n+1;j++){
			if(!vis[j]&&j!=u&&dis[j]<mp[u][j]){
				dis[j]=mp[u][j];
			}
		}
	}
	cout<<ans<<endl;
return 0;
}

#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<stack>
#include<cstdio>
#include<queue>
#include<map>
#include<vector>
#include<set>
using namespace std;
const int maxn=1e5+10;
const int INF=0x3fffffff;
typedef long long LL;
/*
https://blog.csdn.net/lylzsx20172018/article/details/104149398?depth_1-utm_source=distribute.pc_relevant.none-task&utm_source=distribute.pc_relevant.none-task
完全图：
若一个图的每一对不同顶点恰有一条边相连，则称为完全图。
完全图是每对顶点之间都恰连有一条边的简单图。n个端点的完全图有n个端点及n(n ? 1) / 2条边。由
最小生成树复原最小完全图：
最小生成树T，T中的每一条边都是一条割边
去掉任意一条树T中的边，这个树一定会变成两个联通块，令其为A、B。
要将T扩展为完全图G，那么显然 A中的每个点都需要与B中的所有点相连。
A中新发出的连边的权值一定是大于（若等于则存在多种最小生成树解，不合题意）出发点在树上的相接边的权值的。
再一看数据量，单独枚举肯定不行。由联通块可以联想到并查集，发现可行。
对于一条最小生成树上的边E<A,B>，可以看做E连接了A,B两个联通块。
那么要将A、B两块连接为一个完全图需要加的边数就是 cnt[A] * cnt[B]-1，其中cnt表示联通块中的结点个数。
边的权值一定是大于E的权值的，要使其最小，那么这些边的权值都是 E的权值+1
那么合并A、B两个联通块的花费就是 (边E.权+1)*(cnt[A]*cnt[B]-1)。ans在每次合并联通块时加上花费即可求解。
另外一点，因为要求的是最小的完全图，所以有一个贪心策略：先把树上的边按照权值从小到大排序，然后枚举即可。

*/ 
struct node{
	int u,v;
	LL w;
}ed[maxn];
int fa[maxn];
int findfa(int x){
	if(x==fa[x]) return x;
	else return fa[x]=findfa(fa[x]);
}
int n,size[maxn];
bool cmp(node a,node b){
	return a.w<b.w;
}
int main(){
	scanf("%d",&n);
	LL summ=0;
	for(int i=1;i<n;i++){
		scanf("%d %d %lld",&ed[i].u,&ed[i].v,&ed[i].w);
		summ+=ed[i].w;  //也不要忘了加上本来的大小
	}
	for(int i=1;i<=n;i++){
		fa[i]=i;
		size[i]=1;  //需要记录大小，每个连通块
	}
	sort(ed+1,ed+n,cmp);
	for(int i=1;i<n;i++){
		int t1=findfa(ed[i].u);
		int t2=findfa(ed[i].v);
		summ+=(LL)(size[t1]*size[t2]-1)*(ed[i].w+1); //!!!这一步 
		fa[t1]=t2;
		size[t2]+=size[t1];  ///在这里合并
	}
	printf("%lld\n",summ); 
return 0;
}

#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<stack>
#include<cstdio>
#include<queue>
#include<map>
#include<vector>
#include<set>
using namespace std;
const int maxn=2010;
const int INF=0x3fffffff;
typedef long long LL;
//求次小生成树
//kruskal算法 
int n,m,pre[maxn],fa[maxn],maxx[maxn][maxn];
struct edge{
	int u,v,w;
	bool vis;
}ed[20010]; 
vector<int> g[maxn];
bool cmp(edge a,edge b){
	return a.w<b.w;
}
void inti(){
	for(int i=1;i<=n;i++){
		g[i].clear();
		g[i].push_back(i);
		fa[i]=i;
	}
}
int findf(int x){
	if(x==fa[x]) return x;
	else return fa[x]=findf(fa[x]);
}
int kruskal(){
	sort(ed+1,ed+1+m,cmp);
	inti();
	int ans=0,cnt=0;
	for(int i=1;i<=m;i++){
		if(cnt==n-1) break;   //已经ok了
		int fa1=findf(ed[i].u);
		int fa2=findf(ed[i].v);
		if(fa1!=fa2){
			cnt++;
			ed[i].vis=1;
			ans+=ed[i].w;
			int len_fx=g[fa1].size();
			int len_fy=g[fa2].size();
			for(int j=0;j<len_fx;j++){
				for(int k=0;k<len_fy;k++){
					maxx[g[fa1][j]][g[fa2][k]]=maxx[g[fa2][k]][g[fa1][j]]=ed[i].w;
				}
			}
			fa[fa1]=fa2;
			for(int j=0;j<len_fx;j++){
				g[fa2].push_back(g[fa1][j]);
			}
		} 
	}
	return ans;
}

int second_kruskal(int mst){
	int ans=INF;
	for(int i=1;i<=m;i++){
		if(!ed[i].vis){  //这条边没有访问过 
 			ans=min(ans,mst+ed[i].w-maxx[ed[i].u][ed[i].v]);
		}
	}
	return ans;
}
int main(){
		scanf("%d %d",&n,&m);
		for(int i=1;i<=m;i++){
			scanf("%d %d %d",&ed[i].u,&ed[i].v,&ed[i].w);
			ed[i].vis=0;
		}
		int mst=kruskal();
		int sec=second_kruskal(mst);
		printf("%d\n",sec);
	
	return 0;
}
 

/*
先挑出need条最短的边,再从黑边里面挑组成最小生成树不就行了?这样不行,因为这样它就干扰了原来的最小生成树,不能保证最优解.
因为kruskal算法的根本是边的权值要单调递增.所以我们可以从这里下手,把每一条白边加上一个值,改变每一条边的排列顺序,最后计算答案时就只需要减去
原来加上的值就可以了.由于我们不知道要加上多少,所以我们可以用二分答案来做每一次的判断来得到答案.
意:如果两条边权值相等,白边的优先级要高一些.
二分答案，考虑我们往白边上加值或者减值，那么就会对应的少选白边或者少选黑边

那么如果当前  白边+mid如果kuskal选择白边比need多就继续往上面加值，如果选择白边比need少就往下减值

因为kuskal保证图一定连通，并且代价最小。所以保证了正确性
*/
//呜呜呜呜，不知道哪里错了
#include<bits/stdc++.h>
#define maxn 50005
using namespace std;
int n,m,p,father[maxn],ans,sum,cnt,white;
struct node{
    int u,v,dis,c;
}edge[maxn*4];
inline bool cmp(node x,node y)
{
    if(x.dis==y.dis) return x.c<y.c;//权值相等白边优先级高
    return x.dis<y.dis;
}
inline int find(int x)
{
    if(father[x]!=x) father[x]=find(father[x]);
    return father[x];
}
inline bool check(int x)//二分答案+kruskal
{
    for(int i=0;i<=n;i++) father[i]=i;
    for(int i=1;i<=m;i++)
    {
        if(!edge[i].c) edge[i].dis+=x;//加上x的值
    }
    sort(edge+1,edge+m+1,cmp);
    cnt=0,white=0,sum=0;
    for(int i=1;i<=m;i++)//略作修改的kruskal模板
    {
        if(cnt==n-1) break;
        int x=find(edge[i].u),y=find(edge[i].v);
        if(x==y) continue;
        father[x]=y;
        cnt++;
        sum+=edge[i].dis;
        if(!edge[i].c) white++;
    }
    for(int i=1;i<=m;i++)
    {
        if(!edge[i].c) edge[i].dis-=x;//还原
    }
    if(white>=p) return 1;
    return 0;
}
int main()
{
    scanf("%d%d%d",&n,&m,&p);
    for(int i=1;i<=m;i++) scanf("%d%d%d%d",&edge[i].u,&edge[i].v,&edge[i].dis,&edge[i].c);
    int l=-101,r=101,mid;
    while(l<=r)
    {
        mid=l+r>>1; 
        if(check(mid)) 
        {
            l=mid+1;
            ans=sum-p*mid;
        }
        else r=mid-1;
    } 
    printf("%d",ans);
    return 0;
} 

#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<stack>
#include<cstdio>
#include<queue>
#include<map>
#include<vector>
#include<set>
using namespace std;
const int maxn=2010;
const int INF=0x3fffffff;
typedef long long LL;
/*
对于不同的最小生成树，每种权值的边使用的数量是一定的，每种权值的边的作用是确定的
我们可以先做一遍Kruskal，求出每种权值的边的使用数量num
再对于每种权值的边，2^num搜索出合法使用方案，把每种权值的边的方案用乘法原理乘起来就是答案了
另外，最小生成树计数的数学原理（有点复杂5555）https://wenku.baidu.com/view/872eb02de2bd960590c677c6.html 
*/ 
int n,m;
struct node{
	int u,v,dis,pos;
}ed[maxn];
int fa[maxn];
int num[maxn],tot;
int st[maxn],cnt;
int summ,mod=31011;
LL ans=1;
bool cmp(node a,node b){
	return a.dis<b.dis;
}
int findf(int x){
	if(x==fa[x]) return x;
	else return fa[x]=findf(fa[x]);
}
void dfs(int kind,int now,int chosen){  //dfs(i,st[i],0);
	if(now==st[kind+1]) {   //到了下一个长度的坐标了 
		if(chosen==num[kind]) summ++,cout<<summ<<endl;//如果这种长度的边用了这么多次 
		return;
	}
	int fa1=findf(ed[now].u);
	int fa2=findf(ed[now].v);
	if(fa1!=fa2){
		fa[fa1]=fa2;  //合并 
		dfs(kind,now+1,chosen+1);  //选择这条边，进行下一条 
		fa[fa1]=fa1; //恢复 
		fa[fa2]=fa2;
	}
	dfs(kind,now+1,chosen);  //同一个连通块，就不选，接着下一个 
}
int main(){
	scanf("%d %d",&n,&m);
	for(int i=1;i<=m;i++){
		scanf("%d %d %d",&ed[i].u,&ed[i].v,&ed[i].dis);
	}
	for(int i=1;i<=n;i++) fa[i]=i;
	sort(ed+1,ed+1+m,cmp);
	//其实这些动作相当于再把长度离散化 
	for(int i=1;i<=m;i++){
		if(ed[i].dis!=ed[i-1].dis) st[++cnt]=i; //不同长度边的 下标 
		ed[i].pos=cnt; //所在的位置 
	}
	st[cnt+1]=m+1;
	for(int i=1;i<=m;i++){
		int fa1=findf(ed[i].u);
		int fa2=findf(ed[i].v);
		if(fa1!=fa2) {
			fa[fa1]=fa2;
			num[ed[i].pos]++;   //这个位置的数（这个长度的边）用了多少次 
			tot++;  //生成树含有的边数 
		}
	}
	if(tot!=n-1) {
		printf("0\n");
		return 0;
	}
	for(int i=1;i<=n;i++) fa[i]=i;
	for(int i=1;i<=cnt;i++){
		if(num[i]){
			summ=0;
			dfs(i,st[i],0);
		//	cout<<summ<<endl;
			for(int j=st[i];j<st[i+1];j++){ //计算完了之后，这些长度一样的边就合并 
				fa[findf(ed[j].u)]=findf(ed[j].v);
			} 
			ans=(ans*summ)%mod;
		}
	}
	printf("%lld",ans);
return 0;
}

//再次哭泣
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=2000,Mod=31011;
int n,m,tot,sum,ans=1,cnt,st[maxn],fa[maxn],num[maxn];
struct edge{int x,y,dis,pos;}e[maxn];
void read(int &k){
    k=0; int f=1; char c=getchar();
    while(c<'0'||c>'9')c=='-'&&(f=-1),c=getchar();
    while('0'<=c&&c<='9')k=k*10+c-'0',c=getchar();
    k*=f;
}
int find(int x){return fa[x]==x?x:find(fa[x]);}
void dfs(int kind,int now,int chosen){
    if (now==st[kind+1]){
        if (chosen==num[kind]) {
        	sum++;
		}
        return;
    }
    int p=find(e[now].x),q=find(e[now].y);
    if (p!=q) fa[p]=q,dfs(kind,now+1,chosen+1),fa[p]=p,fa[q]=q;    
    dfs(kind,now+1,chosen);
}
bool cmp(edge a,edge b){return a.dis<b.dis;}
int main(){
    read(n); read(m);
    for (int i=1;i<=m;i++)read(e[i].x),read(e[i].y),read(e[i].dis);
    sort(e+1,e+m+1,cmp);
    for (int i=1;i<=m;i++) {
        if (e[i].dis!=e[i-1].dis) st[++cnt]=i;
        e[i].pos=cnt;
    }
    st[cnt+1]=m+1;
    for (int i=1;i<=n;i++) fa[i]=i;
    for (int i=1,x,y;i<=m;i++) 
        if ((x=find(e[i].x))!=(y=find(e[i].y))) fa[x]=y,num[e[i].pos]++,tot++;
    if (tot!=n-1) return puts("0"),0;
    for (int i=1;i<=n;i++) fa[i]=i;
    for (int i=1;i<=cnt;i++) if(num[i]){
        sum=0; dfs(i,st[i],0);
        
        for (int j=st[i];j<st[i+1];j++) fa[find(e[j].x)]=find(e[j].y);
        ans=1LL*ans*sum%Mod;
    }
    printf("%d",ans);
    return 0;
}