讨论详情 - aoj

图论
板子
2024hanminghang LV 10 @ 2024-11-24 23:33:11

最短路dijkstra

//dijkstra 
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
const int maxm=5e5+10;
struct edge{
	int to,dis,nxt;
}e[maxm];
int dis[maxn],cnt,head[maxn];
bool vis[maxn];
int n,m,s,u,v,d;
struct node{
	int dis;
	int pos;
	bool operator<(const node &x)const{
		return x.dis<dis;
	}
};
priority_queue<node> q;

void add1(int u,int v,int d){
	e[++cnt].dis=d;
	e[cnt].to=v;
	e[cnt].nxt=head[u];
	head[u]=cnt;
}

void dijkstra(){
	dis[s]=0;
	q.push((node){0,s});
	while(!q.empty()){
		node tmp=q.top();
		q.pop();
		int x=tmp.pos,d=tmp.dis;
		if(vis[x]) continue;
		vis[x]=1;
		for(int i=head[x];i;i=e[i].nxt){
			int y=e[i].to;
			if(dis[y]>dis[x]+e[i].dis){
				dis[y]=dis[x]+e[i].dis;
				if(!vis[y]) q.push((node){dis[y],y});
			}
		}
	}
}

int main(){
	scanf("%d%d%d",&n,&m,&s);
	memset(dis,0x7f,sizeof(dis));
	for(int i=0;i<m;i++){
		scanf("%d%d%d",&u,&v,&d);
		add1(u,v,d);
	}
	dijkstra();
	for(int i=1;i<=n;i++) printf("%d ",dis[i]);
	return 0;
}

最短路floyd

//floyd 
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,u,v,w,x,y,q;
int mp[105][105];
signed main(){
	scanf("%lld%lld",&n,&m,&q);
	memset(mp,0x3f,sizeof(mp));
	for(int i=1;i<=n;i++){
		scanf("%lld%lld%lld",&u,&v,&w);
		mp[u][v]=w;
	}
	for(int k=1;k<=n;k++){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				mp[i][j]=min(mp[i][j],mp[i][k]+mp[k][j]);
			}
		}
	}
	while(q--){
		scanf("%lld%lld",&x,&y);
		printf("%lld",mp[x][y]);
	}
	return 0;
}

最短路SPFA

//SPFA 
#include<bits/stdc++.h>
using namespace std;
const long long inf=2147483647;
const int maxn=10005;
const int maxm=500005;
int n,m,s,tot,u,v,w;
int dis[maxn],vis[maxn],head[maxm];
struct edge{
	int net,to,dis;
}e[maxm];

inline void add(int u,int v,int w){
	e[++tot].to=v;
	e[tot].dis=w;
	e[tot].net=head[u];
	head[u]=tot;
}

void spfa(){
	queue<int> q;
	for(int i=1;i<=n;i++){
		dis[i]=inf;
		vis[i]=0;
	}
	q.push(s);
	dis[s]=0;vis[s]=1;
	while(!q.empty()){
		int x=q.front();
		q.pop();
		vis[x]=0;
		for(int i=head[x];i;i=e[i].net){
			int v=e[i].to;
			if(dis[v]>dis[x]+e[i].dis){
				dis[v]=dis[x]+e[i].dis;
				if(vis[v]==0){
					vis[v]=1;
					q.push(v);
				}
			}
		}
	}
}

int main(){
	scanf("%d%d%d",&n,&m,&s);
	for(int i=1;i<m;i++){
		scanf("%d%d%d",&u,&v,&w);
		add(u,v,w);
	}
	spfa();
	for(int i=1;i<=n;i++){
		if(s==i) printf("0 ");
		else printf("%d ",dis[i]);
	}
	return 0;
}

最小生成树kruskal

//kruskal 
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int n,m,ans;
int fa[maxn];
struct node{
	int x,y,w;
}e[maxn];

void Init(){
	for(int i=1;i<=maxn;i++) fa[i]=i;
}

int getf(int x){
	if(fa[x]==x) return x;
	return fa[x]=getf(fa[x]);
}

bool merge(int x,int y){
	x=getf(x);
	y=getf(y);
	if(x!=y){
		fa[x]=y;
		return true;
	}
	return false;
}

bool cmp(node e1,node e2){
	return e1.w<e2.w;
}

int kruskal(){
	sort(e,e+m,cmp);
	Init();
	int sum=0;
	for(int i=0;i<m;i++){
		if(merge(e[i].x,e[i].y)) sum+=e[i].w;
	}
	return sum;
}

int main(){
	scanf("%d%d",&n,&m);
	for(int i=0;i<m;i++) cin>>e[i].x>>e[i].y>>e[i].w;
	ans=kruskal();
	printf("%d",ans);
	return 0;
}

最小生成树prim

//prim最小生成树 
#include<bits/stdc++.h>
using namespace std;
int a[3010][3010],d[3010],n,m,ans;
bool v[3010];
int x,y,z;

void prim(){
	memset(d,0x3f,sizeof(d));
	memset(v,0,sizeof(v));
	d[1]=0;
	for(int i=1;i<n;i++){
		int x=0;
		for(int j=1;j<=n;j++){
			if(!v[j]&&(x==0||d[j]<d[x])) x=j;
		}
		v[x]=1;
		for(int y=1;y<=n;y++){
			if(!v[y]) d[y]=min(d[y],a[x][y]);
		}
	}
}

int main(){
	scanf("%d%d",&n,&m);
	memset(a,0x3f,sizeof(a));
	for(int i=1;i<=n;i++) a[i][i]=0;
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&x,&y,&z);
		a[x][y]=a[y][x]=min(a[x][y],z);
	}
	prim();
	for(int i=2;i<=n;i++){
		ans+=d[i];
	}
	printf("%d",ans);
	return 0;
}

tarjan边双连通分量

//tarjan边双 
#include<bits/stdc++.h>
using namespace std;
const int maxn=5e5+10;
const int maxm=2e6+10;
struct edge{
	int nxt,to;
}e[maxm];
int head[maxn],tot=1,num;
int dfn[maxn],low[maxn];
int bridge[maxm];
int n,m,x,y;
int c[maxn],dcc;
vector<int> ans[maxn];
void add(int x,int y){
	e[++tot].nxt=head[x];
	e[tot].to=y;
	head[x]=tot;
}

void tarjan(int x,int p){
	dfn[x]=low[x]=++num;
	for(int i=head[x];i;i=e[i].nxt){
		int y=e[i].to;
		if(!dfn[y]){
			tarjan(y,i);
			low[x]=min(low[x],low[y]);
			if(low[y]>dfn[x]){
				bridge[i]=bridge[i^1]=1;
			}
		}else if(i!=(p^1)) low[x]=min(low[x],dfn[y]);
	} 
}

void dfs(int x){
	c[x]=dcc;
	if(x) ans[dcc].push_back(x);
	for(int i=head[x];i;i=e[i].nxt){
		int y=e[i].to;
		if(c[y]||bridge[i]) continue;
		dfs(y);
	}
}

int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		scanf("%d%d",&x,&y);
		add(x,y);
		add(y,x);
	}
	for(int i=1;i<=n;i++){
		if(!dfn[i]) tarjan(i,0);
	}
	for(int i=1;i<=n;i++){
		if(!c[i]){
			++dcc;
			dfs(i);
		}
	}
	printf("%d\n",dcc);
	for(int i=1;i<=dcc;i++){
		printf("%d ",ans[i].size());
		for(int j=0;j<ans[i].size();j++){
			printf("%d ",ans[i][j]);
		}
		printf("\n");
	}
	return 0;
}

tarjan边双缩点

//tarjan边双缩点 
#include<bits/stdc++.h>
using namespace std;
const int maxn=5e5+10;
const int maxm=2e6+10;
struct edge{
	int nxt,to;
}e[maxm],ec[maxm];
int head[maxn],hc[maxn],tc=1,tot=1,num;
int dfn[maxn],low[maxn];
int bridge[maxm];
int n,m,x,y;
int c[maxn],dcc;
vector<int> ans[maxn];
 
void add(int x,int y){
	e[++tot].nxt=head[x];
	e[tot].to=y;
	head[x]=tot;
}

void addc(int x,int y){
	ec[++tc].nxt=hc[x];
	ec[tc].to=y;
	hc[x]=tc;
}

void tarjan(int x,int p){
	dfn[x]=low[x]=++num;
	for(int i=head[x];i;i=e[i].nxt){
		int y=e[i].to;
		if(!dfn[y]){
			tarjan(y,i);
			low[x]=min(low[x],low[y]);
			if(low[y]>dfn[x]){
				bridge[i]=bridge[i^1]=1;
			}
		}else if(i!=(p^1)) low[x]=min(low[x],dfn[y]);
	} 
}

void dfs(int x){
	c[x]=dcc;
	if(x) ans[dcc].push_back(x);
	for(int i=head[x];i;i=e[i].nxt){
		int y=e[i].to;
		if(c[y]||bridge[i]) continue;
		dfs(y);
	}
}

int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		scanf("%d%d",&x,&y);
		add(x,y);
		add(y,x);
	}
	for(int i=1;i<=n;i++){
		if(!dfn[i]) tarjan(i,0);
	}
	for(int i=1;i<=n;i++){
		if(!c[i]){
			++dcc;
			dfs(i);
		}
	}
	for(int i=2;i<=tot;i++){
		int x=e[i^1].to,y=e[i].to;
		if(c[x]==c[y]) continue;
		addc(c[x],c[y]);
	}//图存在ec里面 
	return 0;
}

tarjan割边

//tarjan割边 
#include<bits/stdc++.h>
using namespace std;
const int maxn=5e5+10;
const int maxm=2e6+10;
struct edge{
	int nxt,to;
}e[maxm];
int head[maxn],tot=1,num;
int dfn[maxn],low[maxn];
int bridge[maxm];
int n,m,x,y;
void add(int x,int y){
	e[++tot].nxt=head[x];
	e[tot].to=y;
	head[x]=tot;
}

void tarjan(int x,int p){
	dfn[x]=low[x]=++num;
	for(int i=head[x];i;i=e[i].nxt){
		int y=e[i].to;
		if(!dfn[y]){
			tarjan(y,i);
			low[x]=min(low[x],low[y]);
			if(low[y]>dfn[x]){
				bridge[i]=bridge[i^1]=1;
			}
		}else if(i!=(p^1)) low[x]=min(low[x],dfn[y]);
	} 
}

int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		scanf("%d%d",&x,&y);
		add(x,y);
		add(y,x);
	}
	for(int i=1;i<=n;i++){
		if(!dfn[i]) tarjan(i,0);
	}
	for(int i=2;i<tot;i+=2){
		if(bridge[i]) printf("%d %d\n",e[i^1].to,e[i].to);
	}
	return 0;
}

tarjan割点

//tarjan割点 
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+5;
const int maxm=1e6+5;
struct edge{
	int nxt,to;
}e[maxm];
int head[maxn],tot=1;
int dfn[maxn],low[maxn],cut[maxn],num;
int n,m,x,y,ans,root;

void add(int x,int y){
	e[++tot].nxt=head[x];
	e[tot].to=y;
	head[x]=tot;
}

void tarjan(int x){
	int flag=0;
	dfn[x]=low[x]=++num;
	for(int i=head[x];i;i=e[i].nxt){
		int y=e[i].to;
		if(!dfn[y]){
			tarjan(y);
			low[x]=min(low[y],low[x]);
			if(low[y]>=dfn[x]){
				flag++;
				if(x!=root||flag>1) cut[x]=1;
			} 
		}
		else low[x]=min(low[x],dfn[y]);
	}
}

int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		scanf("%d%d",&x,&y);
		if(x==y) continue;
		add(x,y);
		add(y,x);
	}
	for(int i=1;i<=n;i++){
		if(!dfn[i]) root=i,tarjan(i);
	}
	for(int i=1;i<=n;i++) ans+=cut[i];
	printf("%d\n",ans);
	for(int i=1;i<=n;i++) if(cut[i]) printf("%d ",i);
	return 0;
}

tarjan点双连通分量

//tarjan点双 
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e6+5;
const int maxm=3e6+5;
struct edge{
	int nxt,to;
}e[maxm];
int head[maxn],tot=1;
int dfn[maxn],low[maxn],cut[maxn],num;
int n,m,x,y,ans,root;
int st[maxn],cnt,top;
vector<int> dcc[maxn];

void add(int x,int y){
	e[++tot].nxt=head[x];
	e[tot].to=y;
	head[x]=tot;
}

void tarjan(int x){
	int flag=0;
	st[++top]=x;
	dfn[x]=low[x]=++num;
	if(x==root&&head[x]==0){
		dcc[++cnt].push_back(x);
		return;
	}
	for(int i=head[x];i;i=e[i].nxt){
		int y=e[i].to;
		if(!dfn[y]){
			tarjan(y);
			low[x]=min(low[y],low[x]);
			if(low[y]>=dfn[x]){
				flag++;
				if(x!=root||flag>1) cut[x]=1;
				cnt++;
				int z;
				do{
					z=st[top--];
					dcc[cnt].push_back(z);
				}while(z!=y);
				dcc[cnt].push_back(x);
			} 
		}
		else low[x]=min(low[x],dfn[y]);
	}
}

int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		scanf("%d%d",&x,&y);
		if(x==y) continue;
		add(x,y);
		add(y,x);
	}
	for(int i=1;i<=n;i++){
		if(!dfn[i]) root=i,tarjan(i);
	}
	printf("%d\n",cnt);
	for(int i=1;i<=cnt;i++){
		printf("%d ",dcc[i].size());
		for(int j=0;j<dcc[i].size();j++){
			printf("%d ",dcc[i][j]);
		}
		printf("\n");
	}
	return 0;
}

tarjan有向图强连通分量

//tarjan强连通分量 
#include<bits/stdc++.h>
using namespace std;
const int maxm=1e6+5;
const int maxn=1e5+5;
struct edge{
	int to,nxt;
}e[maxm];
int head[maxn],dfn[maxn],low[maxn];
int st[maxn],ins[maxn],c[maxn];
vector<int> scc[maxn];
int n,m,tot,num,top,cnt,x,y;
void add(int x,int y){
	e[++tot].to=y;
	e[tot].nxt=head[x];
	head[x]=tot;
}

void tarjan(int x){
	dfn[x]=low[x]=++num;
	st[++top]=x,ins[x]=1;
	for(int i=head[x];i;i=e[i].nxt){
		int y=e[i].to;
		if(!dfn[y]){
			tarjan(y);
			low[x]=min(low[x],low[y]);
		}else if(ins[y]){
			low[x]=min(low[x],dfn[y]);
		}
	}
	if(dfn[x]==low[x]){
		cnt++;
		int z;
		do{
			z=st[top--];
			ins[z]=0;
			c[z]=cnt;
			scc[cnt].push_back(z);
		}while(x!=z);
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		scanf("%d%d",&x,&y);
		add(x,y);
	}
	for(int i=1;i<=n;i++){
		if(!dfn[i]) tarjan(i);
	}
	printf("%d\n",cnt);
	for(int i=1;i<=cnt;i++){
		for(int j=0;j<scc[i].size();j++){
			printf("%d ",scc[i][j]);
		}
		putchar('\n');
	}
	return 0;
}

tarjan有向图强连通分量缩点

//tarjan有向图缩点 
#include<bits/stdc++.h>
using namespace std;
const int maxm=1e6+5;
const int maxn=1e5+5;
struct edge{
	int to,nxt;
}e[maxm],ec[maxm];
int head[maxn],dfn[maxn],low[maxn];
int st[maxn],ins[maxn],c[maxn];
vector<int> scc[maxn];
int n,m,tot,num,top,cnt,x,y;
int hc[maxn],tc;
void add(int x,int y){
	ec[++tc].to=y;
	ec[tc].nxt=head[x];
	head[x]=tc;
}

void addc(int x,int y){
	ec[++tot].to=y;
	ec[tot].nxt=hc[x];
	hc[x]=tot;
}

void tarjan(int x){
	dfn[x]=low[x]=++num;
	st[++top]=x,ins[x]=1;
	for(int i=head[x];i;i=e[i].nxt){
		int y=e[i].to;
		if(!dfn[y]){
			tarjan(y);
			low[x]=min(low[x],low[y]);
		}else if(ins[y]){
			low[x]=min(low[x],dfn[y]);
		}
	}
	if(dfn[x]==low[x]){
		cnt++;
		int z;
		do{
			z=st[top--];
			ins[z]=0;
			c[z]=cnt;
			scc[cnt].push_back(z);
		}while(x!=z);
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		scanf("%d%d",&x,&y);
		add(x,y);
	}
	for(int i=1;i<=n;i++){
		if(!dfn[i]) tarjan(i);
	}
	for(int x=1;x<=n;x++){
		for(int i=head[x];i;i=e[i].nxt){
			int y=e[i].to;
			if(c[x]==c[y]) continue;
			addc(c[x],c[y]);
		}
	}//ec为新图的邻接表 
	return 0;
}

网络流Dinic

//网络流Dinic 
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int inf=2147480000;
const int maxn=520010;
int n,m,s,t,u,v;
int w,ans,dis[maxn];
int tot=1,now[maxn],head[maxn];
struct node{
	int to,net,val;
}e[maxn];

inline void add(int u,int v,int w){
	e[++tot].to=v;
	e[tot].val=w;
	e[tot].net=head[u];
	head[u]=tot;
	e[++tot].to=u;
	e[tot].val=0;
	e[tot].net=head[v];
	head[v]=tot;
}

int bfs(){
	for(int i=1;i<=n;i++) dis[i]=inf;
	queue<int> q;
	q.push(s);
	dis[s]=0;
	now[s]=head[s];
	while(!q.empty()){
		int x=q.front();
		q.pop();
		for(int i=head[x];i;i=e[i].net){
			int v=e[i].to;
			if(e[i].val>0 && dis[v]==inf){
				q.push(v);
				now[v]=head[v];
				dis[v]=dis[x]+1;
				if(v==t) return 1;
			}
		}
	} 
	return 0;
}

int dfs(int x,int sum){
	if(x==t) return sum;
	int k,res=0;
	for(int i=now[x];i && sum;i=e[i].net){
		now[x]=i;
		int v=e[i].to;
		if(e[i].val>0 && (dis[v]==dis[x]+1)){
			k=dfs(v,min(sum,e[i].val));
			if(k==0) dis[v]=inf;
			e[i].val-=k;
			e[i^1].val+=k;
			res+=k;
			sum-=k;
		}
	}
	return res;
}

signed main(){
	scanf("%lld%lld",&n,&m,&s,&t);
	for(int i=1;i<=m;i++){
		scanf("%lld%lld%lld",&u,&v,&w);
		add(u,v,w);
	}
	while(bfs()){
		ans+=dfs(s,inf);
	}
	printf("%lld",ans);
	return 0;
}

最小费用最大流

#include<bits/stdc++.h>
using namespace std;
const int maxn=100010;
bool vis[maxn];
int n,m,s,t;
int x,y,z,f;
int dis[maxn],pre[maxn];
int last[maxn],flow[maxn],maxflow,mincost;
struct edge{
	int to,net,val,dis;
}e[maxn];
int head[maxn],tot=-1;
queue<int> q;

inline void add(int u,int v,int w,int dis){
	e[++tot].net=head[u];
	e[tot].to=v;
	e[tot].val=w;
	e[tot].dis=dis;
	head[u]=tot;
}

bool spfa(int s,int t){
	memset(dis,0x7f,sizeof(dis));
	memset(flow,0x7f,sizeof(flow));
	memset(vis,0,sizeof(vis));
	q.push(s);
	vis[s]=1;
	dis[s]=0;
	pre[t]=-1;
	while(!q.empty()){
		int now=q.front();
		q.pop();
		vis[now]=0;
		for(int i=head[now];i!=-1;i=e[i].net){
			if(e[i].val>0 && dis[e[i].to]>dis[now]+e[i].dis){
				dis[e[i].to]=dis[now]+e[i].dis;
				pre[e[i].to]=now;
				last[e[i].to]=i;
				flow[e[i].to]=min(flow[now],e[i].val);
				if(!vis[e[i].to]){
					vis[e[i].to]=1;
					q.push(e[i].to); 
				}
			}
		}
	}
	return pre[t]!=-1;
}

void MCMF(){
	while(spfa(s,t)){
		int now=t;
		maxflow+=flow[t];
		mincost+=flow[t]*dis[t];
		while(now!=s){
			e[last[now]].val-=flow[t];
			e[last[now] ^ 1].val+=flow[t];
			now=pre[now];
		}
	}
}

int main(){
	memset(head,-1,sizeof(head));
	scanf("%d%d%d%d",&n,&m,&s,&t);
	for(int i=1;i<=m;i++){
		scanf("%d%d%d%d",&x,&y,&z,&f);
		add(x,y,z,f);
		add(y,x,0,-f);
	}
	MCMF();
	printf("%d %d",maxflow,mincost);
	return 0;
}

目前还没有评论...

板子

0 条评论

状态

开发

支持

板子

0 条评论

状态

开发

支持

登录