huangxihan

UID: 25, 注册于 2023-2-1 18:07:14, 最后登录于 2024-4-24 17:26:23, 目前离线.

解决了 89 道题目，RP: 168.21 (No. 82)

♂

个人简介

> Bilibili:小黄人de工作室
> https://wenku.baidu.com/view/9f3ccc51cf1755270722192e453610661fd95a46.html?_wkts_=1709111353938&bdQuery=%E6%84%9F%E6%82%9F%E5%88%9D%E4%B8%AD%E7%94%9F100%E4%B8%AA&needWelcomeRecommand=1
> 快速幂
> dfs
> bfs
> *dp
> dij最短路
> spfa最短路
> floyd最短路
> 全员最短路
> kruscal最小生成树
> prim最小生成树
> tajin强连通风量
> 割点
> 割边
> 缩点
> *次小路、生成树

次小路

#include <bits/stdc++.h>
#define PI pair<int,int>
#define INF 0x3f3f3f3f
using namespace std;
struct node{
	int v,w;
};
vector<node>a[5005];
int dis[5005],dis2[5005];
priority_queue<PI,vector<PI>,greater<PI> >q;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	int n,m,u,v,w;cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>u>>v>>w;
		a[u].push_back(node{v,w});
		a[v].push_back(node{u,w});
	}
	fill(dis+1,dis+n+1,INF);
	fill(dis2+1,dis2+n+1,INF);
	dis[1]=0;
	q.push(make_pair(0,1));
	while(q.size()){
		u=q.top().second;
		int d=q.top().first;
		q.pop();
		for(int i=0;i<a[u].size();i++){
			v=a[u][i].v;
			int d2=d+a[u][i].w;
			if(dis[v]>d2){
				swap(dis[v],d2);
				q.push(make_pair(dis[v],v));
			}
			if(dis2[v]>d2&&dis[v]<d2){
				dis2[v]=d2;
				q.push(make_pair(dis2[v],v));
			}
		}
	}
	cout<<dis2[n];
	return 0;
}

P1574 快速幂

#include<bits/stdc++.h>
#define int long long
using namespace std;
int p;int a,b;
int qpow(int a,int b){
	int ans=1;
	int base=a;
	while(b){
		if(b%2==1)ans*=base,ans%=p;
		base=(base*base)%p;
		b/=2;
	}
	return ans;
}
main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>a>>b>>p;
	if(b==0){
		if(p!=1)cout<<1;
		else cout<<0;
	}
	else cout<<qpow(a,b);
	return 0;
}

P1487 炸铁路（割边）

#include<bits/stdc++.h>
using namespace std;

int dfn[5050],low[5050];
int n,m,t;
int x,y,z;
vector<int> g[150];
int cut[150][150];
void tarjan(int u,int fa){
    t++;
    dfn[u]=low[u]=t;
    for(int i=0;i<g[u].size();i++){
        int v=g[u][i];
        if(v==fa) continue;
        if(dfn[v]==0){
            tarjan(v,u);
            low[u]=min(low[u],low[v]);
            if(dfn[u]<low[v]){
                cut[u][v]=1;
                cut[v][u]=1;
            }
        }
        else low[u]=min(low[u],dfn[v]);
    }
//  cout<<dfn[u]<<" "<<low[u]<<"\n";
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>x>>y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    for(int i=1;i<=n;i++){
        if(dfn[i]==0){
        	tarjan(i,i);
		}
    }
    for(int i=1;i<=n;i++){
    	for(int j=i+1;j<=n;j++){
    		if(cut[i][j]==1){
    			cout<<i<<" "<<j<<"\n";
			}
		}
	}
    return 0;
}

#include<bits/stdc++.h>
using namespace std;

int dfn[5050],low[5050];
int n,m,t;
int x,y,z;
vector<int> g[150];
int cut[150][150];
void dfs(int u,int fa){
    dfn[u]=low[u]=++t;
    for(int i=0;i<g[u].size();i++){
        int v=g[u][i];
        if(v==fa) continue;
        if(dfn[v]==0){
            dfs(v,u);
            low[u]=min(low[u],low[v]);
            if(dfn[u]<low[v]){
				cut[min(u,v)][max(u,v)]=1;
            }
        }
        else low[u]=min(low[u],dfn[v]);
    }
//  cout<<dfn[u]<<" "<<low[u]<<"\n";
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>x>>y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    for(int i=1;i<=n;i++){
        if(dfn[i]==0){
        	dfs(i,i);
		}
    }
    for(int i=1;i<=n;i++){
    	for(int j=i+1;j<=n;j++){
    		if(cut[i][j]==1){s
    			cout<<i<<" "<<j<<"\n";
			}
		}
	}
    return 0;
}

P1486 割点

#include<bits/stdc++.h>
using namespace std;
int shijianchuo;
int n,m;int cnt=0;
int dfn[100001],low[100001];
int h[100001];
vector<int> a[100001];
void tarjan(int u,int Root){
	low[u]=dfn[u]=++shijianchuo;
	int child=0;
	for(int i=0;i<a[u].size();i++){
		int v=a[u][i];
		if(!dfn[v]){
			child++;
			tarjan(v,Root);
			low[u]=min(low[u],low[v]);
			if(dfn[u]<=low[v]&&u!=Root) h[u]=1;
		}else{
			low[u]=min(low[u],dfn[v]);
		}
	}
	if(u==Root) if(child>1) h[u]=1;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int x,y;
		cin>>x>>y;
		a[x].push_back(y);
		a[y].push_back(x);
	}
	for(int i=1;i<=n;i++){
		tarjan(i,i);
	}
	for(int i=1;i<=n;i++){
		if(h[i]==1)cnt++;
	}
	cout<<cnt<<endl;
	for(int i=1;i<=n;i++){
		if(h[i]==1)cout<<i<<" ";
	}
	return 0;
}

信息

递交者** huangxihan LV 6 题目P1486 割点语言C++14递交时间7 个月前评测时间7 个月前**分数100总耗时126ms峰值内存7.3 MiB

受欢迎的奶牛缩点

#include<bits/stdc++.h>
using namespace std;
vector<int>a[1000001];
int b[1000001],c[1000001],d[1000001];
stack<int>st;
bool h[1000001];
int dfn[1000001],low[1000001],indx,times,v;
void dfs(int u){//suo
	dfn[u]=low[u]=++times;
	h[u]=1;st.push(u);
	for(int i=0;i<a[u].size();i++){
		v=a[u][i];
		if(!dfn[v]){
			dfs(v);
			low[u]=min(low[u],low[v]);
		}else if(h[v])low[u]=min(low[u],dfn[v]);
	}
	if(dfn[u]==low[u]){
		h[u]=0;c[u]=++indx;
		b[indx]=1;
		while(st.top()!=u){
			b[indx]++;
			c[st.top()]=indx;
			h[st.top()]=0;
			st.pop();
		}st.pop();
	}
}
int main(){
	memset(low,0x3f,sizeof(low));
	int n,m,u,v;cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>u>>v;
		a[u].push_back(v);
	}
	for(int i=1;i<=n;i++)
		if(!dfn[i])times=0,dfs(i);
	for(int i=1;i<=n;i++)
		for(int j=0;j<a[i].size();j++)
			if(c[i]!=c[a[i][j]])d[c[i]]++;
	int ans=0,cou=0;
	for(int i=1;i<=indx;i++)
		if(!d[i]){
			cou++;
			ans+=b[i];
		}
	if(cou==1)cout<<ans;
	else cout<<0;
	return 0;
}

最小生成树kruscal

#include<bits/stdc++.h>
using namespace std;
long long f[500005];
long long ans=0;
long long n,m,cnt;
struct node{
	long long u,v,w;
}a[500005];
bool cmp(node x,node y){
	return x.w<y.w;
}
long long get(long long x){
	if(f[x]==x)return x;
	f[x]=get(f[x]);
	return f[x];
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for(long long i=1;i<=n;i++){
		f[i]=i;
	}
	for(long long i=1;i<=m;i++){
		cin>>a[i].u>>a[i].v>>a[i].w;
	}
	sort(a+1,a+1+m,cmp);
	for(long long i=1;i<=m;i++){
		long long u=a[i].u;long long v=a[i].v;
		long long x=get(u);long long y=get(v);
		if(x!=y){
			f[x]=y;
			ans+=a[i].w;
			cnt++;
		}
	}
	cout<<ans;
	return 0;
}

最小生成树prim

#include <bits/stdc++.h>
#pragma GCC optimize(3)
using namespace std;
struct node{
	int v,w;
};
vector<node>a[500001];
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q;
bool h[500001];
int main(){
	int n,m;
	scanf("%d %d",&n,&m);
	for(int i=1;i<=m;i++){
		int u,v,w;
		scanf("%d %d %d",&u,&v,&w);
		a[u].push_back(node{v,w});
		a[v].push_back(node{u,w});
	}
	long long ans=0;
	int u=1;
	h[1]=1;
	for(int j=0;j<a[u].size();j++){
		q.push(make_pair(a[u][j].w,a[u][j].v));
	}
	for(int i=1;i<n;i++){
		while(h[q.top().second])q.pop();
		u=q.top().second;
		ans+=q.top().first;
		h[u]=1;
		q.pop();
		for(int j=0;j<a[u].size();j++){		
			q.push(make_pair(a[u][j].w,a[u][j].v));		
		}
	}
	printf("%lld\n",ans);
	return 0;
}

单元最短路dij

#include<bits/stdc++.h>
using namespace std;
#define PI pair<int,int>
struct node{
	int v,w;
};
vector<node>a[100001];
int dis[100001],h[1000001];
priority_queue<PI,vector<PI>,greater<PI> > q;
int main(){
	int n,m,s,u,v,w;
	cin>>n>>m>>s;
	for(int i=1;i<=m;i++){
		cin>>u>>v>>w;
		a[u].push_back(node{v,w});
	}
	memset(dis,0x3f,sizeof dis);
	dis[s]=0;
	q.push(make_pair(0,s));
	while(!q.empty()){
		u=q.top().second;w=q.top().first;
		q.pop();
		if(h[u]==1)continue;
		h[u]=1;
		for(int i=0;i<a[u].size();i++){
			v=a[u][i].v;
			w=a[u][i].w;
			if(dis[v]>dis[u]+w){
				dis[v]=dis[u]+w;
				q.push(make_pair(dis[v],v));
			}
		}
	}
	for(int i=1;i<=n;i++)cout<<dis[i]<<' ';
	return 0;
}

spfa 负权用

#include<bits/stdc++.h>
using namespace std;
int n,m,s;
struct node{
	int v,w;
};
int h[500005];
int u,v,w;
int d[500005];
int dis[200001];
vector<node>a[500005];
queue<int>q;
int main(){
	cin>>n>>m>>s;
	memset(dis,0x3f,sizeof dis);
	for(int i=1;i<=m;i++){
		cin>>u>>v>>w;
		
		a[u].push_back(node{v,w});
	}
	q.push(s);
	dis[s]=0;
	h[s]=1;
	d[s]++;
	while(!q.empty()){
		int u=q.front();q.pop();
		h[u]=0;
		for(int i=0;i<a[u].size();i++){
			int v=a[u][i].v;int w=a[u][i].w;
			if(dis[v]>dis[u]+w){
				dis[v]=dis[u]+w;
				if(h[v]==0){
					q.push(v);
					h[v]=1;
					d[v]++;
					if(d[v]==n){
						return 0;
					}
				}
			}
		}
	}
	for(int i=1;i<=n;i++){
		cout<<dis[i]<<' ';
	}
	return 0;
	
}

先序中序后序

#include<bits/stdc++.h>
using namespace std;
char ch;int L,R;
int l=0;
struct node{
	int Left,Right;
	char data;
};
node a[10001];
void dfsa(int Root){//xian xu
	if(Root==0)return ;
	cout<<a[Root].data;
	dfsa(a[Root].Left);
	dfsa(a[Root].Right);
}
void dfsb(int Root){//zhong xu
	if(Root==0)return ;
	dfsa(a[Root].Left);
	cout<<a[Root].data;
	dfsa(a[Root].Right);
}
void dfsc(int Root){//hou xu
	if(Root==0)return ;
	dfsa(a[Root].Left);
	dfsa(a[Root].Right);
	cout<<a[Root].data;
}

int main(){
	for(int i=1;;i++){
		cin>>ch>>L>>R;
		if(ch=='#'&&L==0&&R==0){
			break;
		}
		a[i].data=ch;a[i].Left=L;a[i].Right=R;
	}
	dfsa(1);
	cout<<"\n";
	dfsb(1);
	cout<<"\n";
	dfsc(1);
	return 0;
}

P1477 Johnson 全源最短路 spfa判 dij做

#include <bits/stdc++.h>
#define PI pair<int,int>
using namespace std;
struct node{
	int v,w;
};
vector<node>a[3002];
int dis[3002],h[3002],d[3002],cnt[3002];
priority_queue<PI,vector<PI>,greater<PI> >q;
queue<int>Q;
void dij(int s){
	memset(h,0,sizeof(h));
	memset(dis,0x3f,sizeof(dis));
	dis[s]=0;
	q.push(make_pair(0,s));
	while(q.size()){
		int u=q.top().second;
		q.pop();if(h[u])continue;h[u]=1;
		for(int i=0;i<a[u].size();i++){
			int v=a[u][i].v,w=a[u][i].w;
			if(dis[v]>dis[u]+w){
				dis[v]=dis[u]+w;
				q.push(make_pair(dis[v],v));
			}
		}
	}
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	int n,m,u,v,w;cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>u>>v>>w;
		a[u].push_back(node{v,w});
	}
	for(int i=1;i<=n;i++)
		a[n+1].push_back(node{i,0});
	memset(d,0x3f,sizeof(d));
	d[n+1]=0;Q.push(n+1);h[n+1]=1;cnt[n+1]++;
	while(Q.size()){
		u=Q.front();Q.pop();h[u]=0;
		for(int i=0;i<a[u].size();i++){
			v=a[u][i].v;w=a[u][i].w;
			if(d[v]>d[u]+w){
				d[v]=d[u]+w;
				if(!h[v]){
					Q.push(v);
					h[v]=1;
					if(++cnt[v]==n+1){
						cout<<"-1";
						return 0;
					}
				}
			}
		}
	}
	for(int i=1;i<=n;i++)
		for(int j=0;j<a[i].size();j++)
			a[i][j].w+=d[i]-d[a[i][j].v];
	for(int i=1;i<=n;i++){
		dij(i);
		long long s=0;
		for(int j=1;j<=n;j++){
			if(dis[j]!=dis[0])s+=1ll*j*(dis[j]-d[i]+d[j]);
			else s+=1ll*j*1000000000;
		}
		cout<<s<<"\n";
	}
	return 0;
}

[**P1359**  二叉树的先序遍历](http://czoj.com.cn/p/P1359)
[**P1360**  二叉树的中序遍历](http://czoj.com.cn/p/P1360)
[**P1357**  二叉树的后序遍历](http://czoj.com.cn/p/P1357)

通过的题目
P1

P2

P3

P4

P5

P6

P7

P8

P9

P10

P11

P12

P13

P14

P15

P16

P17

P18

P19

P20

P21

P22
P23

P24

P25

P26

P27

P28

P29

P30

P31

P32

P34

P35

P36

P37

P208

P237

P334

P357

P358

P359

P360

P361
P362

P363

P364

P365

P366

P367

P368

P369

P370

P371

P372

P373

P374

P376

P377

P382

P454

P465

P466

P468

P471

P473
P475

P478

P480

P484

P485

P487

P488

P489

P490

P491

P492

P494

P495

P500

P539

P575

P621

P638

P640

P718

P720

P733
最近活动

动态规划: 19
数据结构: 18
图论: 9
时间: 7
树: 7
图: 7
背包 DP: 7
来源: 6
2023: 3
算法基础: 3
tarjan: 3
2004: 2
USACO: 2
NOIP 提高组: 2
并查集: 2
图的存储: 2
最短路: 2
数学: 2
贪心: 2
钟楼区小学生选拔: 2

huangxihan

个人简介

信息

通过的题目

最近活动

题目标签

状态

支持

关于

huangxihan

个人简介

信息

通过的题目

最近活动

题目标签

状态

支持

关于

还没有账户？

登录