模板复习

prim

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#include<algorithm>
using namespace std;
const int INF=0x3f3f3f3f;
const double PI=acos(-1.0);
typedef long long LL;
#define mem(x,y) memset(x,y,sizeof(x))
#define T_T while(T--)
#define F(i,x) for(i=1;i<=x;i++)
#define SI(x) scanf("%d",&x)
#define SL(x) scanf("%lld",&x)
#define PI(x) printf("%d",x)
#define PL(x) printf("%lld",x)
#define P_ printf(" ")
const int MAXN=110;
int vis[MAXN],low[MAXN],mp[MAXN][MAXN];
int N;
void prime(){
	int i,j;
	int ans=0;
	mem(vis,0);mem(low,INF);
	vis[1]=1;
	F(i,N)low[i]=mp[1][i];
	F(i,N){
		int temp=INF,k;
		F(j,N)if(!vis[j]&&temp>low[j])temp=low[k=j];
		if(temp==INF)break;
		ans+=temp;
		vis[k]=1;
		F(j,N)if(!vis[j]&&mp[k][j]<low[j])low[j]=mp[k][j];
	}
	PI(ans);puts("");
}
int main(){
	while(~scanf("%d",&N)){
		int i,j;
		mem(mp,INF);
		F(i,N){
			F(j,N){
				scanf("%d",&mp[i][j]);
			}
		}
		prime();
	}
	return 0;
}

　　kruthka

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#include<algorithm>
using namespace std;
const int INF=0x3f3f3f3f;
const double PI=acos(-1.0);
typedef long long LL;
#define mem(x,y) memset(x,y,sizeof(x))
#define T_T while(T--)
#define F(i,x) for(i=1;i<=x;i++)
#define SI(x) scanf("%d",&x)
#define SL(x) scanf("%lld",&x)
#define PI(x) printf("%d",x)
#define PL(x) printf("%lld",x)
#define P_ printf(" ")
const int MAXN=110;
int pre[MAXN];
int ans;
int find(int x){
	return x==pre[x]?x:find(pre[x]);
}
void merge(int x,int y,int z){
	if(pre[x]==0)pre[x]=x;
	if(pre[y]==0)pre[y]=y;
	int f1,f2;
	f1=find(x);f2=find(y);
	if(f1!=f2){
		pre[f1]=f2;ans+=z;
	}
}
int main(){
	int N;
	while(~scanf("%d",&N)){
		int i,j,x;
		mem(pre,0);
		ans=0;
		F(i,N){
			F(j,N){
				SI(x);
				merge(i,j,x);
			}
		}
		PI(ans);puts("");
	}
	return 0;
}

　　topu:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#include<algorithm>
#include<stack>
#include<queue>
using namespace std;
const int INF=0x3f3f3f3f;
const double PI=acos(-1.0);
typedef long long LL;
#define mem(x,y) memset(x,y,sizeof(x))
#define T_T while(T--)
#define F(i,x) for(i=1;i<=x;i++)
#define SI(x) scanf("%d",&x)
#define SL(x) scanf("%lld",&x)
#define PI(x) printf("%d",x)
#define PL(x) printf("%lld",x)
#define P_ printf(" ")
const int MAXN=1010;
int que[MAXN],ans[MAXN],head[MAXN],edgnum,N,top;
struct Edge{
	int from,to,next;
}edg[MAXN];
void initial(){
	mem(que,0);mem(head,-1);edgnum=0;top=0;
}
void add(int u,int v){
	Edge E={u,v,head[u]};
	edg[edgnum]=E;
	head[u]=edgnum++;
}
priority_queue<int,vector<int>,greater<int> >q;
void topu(){
	for(int i=1;i<=N;i++)if(!que[i])q.push(i);
	while(!q.empty()){
		int k=q.top();
		ans[top++]=k;
		q.pop();
		for(int j=head[k];j!=-1;j=edg[j].next){
			que[edg[j].to]--;
			if(!que[edg[j].to])q.push(edg[j].to);
		}
	}
	for(int i=0;i<top;i++)printf("%d ",ans[i]);puts("");
}
int main(){
	while(~scanf("%d",&N)){
		int a,b;
		initial();
		int i;
		F(i,N){
			scanf("%d%d",&a,&b);
			add(a,b);
			que[b]++;
		}
		topu();
	}
	return 0;
}