# 剪切板()-其他

## 剪切板()

### 代码

``````#include <bits/stdc++.h>
#define ll long long
#define rll register ll
#define cll const ll
#define N 1000005
using namespace std;
{
rll x=0;bool f=1;register char c=getchar();
while(c<48||c>57){if(c=='-') f=0;c=getchar();}
while(c>=48&&c<=57){x=x*10+(c^48);c=getchar();}
return f?x:-x;
}
inline void write(ll x)
{
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+48);
}
struct node{ll x,y,z;}e[N];
inline bool cmp(node a,node b){return a.z<b.z;}
ll ans,cnt,f[N];
inline ll find(ll x)
{
if(x==f[x]) return x;
return f[x]=find(f[x]);
}
int main()
{
for(rll i=1;i<=m;i++)
sort(e+1,e+1+m,cmp);
for(rll i=1;i<=n;i++) f[i]=i;
for(rll i=1;i<=m;i++)
{
cll x=find(e[i].x),y=find(e[i].y);
if(x==y) continue;
f[x]=y,ans+=e[i].z,cnt++;
}
if(cnt<n-1) cout << "impossible";
else write(ans);
return 0;
}
``````

### 代码

``````#include <bits/stdc++.h>
#define ll long long
#define rll register ll
#define cll const ll
#define N 505
using namespace std;
{
rll x=0;bool f=1;register char c=getchar();
while(c<48||c>57){if(c=='-') f=0;c=getchar();}
while(c>=48&&c<=57){x=x*10+(c^48);c=getchar();}
return f?x:-x;
}
inline void write(ll x)
{
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+48);
}
bool flag[N];
inline void prim()
{
memset(dis,0x3f,sizeof dis);
dis[1]=0;
for(rll i=0;i<n;i++)
{
rll t=-1;
for(rll j=1;j<=n;j++)
if(!flag[j]&&(t==-1||dis[t]>dis[j])) t=j;
if(i&&dis[t]>=0x3f3f3f3f3f3f3f3f){cout << "impossible";return;}
if(i) ans+=dis[t];
for(rll j=1;j<=n;j++)
dis[j]=min(dis[j],g[t][j]);
flag[t]=1;
}
write(ans);
}
int main()
{
memset(g,0x3f,sizeof g);
while(m--)
{
g[a][b]=g[b][a]=min(g[a][b],c);
}
prim();
return 0;
}
``````
————————

### 代码

``````#include <bits/stdc++.h>
#define ll long long
#define rll register ll
#define cll const ll
#define N 1000005
using namespace std;
{
rll x=0;bool f=1;register char c=getchar();
while(c<48||c>57){if(c=='-') f=0;c=getchar();}
while(c>=48&&c<=57){x=x*10+(c^48);c=getchar();}
return f?x:-x;
}
inline void write(ll x)
{
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+48);
}
struct node{ll x,y,z;}e[N];
inline bool cmp(node a,node b){return a.z<b.z;}
ll ans,cnt,f[N];
inline ll find(ll x)
{
if(x==f[x]) return x;
return f[x]=find(f[x]);
}
int main()
{
for(rll i=1;i<=m;i++)
sort(e+1,e+1+m,cmp);
for(rll i=1;i<=n;i++) f[i]=i;
for(rll i=1;i<=m;i++)
{
cll x=find(e[i].x),y=find(e[i].y);
if(x==y) continue;
f[x]=y,ans+=e[i].z,cnt++;
}
if(cnt<n-1) cout << "impossible";
else write(ans);
return 0;
}
``````

### 代码

``````#include <bits/stdc++.h>
#define ll long long
#define rll register ll
#define cll const ll
#define N 505
using namespace std;
{
rll x=0;bool f=1;register char c=getchar();
while(c<48||c>57){if(c=='-') f=0;c=getchar();}
while(c>=48&&c<=57){x=x*10+(c^48);c=getchar();}
return f?x:-x;
}
inline void write(ll x)
{
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+48);
}
bool flag[N];
inline void prim()
{
memset(dis,0x3f,sizeof dis);
dis[1]=0;
for(rll i=0;i<n;i++)
{
rll t=-1;
for(rll j=1;j<=n;j++)
if(!flag[j]&&(t==-1||dis[t]>dis[j])) t=j;
if(i&&dis[t]>=0x3f3f3f3f3f3f3f3f){cout << "impossible";return;}
if(i) ans+=dis[t];
for(rll j=1;j<=n;j++)
dis[j]=min(dis[j],g[t][j]);
flag[t]=1;
}
write(ans);
}
int main()
{
memset(g,0x3f,sizeof g);
while(m--)
{