专栏文章

7.10

bbokaro_kyoku_mania
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mioxmwjq
此快照首次捕获于
2025/12/03 02:49
3 个月前
此快照最后确认于
2025/12/03 02:49
3 个月前
查看原文
P3366:
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+20;
int n,m,p[N],ans,res;
struct Edge{
	int x,y,z;
}e[N];
const bool cmp(Edge x,Edge y){
	return x.z<y.z;
}
int get_p(int x){
	return x==p[x]?x:p[x]=get_p(p[x]);
}
void Kruskal(){
	sort(e+1,e+1+m,cmp);
	for(int i=1;i<=n;i++){
		p[i]=i;
	}
	for(int i=1;i<=m;i++){
		int x=e[i].x;
		int y=e[i].y;
		x=get_p(x);
		y=get_p(y);
		if(x!=y){
			res--;
			ans+=e[i].z;
			p[x]=y;
		}
	}
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>m;
	res=n;
	for(int i=1;i<=m;i++){
		cin>>e[i].x>>e[i].y>>e[i].z;
	}
	Kruskal();
	if(res==1){
		cout<<ans;
	}
	else{
		cout<<"orz\n";
	}
	
	
	
	
	return 0;
}
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+50;
vector<pair<int,int> >e[N];
int n,m,ans,res,d[N];
bool vis[N];
priority_queue<pair<int,int> >q;
void prim(){
	memset(d,0x3f,sizeof d);
	d[1]=0;
	q.push(make_pair(0,1));
	while(!q.empty()){
		int x=q.top().second;
		q.pop();
		if(vis[x]){
			continue;
		}
		vis[x]=1;
		ans+=d[x];
		res++;
		for(auto to:e[x]){
			if(d[to.first]>to.second){
				d[to.first]=to.second;
				q.push(make_pair(-d[to.first],to.first));
			}
		}	
	}
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int x,y,z;
		cin>>x>>y>>z;
		e[x].push_back(make_pair(y,z));
		e[y].push_back(make_pair(x,z));
	}
	prim();
	if(res==n) cout<<ans<<"\n";
	else cout<<"orz\n";
	
	
	
	
	return 0;
}
P3388:
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
template<typename T>inline void read(T&x){
	x=0;
	char c;
	int sign=1;
	do{
		c=getchar();
		if(c=='-'){
			sign=-1;
		}
	}while(!isdigit(c));
	do{
		x=x*10+c-'0';
		c=getchar();
	}while(isdigit(c));
	x*=sign;
}
const int N=1e6+10;
int n,m;// n������ m������
int dfn[N],low[N],idx,res;
// dfn����¼ÿ�����ʱ���
// low���ܲ��������׵�����С�ı�ţ�idx��ʱ�����res��������
bool vis[N],flag[N];// flag: �� vis������Ƿ��ظ�
vector<int> edge[N];// ��ͼ�õ�
void Tarjan(int u,int fa){ // u ��ǰ��ı�ţ�fa �Լ��ְֵı��
	vis[u]=true;// ���
	low[u]=++idx;// ����ʱ���
	dfn[u]=low[u];
	int child=0;// ÿһ�����������
	for(const auto &v:edge[u]){// ���������������ھ� ��C++11��
	    if(!vis[v]){
    		child++;// ����һ������
    		Tarjan(v,u);// ����
	    	low[u]=min(low[u], low[v]);// �����ܵ�����С�ڵ���
    		if(fa!=u&&low[v]>=dfn[u]&&!flag[u]){// ��Ҫ����
        	// ��������Լ����Ҳ�ͨ�����׷��ص���С����ϸ���Ҫ�󣬲���û�б���ǹ�
			// Ҫ��Ϊ��ɾ�˸���������ȥ�ˣ���Ϊ�����������
	        	flag[u]=1;
    	    	res++; // ��¼��
    		}
    	}
		else if(v!=fa){
    		// �������㲻���Լ��ĸ��ף������ܵ�����С�ڵ���
    		low[u]=min(low[u],dfn[v]);
		}
	}
	// ��Ҫ���룬�Լ��Ļ���Ҫ 2 �����Ӳſ���
	if (fa==u&&child>=2&&!flag[u]){
    	flag[u]=true;
    	res++;// ��¼��
	}
}
signed main(){
	read(n);
	read(m);// ��������
	for(int i=1;i<=m;i++){// ע����Ǵ� 1 ��ʼ��
    	int x,y;
	    read(x);
	    read(y);
		edge[x].push_back(y);
    	edge[y].push_back(x);// ʹ�� vector ��ͼ
	}
	for(int i=1;i<=n;i++){
		if(!vis[i]){// ��Ϊ Tarjan ͼ��һ����ͨ
    		idx=0;// ʱ�����ʼΪ 0
    		Tarjan(i,i);// �ӵ� i ���㿪ʼ������Ϊ�Լ�
    	}
	}
    
	cout<<res<<"\n";
	for(int i=1;i<=n;i++){
		if(flag[i]){
			cout<<i<<" ";// ������
		}
	}
    
    
    
    
    
    
	return 0;
}
P3958:
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
template<typename T>inline void read(T&x){
	x=0;
	char c;
	int sign=1;
	do{
		c=getchar();
		if(c=='-'){
			sign=-1;
		}
	}while(!isdigit(c));
	do{
		x=x*10+c-'0';
		c=getchar();
	}while(isdigit(c));
	x*=sign;
}
const int N=1e3+50; 
struct Edge{
	int x,y;
	Edge(int _x,int _y){
		x=_x;
		y=_y;
	}
};
vector<Edge>e;
int n,p[N];
bool k1[N],k2[N];
int X[N],Y[N],Z[N],h,r;
int dis(int a,int b){
	return (X[a]-X[b])*(X[a]-X[b])+(Y[a]-Y[b])*(Y[a]-Y[b])+(Z[a]-Z[b])*(Z[a]-Z[b]);
}
int get_p(int x){
	return p[x]==x?x:p[x]=get_p(p[x]);
}
void clear(){
	e.clear();	
	for(int i=1;i<=n;i++){
		k1[i]=0;
		k2[i]=0;
	}
		
}
void solve(){
	read(n);
	read(h);
	read(r);
	for(int i=1;i<=n;i++){
		read(X[i]);
		read(Y[i]);
		read(Z[i]);
		for(int j=1;j<i;j++)
			if(dis(i,j)<=4*r*r){
				e.push_back(Edge(i,j));
			}
		if(Z[i]<=r){
			k1[i]=1;
		}
		if(Z[i]>=h-r){
			k2[i]=1;
		}
		p[i]=i;
	}
	for(auto i:e){
		int x=i.x;
		int y=i.y;
		x=get_p(x);
		y=get_p(y);
		if(x!=y){
			p[x]=y;
		}
	}
	bool k=0;
	for(int i=1;i<=n;i++){
		k1[get_p(i)]|=k1[i];
		k2[get_p(i)]|=k2[i];
		if(k1[get_p(i)]&&k2[get_p(i)]){
			k=1;
		}
	}
	if(k==1){
		cout<<"Yes\n";
	}
	else{
		cout<<"No\n";
	}
	clear();
}
int t;
signed main(){
	read(t);
	while(t--){
		solve();
	}
	
	
	
	
	
	return 0;
}
UVA1151:
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
template<typename T>inline void read(T&x){
	x=0;
	char c;
	int sign=1;
	do{
		c=getchar();
		if(c=='-'){
			sign=-1;
		}
	}while(!isdigit(c));
	do{
		x=x*10+c-'0';
		c=getchar();
	}while(isdigit(c));
	x*=sign;
}
int n,q;
const int N=1e3+50;
int in[9][N],p[N],w[9],X[N],Y[N];
struct Edge{
	int x,y,z;
}e[N*N];
const bool cmp(Edge x,Edge y){
	return x.z<y.z;
}
int get_p(int x){
	return p[x]==x?x:p[x]=get_p(p[x]);
}
void solve(){
	read(n);
	read(q);
	for(int i=1;i<=q;i++){
		read(in[i][0]);
		read(w[i]);
		for(int j=1;j<=in[i][0];j++){
			read(in[i][j]);
		}
	}
	int m=0;
	for(int i=1;i<=n;i++){
		read(X[i]);
		read(Y[i]);
		for(int j=1;j<i;j++){
			e[++m].x=i;
			e[m].y=j;
			e[m].z=(X[i]-X[j])*(X[i]-X[j])+(Y[i]-Y[j])*(Y[i]-Y[j]);
		}
	}
	sort(e+1,e+1+m,cmp);
	int res=0,ans=0;
	for(int i=1;i<=n;i++){
		p[i]=i;
	}
	for(int i=1;i<=m;i++){
		int x=e[i].x,y=get_p(e[i].y);
		x=get_p(e[i].x),get_p(e[i].y);
		if(x!=y){
			e[++res]=e[i];
			p[x]=y;
			ans+=e[i].z;
		}
	}
	int s=(1<<q)-1;
	for(int i=1;i<=s;i++){
		int ans2=0;
		for(int j=1;j<=n;j++){
			p[j]=j;
		}
		for(int j=1;j<=8;j++){
			if(i&(1<<j-1)){
				ans2+=w[j];
				for(int k=2;k<=in[j][0];k++){
					int x=in[j][k],y=in[j][k-1];
					x=get_p(x);
					y=get_p(y);
					if(x!=y){
						p[x]=y;
					}
				}
			}
		}
		for(int j=1;j<n;j++){
			int x=e[j].x,y=e[j].y;				
			x=get_p(e[j].x),y=get_p(e[j].y);
			if(x!=y){
				p[x]=y;
				ans2+=e[j].z;
			}
		}
		ans=min(ans,ans2);
	}
	cout<<ans<<"\n";
}
int t;
signed main(){
	read(t);
	while(t--){
		solve();
		if(t)cout<<"\n";
	}
	
	
	
	
	
	
	
	return 0;
}
UVA1395:
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+20;
int n,m,p[N],ans,res;
struct Edge{
	int x,y,z;
}e[N];
const bool cmp(Edge x,Edge y){
	return x.z<y.z;
}
int get_p(int x){
	return x==p[x]?x:p[x]=get_p(p[x]);
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	while(1){
		cin>>n>>m;
		if(n==0&&m==0)break;
		
		for(int i=1;i<=m;i++){
			cin>>e[i].x>>e[i].y>>e[i].z;
		}
		sort(e+1,e+1+m,cmp);
		ans=INT_MAX;
		for(int z=1;z<=m;z++){
			res=n;
			for(int i=1;i<=n;i++){
				p[i]=i;
			}
			for(int i=z;i<=m;i++){
				int x=e[i].x;
				int y=e[i].y;
				x=get_p(x);
				y=get_p(y);
				if(x!=y){
					res--;
					p[x]=y;
					if(res==1){
						ans=min(ans,e[i].z-e[z].z);
						break;
					}
				}
			}
			if(res!=1)break;
		}
		
		if(ans!=INT_MAX){
			cout<<ans<<"\n";
		}
		else{
			cout<<"-1\n";
		}
	}
	
	
	
	
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...