OI常用算法模板

一时失言乱红尘 2024-05-11 09:27 72阅读 0赞

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

#### 文章目录 ####

*  声明：本模板仅作学习参考，禁止用于其它用途，本人概不负责
 *  模板
 *   *  负环
     *  矩阵快速幂
     *  拓补排序
     *  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));
    			}
    	}
    }

### 链式前向星 ###

### 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;
    }

### 基本模板 ###

### 快速幂 ###

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;
    }