2912–分组行动

作者 macorhard

【问题描述】
最近， 木木中学要举行一年一度的辩论赛了， 我们活泼开朗乐观向上不寂寞不生病不挂科天天回家吃饭的新时代好少年——飞飞， 自然是热情参与咯！ 辩论嘛， 就有正方和反方两个组， 这是一个传统项目， 所以， 包括飞飞， 木木中学的每一个学生都会加入 2 个组中的一个， 不会有人打酱油的（如果有人打酱油， 那么飞飞会义无反顾义不容辞的上前用一翻惊天动地的演说打消他打酱油的念头的）。


自然啦， 作为有思想有文化能言善辩的好少年， 飞飞， 其实加入哪个组， 从技术角度分析真是无所谓的， 不过呢， 从另外一些角度来看， 就复杂的多了……


比如， 飞飞是个很不喜欢八卦的正义青年， 所以啊， 飞飞很不想和年级最 PP 的女生青菜分在一个组， 因为会产生八卦的——为什么会有八卦？ 首先是他们比较熟， 最重要的就是因为飞飞是大帅哥啊！ 人长得帅， 有时候真是挺麻烦的， 尤其飞飞还如此低调……


在比如， 飞飞也不想和小邱分在一个组——虽然他们不认识， 但是， 飞飞听说小邱很懒还很暴力， 飞飞不喜欢暴力……当然了， 不论如何的分组行动， 都会产生一些代价的， 比如两个好朋友分在了不同的组，那肯定不是很高兴了。


飞飞知道， 学校里有 M 对同学是相互认识的， 每对认识的同学间， 都有一个要好程度
C， 自然的， 关系越好， 要好程度越高， 也越不愿意分开。 对于一个分组方案， 必然会使得有某些认识的同学分开， 飞飞认为， 一个分组方案的代价就是最不愿意分开的那两个同学之间的要好程度。


飞飞在想， 和青菜 MM 分在不同的组最小代价是多少呢？ 和小邱同学分在不同的组最
小代价是多少呢？ 如果…… 还要将青菜MM和小邱分在不同的组最小代价是多少呢？ ……
好麻烦啊， 飞飞越想越乱， 于是来找你帮忙了。


一些说明：


木木中学有 N 个学生， 木木中学是一所优秀的中学， 学生们都是开朗外向的， 所以一个学校里任意两个学生间接或者直接肯定认识。
显然任意一个辩论组都至少得有一个人。

为了方便， 我们把木木中学的学生用 1 到 N 编号， 飞飞有 Q 个问题， 每个问题的形式都是这样的： 将编号为 a 的学生与编号为 b 的学生分在不同组中， 最少的代价是多少呢？


关于这道题目本身， 只是想检验你能不能帮飞飞， 所以你并不需要一一具体回答每个问题，只需要最后输出每个问题答案的乘积除以 P 的余数就可以了。

INPUT


第一行 4 个正整数， N， M， Q， P第 2~M+1 行， 每行 3 个正整数 a,b,c， 表示编号为 a 的同学和编号为 b 的同学认识， 并且要好程度是 c。 保证 a 和 b 是不会相同的， 也不会有多行描述相同两个学生之间的关系。

第 M+2~M+Q+1 行， 每行 2 个正整数 a,b， 表示飞飞的一个问题， 这里保证 a 和 b 是不
同的。

Solution 1

并查集。 类似于“关押罪犯”。 先按照关系值从大到小排序， 然后对于每个询问
都从权值大的边开始添加， 每添加一条边， 然后查询看询问的两个点连通没有， 若已连通，则当前边权值即为答案。 否则继续操作。 

#include<fstream>
#include<algorithm>
using namespace std;
ifstream cin("group.in");
ofstream cout("group.out");
struct Ctn
{
	int a,b,c;
} Edge[100005];
int fa[50005],N,M,Q,P;
void Read()
{
	cin>>N>>M>>Q>>P;
	for(int i=1; i<=M; i++)cin>>Edge[i].a>>Edge[i].b>>Edge[i].c;
}
bool cmp(const Ctn &x,const Ctn &y)
{
	return x.c>y.c;
}
int GetFather(int x)
{
	if(fa[x]==x)return x;
	fa[x]=GetFather(fa[x]);
	return fa[x];
}
void Solve()
{
	int i,j,a,b,x,y,t,ans=1,faa,fb,fx,fy;
	sort(Edge+1,Edge+M+1,cmp);//按照关系值从大到小排序
	for(j=1; j<=Q; j++)
	{
		cin>>x>>y;
		for(i=1; i<=N; i++)fa[i]=i;
		for(i=1; i<=M; i++)
		{
			a=GetFather(Edge[i].a);
			b=GetFather(Edge[i].b);
			fa[a]=b;
			fx=GetFather(x);
			fy=GetFather(y);
			if(fx==fy)
			{
				t=Edge[i].c;
				break;
			}
		}
		ans=((t%P)*ans)%P;
	}
	cout<<ans<<endl;
}
int main()
{
	Read();
	Solve();
	return 0;
}

solution 2

先读入数据， 建立图；
用 Kruskal 求出最大权生成树；
对于每个询问(x,y)， 即在最大权生成树上求 LCA(x,y)： x 到 y 路径上的最小边权值。 

#include<iostream>
#include<iomanip>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;
const int SIZE(50005);
int n,m,Q,mod,prt[SIZE],g[SIZE],h[SIZE],cnt,p[SIZE][20],gg[SIZE][20],d[SIZE];
struct edge
{
	int x,y,z;
} e[2*SIZE];
struct star
{
	int to,next,v;
} a[2*SIZE];
long long Ans=1;
bool cmp(edge x,edge y)
{
	return x.z>y.z;
}
void AddEdge(int x,int y,int z)
{
	cnt++;
	a[cnt].to=y;
	a[cnt].v=z;
	a[cnt].next=h[x];
	h[x]=cnt;
}
void Read()
{
	scanf("%d%d%d%d",&n,&m,&Q,&mod);
	int x,y,z;
	for(int i=1; i<=m; i++)
		scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].z);
}
int GetFather(int x)
{
	if(prt[x]==x)return x;
	return prt[x]=GetFather(prt[x]);
}
void Kruskal()
{
	sort(e+1,e+m+1,cmp);
	for(int i=1; i<=n; i++)prt[i]=i;
	for(int i=1; i<=m; i++)
	{
		int f1=GetFather(e[i].x),f2=GetFather(e[i].y);
		if(f1!=f2)
		{
			prt[f1]=f2;
			AddEdge(e[i].x,e[i].y,e[i].z);
			AddEdge(e[i].y,e[i].x,e[i].z);
		}
	}
}
void DFS(int x,int fa,int v,int dep)
{
	prt[x]=fa;
	g[x]=v;//边权转为点权
	d[x]=dep;//深度
	for(int i=h[x]; i; i=a[i].next)
		if(a[i].to!=fa)DFS(a[i].to,x,a[i].v,dep+1);
}
void ST()
{
	for(int i=1; i<=n; i++)
		for(int j=1; j<=int(log(n)/log(2)); j++)p[i][j]=-1;
	for(int i=1; i<=n; i++)
	{
		p[i][0]=prt[i];
		gg[i][0]=g[i];
	}
	for(int j=1; j<=int(log(n)/log(2)); j++)
		for(int i=1; i<=n; i++)
			if(p[i][j-1]!=-1)
			{
				p[i][j]=p[p[i][j-1]][j-1];
				gg[i][j]=min(gg[i][j-1],gg[p[i][j-1]][j-1]);
			}
}
long long LCA(int a,int b)
{
	if(d[a]<d[b])swap(a,b);
	int k=int(log(d[a])/log(2)),ret=0x7fffffff/2;
	for(int i=k; i>=0; i--)
		if(d[a]-(1<<i)>=d[b])
		{
			ret=min(ret,gg[a][i]);
			a=p[a][i];
		}
	if(a==b)return ret;
	for(int i=k; i>=0; i--)
		if(p[a][i]!=-1&&p[a][i]!=p[b][i])
		{
			ret=min(ret,gg[a][i]);
			a=p[a][i];
			ret=min(ret,gg[b][i]);
			b=p[b][i];
		}
	ret=min(gg[a][0],min(ret,gg[b][0]));
	return ret;
}
int main()
{
	freopen("group.in","r",stdin);
	freopen("group.out","w",stdout);
	Read();
	Kruskal();
	DFS(1,0,0,1);
	ST();
	int x,y;
	for(int i=1; i<=Q; i++)
	{
		scanf("%d%d",&x,&y);
		Ans*=LCA(x,y);
		Ans%=mod;
	}
	printf("%lld\n",Ans);
	return 0;
}

留下评论