爵士OIer查看:6 回复:4 评论:6 创建时间:2020-06-03T22:19:59用户:爵士OIer查看:6 回复:4 评论:6 创建时间:2020-06-03T22:19:59
最小生成树
Prim：
#include<bits/stdc++.h>
using namespace std;
#define re register
#define il inline
il int read(){
re int x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
return x*f;
}//快读，不理解用cin代替即可
#define inf 123456789
#define maxn 5005
#define maxm 200005
struct edge{
int v,w,next;
}e[maxm<<1];
//注意是无向图，开两倍数组
int head[maxn],dis[maxn],cnt,n,m,tot,now=1,ans;
//已经加入最小生成树的的点到没有加入的点的最短距离，比如说1和2号节点已经加入了最小生成树，那么dis[3]就等于min(1->3,2->3)
bool vis[maxn];
//链式前向星加边
il void add(int u,int v,int w){
e[++cnt].v=v;
e[cnt].w=w;
e[cnt].next=head[u];
head[u]=cnt;
}
//读入数据
il void init(){
n=read(),m=read();
for(re int i=1,u,v,w;i<=m;++i)
{
u=read(),v=read(),w=read();
add(u,v,w),add(v,u,w);
}
}
il int prim(){
//先把dis数组附为极大值
for(re int i=2;i<=n;++i)dis[i]=inf;
//这里要注意重边，所以要用到min
for(re int i=head[1];i;i=e[i].next)dis[e[i].v]=min(dis[e[i].v],e[i].w);
while(++tot<n)//最小生成树边数等于点数-1
{
re int minn=inf;//把minn置为极大值
vis[now]=1;//标记点已经走过
//枚举每一个没有使用的点
//找出最小值作为新边
//注意这里不是枚举now点的所有连边，而是1~n
for(re int i=1;i<=n;++i)
{
if(!vis[i]&&minn>dis[i])
{
minn=dis[i];
now=i;
}
}
ans+=minn;
//枚举now的所有连边，更新dis数组
for(re int i=head[now];i;i=e[i].next)
{
re int v=e[i].v;
if(dis[v]>e[i].w&&!vis[v])dis[v]=e[i].w;
}
}
return ans;
}
int main(){
init();
printf("%d",prim());
return 0;
}
Kruskal：
#include<bits/stdc++.h>
using namespace std;
#define re register
#define il inline
il int read(){
re int x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
return x*f;
}
struct Edge{
int u,v,w;
}edge[200005];
int fa[5005],n,m,ans,eu,ev,cnt;
il bool cmp(Edge a,Edge b){
return a.w<b.w;
}
//喵的依据（按边权排序）
il int find(int x){
while(x!=fa[x]) x=fa[x]=fa[fa[x]];
return x;
}
//并查集循环实现模板，及路径压缩，不懂并查集的同学可以戳一戳代码上方的“并查集详解”
il void kruskal(){
sort(edge,edge+m,cmp);
//将边的权值排序
for(re int i=0;i<m;i++)
{
eu=find(edge[i].u), ev=find(edge[i].v);
if(eu==ev)continue;
//若出现两个点已经联通了，则说明这一条边不需要了
ans+=edge[i].w;
//将此边权计入答案
fa[ev]=eu;
//将eu、ev合并
if(++cnt==n-1)break;
//循环结束条件，及边数为点数减一时
}
}
int main(){
n=read(),m=read();
for(re int i=1;i<=n;i++)fa[i]=i;//初始化并查集
for(re int i=0;i<m;i++)edge[i].u=read(),edge[i].v=read(),edge[i].w=read();
kruskal();
printf("%d",ans);
return 0;
}
最短路
迪杰斯特拉
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define FRE() freopen("in.txt","r",stdin)
using namespace std;
typedef long long ll;
typedef pair<int,int> P;//first是距离，second是点的编号
const int maxn = 150;
int d[maxn];//数组d[i]表示从起点s到顶点 i 的最短距离
int n,m;
struct edge{
edge(int t,int c):to(t),cost(c){}
int to;//表示这条边的终点
int cost;//该边的权重
};
vector<edge> G[maxn];//储存以下标i为起点的边
priority_queue<P,vector<P>,greater<P> > que;//遍历d[]数组的下标，更新最小值
void init()
{
for(int i = 0; i < maxn; i++)
G[i].clear();
for(int i = 0; i < m; i++)
{
int st,en,c;
scanf("%d%d%d",&st,&en,&c);
G[st].push_back(edge(en,c));//这是个无向图注意储存的方式
G[en].push_back(edge(st,c));
}
}
int main(){
//FRE();
while(scanf("%d%d",&n,&m) && n+m)
{
init();
for(int i = 0; i < maxn; i++)
d[i]= INF;
d[1] = 0;//起点到起点本身的距离为0
que.push(P(0, 1));
while(!que.empty())
{
P p = que.top();
que.pop();
int v = p.second;
if(d[v] < p.first) continue;
for(int i = 0; i < G[v].size(); i++)
{
edge e = G[v][i];
if(d[e.to] > d[v] + e.cost)
{
d[e.to] = d[v] + e.cost;
que.push(P(d[e.to],e.to));
}
}
}
printf("%d\n",d[n]);
}
return 0;
}
Floyd
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
int map[1000][1000];
int main(){
int k,i,j,n,m;///n表示顶点个数，m表示边的条数
scanf("%d %d",&n,&m);
for(i=1; i<=n; i++)///初始化
{
for(j=1; j<=n; j++)
{
if(i==j)map[i][j]=0;
else map[i][j]=inf;
}
}
int a,b,c;
for(i=1; i<=m; i++)///有向图
{
scanf("%d %d %d",&a,&b,&c);
map[a][b]=c;
}
for(k=1; k<=n; k++)///典型三行代码
for(i=1; i<=n; i++)
for(j=1; j<=n; j++)
if(map[i][j]>map[i][k]+map[k][j] )
map[i][j]=map[i][k]+map[k][j];
for(i=1; i<=n; i++)///输出最终的结果,最终二维数组中存的即使两点之间的最短距离
{
for(j=1; j<=n; j++)printf("%10d",map[i][j]);
printf("\n");
}
return 0;
}
SPFA
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
int x=0,k=1; char c=getchar();
while(c<'0'||c>'9'){if(c=='-')k=-1;c=getchar();}
while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
return x*k;
}
#define maxn 10005
#define maxm 500005
#define inf 1234567890
int n,m,s,tot,dis[maxn],head[maxn];
bool vis[maxn];
struct Edge
{
int next,to,w;
}h[maxm];
void add(int u,int v,int w)
{
h[++tot].next=head[u];
h[tot].to=v;
h[tot].w=w;
head[u]=tot;
}
//上面和dijkstra算法基本上一样
queue<int> q;
//队列优化
inline void spfa()
{
for(int i=1; i<=n; i++)
{
dis[i]=inf;
//赋初值
}
int u,v;
q.push(s);
dis[s]=0;
//将起点的值负为0
vis[s]=1;//这句话可加可不加，因为循环的时候vis[s]又会被赋为0
while(!q.empty())
//当队列里没有元素的时候，那就已经更新了所有的单源最短路径
{
u=q.front();
//将队手节点记录并弹出队首节点
q.pop();
vis[u]=0;
for(int i=head[u];i;i=h[i].next)
//寻找与u相连的边
{
v=h[i].to;
if(dis[v]>dis[u]+h[i].w)
{
dis[v]=dis[u]+h[i].w;
//松弛操作，和floyd比较相似
if(!vis[v])
{
//已经在队列里的点就不用再进入了
vis[v]=1;
q.push(v);
}
}
}
}
}
int main(){
n=read(),m=read(),s=read();
for(int i=1,u,v,w;i<=m;i++)
{
u=read(),v=read(),w=read();
add(u,v,w);
}
spfa();
for(int i=1; i<=n; i++)
{
printf("%d ",dis[i]);
}
return 0;
}
负环
#include<bits/stdc++.h>
#define ri register int
struct Node{
int to,val,next;
}edge[6005];
int head[2005],cnt=1;
bool vis[2005];
int in[2005];//记录一个点被更新多少次
int dis[2005];
int n,m;
std::queue<int>q;
void add(int u,int v,int w)//链表存图
{
edge[cnt].to=v;
edge[cnt].next=head[u];
edge[cnt].val=w;
head[u]=cnt;
cnt++;
}
bool spfa(){
q.push(1);
vis[1]=true;
in[1]++;
dis[1]=0;
while(q.size())
{
int p=q.front();//取出队首元素
vis[p]=false;
q.pop();
for(ri i=head[p];i;i=edge[i].next) //极其板子的SPFA
{
int v=edge[i].to;
if(dis[v]>edge[i].val+dis[p])
{
dis[v]=edge[i].val+dis[p];
in[v]++;//更新次数++
if(in[v]>=n)return true;//如果一个点被更新超过N次，那么存在负环
if(!vis[v])
{
vis[v]=true;
q.push(v);
}
}
}
}
return false;//如果不存在负环，返回false;
}
int main(){
int t;
scanf("%d",&t);//t组数据
for(ri i=1;i<=t;i++)
{
std::memset(head,0,sizeof(head));
std::memset(edge,0,sizeof(edge));
std::memset(vis,0,sizeof(vis));
std::memset(in,0,sizeof(in));
std::memset(dis,0x3f,sizeof(dis)); //初始化
cnt=1;
scanf("%d%d",&n,&m);
for(ri i=1;i<=m;i++)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
add(u,v,w);
if(w>=0)add(v,u,w);//简单的存图操作
}
if(spfa())printf("YES\n");
else printf("NO\n");
}
return 0;
}
缩点
#include<bits/stdc++.h>
#define maxn 100001
#define maxm 500001
using namespace std;
struct node{
int to,next,from;
}edge[maxm];
queue <int> q;
vector <int> cb[maxn];
vector <int> rdr[maxn];
int ans[maxn],totq,x,y,v,rd[maxn],u,n,m,sum,vis[maxn],dis_[maxn],dis[maxn];
int dfn[maxn],low[maxn],f[maxn],times,cntqq;
int stack_[maxn],heads[maxm],visit[maxn],cnt,tot,index_;
void add(int x,int y) //建边
{
edge[++cntqq].next=heads[x];
edge[cntqq].from=x;
edge[cntqq].to=y;
heads[x]=cntqq;
return;
}
void tuopu() //拓扑排序
{
for(int i=1;i<=tot;i++) //初始化
{
if(rd[i]==0)
q.push(i); //入度为0的都进队列
}
while(!q.empty())
{
int u=q.front();
q.pop();
ans[++totq]=u;
for(int i=1;i<=cb[u].size();i++)
{
v=cb[u][i-1]; //因为vector是从0开始的，所以减1，下面代码的减1也一样
rd[v]--;
if(rd[v]==0)q.push(v);
}
}
}
void tarjan(int x) //tarjan求强连通分量
{
dfn[x]=low[x]=++times;
stack_[++index_]=x; //手写栈嘿嘿嘿
visit[x]=1;
for(int i=heads[x];i!=-1;i=edge[i].next)
{
if(!dfn[edge[i].to])
{
tarjan(edge[i].to);
low[x]=min(low[x],low[edge[i].to]);
}
else
if(visit[edge[i].to])
low[x]=min(low[x],dfn[edge[i].to]);
}
if(low[x]==dfn[x])
{
tot++;//强连通分量编号
while(1)
{
vis[stack_[index_]]=tot; //index_所在的强连通分量编号，等于前面讲的belong
dis_[tot]+=dis[stack_[index_]]; //强连通分量权值累加
visit[stack_[index_]]=0;index_--;
if(x==stack_[index_+1])break;//手写栈嘿嘿嘿
}
}
}
int main(){
memset(heads,-1,sizeof(heads));
int n,m,x,y;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&dis[i]);
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); //tarjan
for(int i=1;i<=cntqq;i++){ //拓扑建边
if(vis[edge[i].from]!=vis[edge[i].to])
{
x=vis[edge[i].from];y=vis[edge[i].to];
rd[y]++;cb[x].push_back(y);rdr[y].push_back(x);
}
}
tuopu();
for(int i=1;i<=tot;i++) //dp
{
int w=ans[i];
f[w]=dis_[w];
for(int j=1;j<=rdr[w].size();j++)
f[w]=max(f[w],f[rdr[w][j-1]]+dis_[w]);
}
for(int i=1;i<=tot;i++) //最后统计答案
sum=max(f[i],sum);
printf("%d",sum);
return 0;
}
差分约束系统
#include <bits/stdc++.h>
using namespace std;
const int N = 50005;
const int M = 50005;
struct edge {
int v, w, fail;
edge() {}
edge(int _v, int _w, int _fail) {
v = _v;
w = _w;
fail = _fail;
}
} e[M];
int head[N], len;
void init() {
memset(head, -1, sizeof(head));
len = 0;
}
void add(int u, int v, int w) {
e[len] = edge(v, w, head[u]);
head[u] = len++;
}
int n, m;
int dis[N], in[N];
bool vis[N];
bool spfa(int u) {
memset(vis, false, sizeof(vis));
vis[u] = true;
memset(dis, -1, sizeof(dis));
dis[u] = 0;
memset(in, 0, sizeof in);
in[u] = 1;
queue<int> q;
q.push(u);
while (!q.empty()) {
u = q.front();
q.pop();
vis[u] = false;
for (int j = head[u]; ~j; j = e[j].fail) {
int v = e[j].v;
int w = e[j].w;
if (dis[v] < dis[u] + w) {
dis[v] = dis[u] + w;
if (!vis[v]) {
q.push(v);
vis[v] = true;
++in[v];
if (in[v] > n + 1) return true;
}
}
}
}
return false;
}
int main() {
init();
int u, v, w, op;
cin >> n >> m;
while (m--) {
cin >> u >> v >> w;
add(u, v, -w);
}
for (int i = 1; i <= n; ++i) add(0, i, 0);
if (spfa(0)) cout << "NO" << endl;
else for (int i = 1; i <= n; ++i) cout << dis[i] << " ";
return 0;
}
强连通分量
（之前发了个帖子讲连通的留了这么张图，原代码找不到了）
欧拉回路
DFS
#include<bits/stdc++.h>
#define MAX 2010
using namespace std;
int maps[MAX][MAX];
int in[MAX];
int t[MAX];
int flag;
int k;
int Max,Min;
int DFS(int x){
int i;
for(i=Min;i<=Max;i++)
{
if(maps[x][i])///从任意一个与它相连的点出发
{
maps[x][i]--;///删去遍历完的边
maps[i][x]--;
DFS(i);
}
}
t[++k]=x;///记录路径，因为是递归所有倒着记
}
int main(){
int n,i,x,y;
Max=-9999;
Min=9999;
flag=0;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d%d",&x,&y);
maps[x][y]++;
maps[y][x]++;
Max=max(x,max(y,Max));
Min=min(x,min(y,Min));
in[x]++;
in[y]++;
}
for(i=Min;i<=Max;i++)
{
if(in[i]%2)///存在奇度点，说明是欧拉通路
{
flag=1;
DFS(i);
break;
}
}
if(!flag)///全为偶度点，从标号最小的开始找
{
DFS(Min);
}
for(i=k;i>=1;i--)
{
printf("%d\n",t[i]);
}
return 0;
}
佛罗来算法
#include<bits/stdc++.h>
using namespace std;
int ans[200];
int top;
int N,M;
int mp[200][200];
void dfs(int x){
int i;
top++;
ans[top]=x;
for (i=1; i<=N; i++)
{
if(mp[x][i]>0)
{
mp[x][i]=mp[i][x]=0;///删除此边
dfs(i);
break;
}
}
}
void fleury(int x){
int brige,i;
top=1;
ans[top]=x;///将起点放入Euler路径中
while(top>=0)
{
brige=0;
for (i=1; i<=N; i++) /// 试图搜索一条边不是割边（桥）
{
if(mp[ans[top]][i]>0)///存在一条可以扩展的边
{
brige=1;
break;
}
}
if (!brige)/// 如果没有点可以扩展，输出并出栈
{
printf("%d ", ans[top]);
top--;
}
else /// 否则继续搜索欧拉路径
{
top--;///为了回溯
dfs(ans[top+1]);
}
}
}
int main(){
int x,y,deg,num,start,i,j;
scanf("%d%d",&N,&M);
memset(mp,0,sizeof (mp));
for(i=1;i<=M; i++)
{
scanf("%d%d",&x,&y);
mp[x][y]=1;
mp[y][x]=1;
}
num=0;
start=1;///这里初始化为1
for(i=1; i<=N; i++)
{
deg=0;
for(j=1; j<=N; j++)deg+=mp[i][j];
if(deg%2==1)///奇度顶点
{
start=i;
num++;
}
}
if(num==0||num==2)fleury(start);
else puts("No Euler path");
return 0;
}
