OI常用算法模板

置顶 已于 2024-02-24 09:56:29 修改
阅读量693 收藏 13
点赞数 9
分类专栏： C/C++/C# 文章标签： 算法
于 2024-02-20 14:18:52 首次发布
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/m0_71905144/article/details/136189284
版权

声明：本模板仅作学习参考，禁止用于其它用途，本人概不负责

文章目录

  • 声明：本模板仅作学习参考，禁止用于其它用途，本人概不负责
  • 模板
    • 负环
    • 矩阵快速幂
    • 拓补排序
    • SPFA
    • Dijkstra
    • 链式前向星
    • Floyd
    • 埃氏筛
    • 并查集
    • 高精度
    • 基本模板
    • 快速幂
    • 传递闭包
    • Kruskal

模板

负环

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define ve vector
#define endl '\n'
#define itn int
#define AC return 0
#define len length
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
using namespace std;
const int N=2e3+5;
struct Edge{
	itn to,val;
	Edge(int v,int w){
		to=v;
		val=w;
	}
};
ve<Edge> edge[N];
int n,m,dis[N],cnt[N];
bool vis[N];
void add(int u,int v,int w){
	edge[u].pb(Edge(v,w));
	if(w>=0)
		edge[v].pb(Edge(u,w));
}
queue<int> q;
void SPFA(){
	while(!q.empty())
		q.pop();
	memset(dis,0x7f,sizeof(dis));
	memset(cnt,0,sizeof(cnt));
	memset(vis,0,sizeof(vis));
	dis[1]=0;
	q.push(1);
	vis[1]=1;
	while(!q.empty()){
		itn now=q.front();
		q.pop();
		vis[now]=0;
		for(itn i=0;i<edge[now].size();i++){
			if(dis[edge[now][i].to]>dis[now]+edge[now][i].val){
				dis[edge[now][i].to]=dis[now]+edge[now][i].val;
				if(!vis[edge[now][i].to]){
					vis[edge[now][i].to]=1;
					q.push(edge[now][i].to);
					cnt[edge[now][i].to]++;
					if(cnt[edge[now][i].to]>=n){
						cout<<"YES"<<endl;
						return;
					}
				}
			}
		}
	}
	cout<<"NO"<<endl;
}
int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    //begin
    int t;
    cin>>t;
    while(t--){
    	cin>>n>>m;
    	for(int i=1;i<=n;i++)
    		edge[i].clear();
    	for(int i=1;i<=m;i++){
    		int u,v,w;
    		cin>>u>>v>>w;
    		add(u,v,w);
		}
		SPFA();
	}
	//end
    AC;
}

矩阵快速幂

#include<bits/stdc++.h>
#define ll long long
#define pb pushaack
#define ve vector
#define endl '\n'
#define itn int
#define AC return 0
#define len length
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
using namespace std;
const int N=1e2+5;
const int MOD=1e9+7;
ll n;
struct JuZhen{
	ll x[N][N];
}A,_a;
JuZhen operator*(const JuZhen &a,const JuZhen &b){
	JuZhen c;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			c.x[i][j]=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			for(int k=1;k<=n;k++){
				c.x[i][j]+=a.x[i][k]*b.x[k][j]%MOD;
				c.x[i][j]%=MOD;
			}
		}
	}
	return c;
}
int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    //begin
    ll k;
    cin>>n>>k;
    for(int i=1;i<=n;i++)
    	for(int j=1;j<=n;j++)
    		cin>>A.x[i][j];
    for(int i=1;i<=n;i++)
    	_a.x[i][i]=1;
    while(k>0){
    	if(k%2)
    		_a=_a*A;
    	A=A*A;
    	k/=2;
	}
    for(int i=1;i<=n;i++){
    	for(int j=1;j<=n;j++)
    		cout<<_a.x[i][j]<<' ';
    	cout<<endl;
	}
	//end
    AC;
}

拓补排序

//B3644
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define ve vector
#define endl '\n'
#define itn int
#define AC return 0
#define len length
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
using namespace std;
const int N=1e2+5;
ve<int> edge[N];
int indeg[N];
int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    //begin
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
    	int t;
    	while(cin>>t){
    		if(t){
    			edge[i].pb(t);
    			indeg[t]++;
			}
			else break;
		}
	}
	for(int i=1;i<=n;i++){
		int t;
		for(int j=1;j<=n;j++){
			if(!indeg[j]){
				t=j;
				break;
			}
		}
		cout<<t<<' ';
		for(int j=0;j<edge[t].size();j++)
			indeg[edge[t][j]]--;
		edge[t].clear();
		indeg[t]=0x7fffffff;
	}
	//end
    AC;
}

SPFA

const int N=3e5+5;
struct Edge{
	itn next,to;
	ll val;
}edge[N];
int head[N],cnt=0,dis[N],n,m,s;
bool vis[N];
inline void add(int u,int v,ll w){
	edge[++cnt]=(Edge){head[u],v,w};
	head[u]=cnt;
}
queue<int> q;
void SPFA(){
	for(int i=2;i<=n;i++)
		dis[i]=1e9;
	dis[s]=0;
	q.push(s);
	while(!q.empty()){
		int now=q.front();
		q.pop();
		vis[now]=0;
		for(int i=head[now];i;i=edge[i].next){
			if(dis[edge[i].to]>dis[now]+edge[i].val){
				dis[edge[i].to]=dis[now]+edge[i].val;
				if(!vis[edge[i].to]){
					vis[edge[i].to]=1;
					q.push(edge[i].to);
				}
			}
		}
	}
}

Dijkstra

const int M=5e5+5;
const int N=1e5+5;
struct node{
	int next,to,val;
}edge[M];
int head[N],dis[N],cnt=0,n,m,s;
bool vis[N];
void add(int u,int v,int w){
	edge[++cnt]=(node){head[u],v,w};
	head[u]=cnt;
}
priority_queue<pair<int,int>,ve<pair<int,int> >,greater<pair<int,int> > > q;
void dijkstra(){
	dis[s]=0;
	q.push(make_pair(0,s));
	while(!q.empty()){
		int now=q.top().second;
		q.pop();
		if(vis[now])
			continue;
		vis[now]=1;
		for(int i=head[now];i;i=edge[i].next)
			if(!vis[edge[i].to] and dis[edge[i].to]>dis[now]+edge[i].val){
				dis[edge[i].to]=dis[now]+edge[i].val;
				q.push(make_pair(dis[edge[i].to],edge[i].to));
			}
	}
}

链式前向星

const int M=5e5+5;
const int N=1e5+5;
struct node{
	int next,to,val;
}edge[M];
int head[N],dis[N],cnt=0,n,m,s;
bool vis[N];
void add(int u,int v,int w){
	edge[++cnt]=(node){head[u],v,w};
	head[u]=cnt;
}
//遍历
for(int i=head[now];i;i=edge[i].next){
	/*...*/
}

Floyd

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+5;
int dis[N][N],u,v,w;
void add(int u1,int v1,int w1){
	dis[u1][v1]=min(dis[u1][v1],w1);
	dis[v1][u1]=min(dis[v1][u1],w1);
}
int main()
{
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++){
            if(i!=j)dis[i][j]=0x3f3f3f3f;
            else dis[i][j]=0;
    	}
	for(int i=1;i<=m;i++){
		cin>>u>>v>>w;
		add(u,v,w);
	}
	for(int k=1;k<=n;k++)
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
                dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
    for(int i=1;i<=n;i++){
    	for(int j=1;j<=n;j++){
    		if(i==j)cout<<"0"<<" ";
    		else cout<<dis[i][j]<<" ";
    	}
    	cout<<endl;
    }
    return 0;
}

埃氏筛

bitset<2147483653> a=0;
void prime(int n){
	a[0]=a[1]=1;
	for(long long i=2;i<=sqrt(n);i++)
	    if(!a[i])
	    	for(long long j=i*i;j<=n;j+=i)
	    		a[j]=1;
}

并查集

class jf_set{
	private: 
		int *fa;
	public:
		jf_set(int size){
			fa=new int[size+1];
			for(int i=0;i<=size;i++)
				fa[i]=i;
		}
		jf_set(){
			fa=new int[10001];
			for(int i=0;i<=10001;i++)
				fa[i]=i;
		}
		void join(int a,int b){
			fa[find(a)]=find(b);
		}
		int find(int x){
			if(fa[x]!=x)fa[x]=find(fa[x]);
			return fa[x];
		}
		int same(int a,int b){
			return find(a)==find(b);
		}
		int count(){
			int s=0;
			for(int i=1;i<sizeof(fa);i++)
				if(fa[i]==i)
					s++;
			return s;
		}
};

高精度

const long long N=1e18;
struct bigint{
    int len,s[N];
    bigint(){
		memset(s,0,sizeof(s));
		len=1;
	}
    bigint(int num){
		*this=num;
	}
    bigint(string num){
		*this=num;
	}
    bigint operator =(int num){
        char c[N];
        sprintf(c,"%d",num);
        *this=c;
        return *this;
    }
    bigint operator =(string num){
        len=num.length();
        for(int i=0;i<len;i++)s[i]=num[len-1-i]-'0';
        return *this;
    }
    string str(){
        string res="";
        for(int i=0;i<len;i++)res=(char)(s[i]+'0')+res;
        return res;
    }
    void clean(){
        while(len>1&&!s[len-1])len--;
    }
    bigint operator +(const bigint &b){
        bigint c;    
        c.len=0;
        for(int i=0,g=0;g||i<len||i<b.len;i++){
            int x=g;
            if (i<len) x+=s[i];
            if (i<b.len) x+=b.s[i];
            c.s[c.len++]=x%10;
            g=x/10;
        }
        return c;
    }
    bigint operator -(const bigint &b){
        bigint c;
        c.len=0;
        int x;     
        for(int i=0,g=0;i<len;i++){
            x=s[i]-g;
            if (i<b.len) x-=b.s[i];
            if (x>=0) g=0;
            else{          
                x+=10;
                g=1;
            }
            c.s[c.len++]=x;
        }
        c.clean();
        return c;
    }
    bigint operator *(const bigint &b){
        bigint c;
        c.len=len+b.len;
        for(int i=0;i<len;i++)
			for (int j=0;j<b.len;j++)
				c.s[i+j]+=s[i]*b.s[j];
        for(int i=0;i<c.len-1;i++){
			c.s[i+1]+=c.s[i]/10;
			c.s[i]%=10;
		}
        c.clean();
        return c;  
    }
    bool operator <(const bigint &b){
        if (len!=b.len) return len<b.len;
        for (int i=len-1;i>=0;i--)
			if(s[i]!=b.s[i])
				return s[i]<b.s[i];
        return 0;
    }
    bool operator >(const bigint &b){
        if (len!=b.len) return len>b.len;
        for (int i=len-1;i>=0;i--)
			if(s[i]!=b.s[i])
				return s[i]>b.s[i];
        return 0;
    }
    bool operator ==(const bigint &b){
        if (len!=b.len) return 0;
        return !(*this<b)and!(*this<b);
        return 0;
    }
    bigint operator +=(const bigint &b){
        *this=*this+b;
        return *this;
    }
    bigint operator -=(const bigint &b){
        *this=*this-b;
        return *this;
    }
};
istream& operator >>(istream &in,bigint &x){
	string s;
	in>>s;
	x=s.c_str();
	return in;
}
ostream& operator <<(ostream &out,bigint &x){
    out<<x.str();
    return out;
}

基本模板

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define ve vector
#define endl '\n'
#define itn int
#define AC return 0
#define len length
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
using namespace std;
int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    //begin

	//end
    AC;
}

快速幂

long long fpow(int a,int b,int p){
	long long _a=1,_b=a;
	while(b>0){
		if(b%2)
			_a=(_a*_b)%p;
		_b=(_b*_b)%p;
		b/=2;
	}
	return _a;
}

传递闭包

#include<bits/stdc++.h>
using namespace std;
const int N=1e2+5;
int dis[N][N],u,v,w;
void add(int u1,int v1,int w1){
	dis[u1][v1]=min(dis[u1][v1],w1);
	dis[v1][u1]=min(dis[v1][u1],w1);
}
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	    for(int j=1;j<=n;j++)
	        cin>>dis[i][j];
	for(int k=1;k<=n;k++)
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
                dis[i][j]|=dis[i][k]&dis[k][j];
    for(int i=1;i<=n;i++){
    	for(int j=1;j<=n;j++)
    		cout<<bool(dis[i][j])<<" ";
    	cout<<endl;
    }
    return 0;
}

Kruskal

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define ve vector
#define endl '\n'
#define itn int
#define AC return 0
#define len length
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
using namespace std;
const int N=5e3+5;
const int M=2e5+5;
struct Edge{
	int from,to,val;
	bool operator<(const Edge& b)const{
		return this->val<b.val;
	}
}edge[M];
int fa[N];
int find(int x){
	return fa[x]==x?x:fa[x]=find(fa[x]);
}
inline void join(int x,int y){
	fa[find(x)]=find(y);
}
inline bool same(int x,int y){
	return find(x)==find(y);
}
int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    //begin
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    	fa[i]=i;
    for(int i=1;i<=m;i++){
    	itn u,v,w;
    	cin>>u>>v>>w;
    	edge[i]=(Edge){u,v,w};
	}
	sort(edge+1,edge+m+1);
	itn cnt,ans;
	cnt=ans=0;
	for(int i=1;i<=m;i++){
		if(!same(edge[i].from,edge[i].to)){
			ans+=edge[i].val;
			cnt++;
			join(edge[i].from,edge[i].to);
		}
		if(cnt==n-1){
			cout<<ans;
			AC;
		}
	}
	cout<<"orz";
	//end
    AC;
}
评论
添加红包

请填写红包祝福语或标题

个

红包个数最小为10个

元

红包金额最低5元

当前余额3.43元 前往充值 >
需支付：10.00元
成就一亿技术人!
领取后你会自动成为博主和红包主的粉丝 规则
hope_wisdom
发出的红包

打赏作者

Code Writers

你的鼓励将是我创作的最大动力

¥1 ¥2 ¥4 ¥6 ¥10 ¥20
扫码支付：¥1
获取中
扫码支付

您的余额不足，请更换扫码支付或充值

打赏作者

实付元
使用余额支付
点击重新获取
扫码支付
钱包余额 0

抵扣说明：

1.余额是钱包充值的虚拟货币，按照1:1的比例进行支付金额的抵扣。
2.余额无法直接购买下载，可以购买VIP、付费专栏及课程。

余额充值