刚学oi1e-10s,十分求助
  • 板块P1194 买礼物
  • 楼主Shirο
  • 当前回复3
  • 已保存回复3
  • 发布时间2020/10/6 07:51
  • 上次更新2023/11/5 11:52:02
查看原帖
刚学oi1e-10s,十分求助
88686
Shirο楼主2020/10/6 07:51
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
using namespace std;
const int maxn=5e3+5;
const int maxm=1e6+5;
#define __ read()
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
class edge
{
	public:
		int x,y,l;
		edge(void);
		edge(int X,int Y,int L);
		void print();	
}e[maxm];
edge::edge(void){}
edge::edge(int X,int Y,int L){x=X;y=Y;l=L;}
void edge::print(){printf("%d %d %d\n",x,y,l);}
bool cmp(edge e1,edge e2){return e1.l<e2.l;}
int ans=0,g[maxn][maxn],prt[maxn],A,B,cnt=0;
void input()
{
	A=__,B=__;rep(i,1,B)rep(j,1,B)g[i][j]=__;
	rep(i,1,B)rep(j,i+1,B)e[++cnt]=edge(i,j,g[i][j]);
	rep(i,1,B)prt[i]=i;
}
int find(int x){if(prt[x]!=x)prt[x]=find(prt[x]);return prt[x];}
void merge(int x,int y){prt[find(x)]=find(y);}
void solve()
{
	sort(e+1,e+cnt+1,cmp);
	int ee=0;
	rep(i,1,cnt)
	{
		#define from find(e[i].x)
		#define to   find(e[i].y)
		#define len  (e[i].l)
			if(from!=to)
			{
				ans+=min(len,A);
				++ee;merge(from,to);
			}
			if(ee==B-1)break;
		#undef from
		#undef to
		#undef len
	}
	if(ee==B-1)printf("%d\n",ans+A);
	else puts("-1");

}
int main()
{
	input();
	solve();
}


2020/10/6 07:51
加载中...