ttyclear's blog

Think twice,Code once.

ttyclear的板子

发布于 2020-09-26 | 9分钟 | 1412字数

数据结构

并查集

#include <bits/stdc++.h>
#define endl '\n'
#define fast ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define ll long long
#define ull unsigned long long
using namespace std;
const int N=1e5+5;
const int M=2*1e5+5;
const ll inf=0x7fffffff;  //2147483647
const int mod=1e9+7;
const int fx[5]={0,-1,0,1,0};
const int fy[5]={0,0,-1,0,1};
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while (ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while (ch>='0' && ch<='9'){x=(x<<3)+(x<<1);x+=(ch-'0');ch=getchar();}
    return x*f;
}

void write(int x)
{
    if (x<0) putchar('-'),x=-x;
    if (x>10) write(x/10);
    putchar(x%10+'0');
}

int n,m,f[N];
int find(int x){return f[x] == x ? x : f[x] = find(f[x]);
}
int main()
{
	cin>>n>>m;
	for (int i = 1;i <= n;i++)
	   f[i] = i;
	for (int i = 1;i <= m;i++)
	{
		int z,x,y;
		cin>>z>>x>>y;
		if (z==1)
		   f[find(x)]=find(y);  //将能找到最早的祖先节点合并
		else if (find(x)==find(y))
		   cout<<"Y\n";
		else
		   cout<<"N\n";
	}
	return 0;
}

图论

O((m+n)⋅logn)O((m+n)·logn)堆优化Dijkstra

#include <bits/stdc++.h>
#define endl '\n'
#define fast ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define ll long long
#define ull unsigned long long
using namespace std;
const int N=1e5+5;
const int M=2*1e5+5;
const ll inf=0x7fffffff;  //2147483647
const int mod=1e9+7;
const int fx[5]={0,-1,0,1,0};
const int fy[5]={0,0,-1,0,1};
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while (ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while (ch>='0' && ch<='9'){x=(x<<3)+(x<<1);x+=(ch-'0');ch=getchar();}
    return x*f;
}

void write(int x)
{
    if (x<0) putchar('-'),x=-x;
    if (x>10) write(x/10);
    putchar(x%10+'0');
}

int n, m, s, tot;
ll Next[M], edge[M], ver[M], head[N], dis[N], path[N];
bool vis[N];

void add_edge(int x, int y, int z)  //start, end, value
{
  ver[++tot] = y;
  edge[tot] = z;
  Next[tot] = head[x];
  head[x] = tot;
}

struct node
{
  ll dis;
  int id;
  bool operator<(const node&tty)const{return tty.dis < dis;}
};
priority_queue<node>q;

void dijkstra(int s)
{
  memset(dis, 0x3f, sizeof(dis));
  dis[s] = 0;
  q.push(node{0, s});
  while (q.size())
  {
    int x = q.top().id;
    q.pop();
    if (vis[x])   
      continue;
    vis[x] = 1;
    for (int i = head[x];i;i = Next[i])
    {
      int y = ver[i],z = edge[i];
      if (dis[y] > dis[x] + z)
      {
        dis[y] = dis[x] + z;
        path[y] = x;
        q.push(node{dis[y], y});
      }
    }
  }
}

void print_path(int start, int end)
{
  string string_of_path;
  for (int i = end;i;i = path[i])
    string_of_path = to_string(i) + ' ' + string_of_path;
  cout<<string_of_path<<endl;
}

int main()
{
  cin>>n>>m>>s;
  for (int i = 1;i <= m;i++)
  {
    int x,y,z;
    cin>>x>>y>>z;
    add_edge(x, y, z);
  }
  dijkstra(s);
  for (int i=1;i<=n;i++)
     cout<<dis[i]<<' ';
  system("pause");
  return 0;
}

O(km)O(km)的SPFA（k为常数）

#include <bits/stdc++.h>
#define endl '\n'
#define fast ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define ll long long
#define ull unsigned long long
using namespace std;
const int N=1e5+5;
const int M=2*1e5+5;
const ll inf=0x7fffffff;  //2147483647
const int mod=1e9+7;
const int fx[5]={0,-1,0,1,0};
const int fy[5]={0,0,-1,0,1};
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while (ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while (ch>='0' && ch<='9'){x=(x<<3)+(x<<1);x+=(ch-'0');ch=getchar();}
    return x*f;
}

void write(int x)
{
    if (x<0) putchar('-'),x=-x;
    if (x>10) write(x/10);
    putchar(x%10+'0');
}

int n, m, s, tot;
ll Next[M], edge[M], ver[M], head[N], dis[N], path[N];
bool vis[N];
queue<int>q;

void add_edge(int x, int y, int z)  //start, end, value
{
  ver[++tot] = y;
  edge[tot] = z;
  Next[tot] = head[x];
  head[x] = tot;
}

void spfa(int s)
{
  dis[s] = 0, vis[s] = 1;
  q.push(s);
  while (!q.empty())
  {
    int x = q.front();
    q.pop();
    vis[x] = 0;
    for (int i = head[x];i;i = Next[i])
    {
      int y = ver[i],z = edge[i];  //from node x to node y with value z
      if (dis[y] > dis[x] + z)  //relax
      {
        dis[y] = dis[x] + z;
        if (!vis[y])
        {
          q.push(y);
          vis[y] = 1;
          path[y] = x;  //the way to y goes from x
        }
      }
    }
  }
}

void print_path(int start, int end)  //start node1 node2 ... end
{
  string string_of_path;
  for (int i = end;i;i = path[i])
    string_of_path = to_string(i) + ' ' + string_of_path;  //reverse
  cout<<string_of_path<<endl;
}

int main()
{
  cin>>n>>m>>s;
  for (int i = 1;i <= m;i++)
  {
    int x,y,z;
    cin>>x>>y>>z;
    add_edge(x, y, z);
    // add_edge(y, x, z); 对于无向图记得双向加边
  }
  for (int i = 1;i <= n;i++)   dis[i] = inf;
  spfa(s);
  for (int i = 1;i <= n;i++)
    cout<<dis[i]<<' ';
  system("pause");
  return 0;
}

(PS:之前一直忘了memset是对字节赋值，写出了"memset(dis,inf,sizeof(dis))"的惊人代码，死活调不对QAQ)

O(ElogE)O(ElogE)并查集实现kruskal

#include <bits/stdc++.h>
#define endl '\n'
#define fast ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define ll long long
#define ull unsigned long long
using namespace std;
const int N=1e5+5;
const int M=2*1e5+5;
const ll inf=0x7fffffff;  //2147483647
const int mod=1e9+7;
const int fx[5]={0,-1,0,1,0};
const int fy[5]={0,0,-1,0,1};
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while (ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while (ch>='0' && ch<='9'){x=(x<<3)+(x<<1);x+=(ch-'0');ch=getchar();}
    return x*f;
}

void write(int x)
{
    if (x<0) putchar('-'),x=-x;
    if (x>10) write(x/10);
    putchar(x%10+'0');
}

int n, m, f[N], ans, cnt;
struct Edge
{
	int x,y,z;
}edge[M];
bool cmp(Edge a, Edge b){return a.z < b.z;}
int find(int x){return f[x] == x ? x : f[x]=find(f[x]);}
int main()
{
	cin>>n>>m;
	for (int i = 1; i <= n;i++)   f[i] = i;
	for (int i = 1;i <= m;i++)
	{
		cin>>edge[i].x>>edge[i].y>>edge[i].z;
	}
	sort(edge+1, edge+m+1, cmp);
	for (int i = 1;i <= m;i++)
	{
		if (find(edge[i].x) ^ find(edge[i].y))  //两点不在同一路径上（同一个并查集里）
		{
			ans += edge[i].z;
			f[find(edge[i].x)] = find(edge[i].y);
			cnt++;
		}
		if (cnt == n-1)
		   break;
	}
	if (ans)
	   cout<<ans<<endl;
	else
	   cout<<"orz\n";
	system("pause");
	return 0;
}

不定期更新

部分初赛数学知识点整理 上一篇
关于 下一篇
0%