7.10
P3366:
#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;
} #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:
#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:
#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:
#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:
#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;
}