zxq0408

196

YuYuYuZ

zxq0408
11天前
//0x3f代表无限大
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 510;
int n, m;
int g[N][N];  //稠密图，用邻接矩阵
int dist[N];  //用于记录每一个点距离第一个点的距离
bool st[N];  //记录每个点的最短距离是否已经确定

int D_()
{
memset(dist, 0x3f, sizeof(dist));
dist[1] = 0;

for(int i = 0; i < n; i ++)    //有n个点，所以要进行n次迭代
{
int t = -1;  //t存储当前访问的点

for(int j = 1; j <= n; j ++)
{
if(!st[j] && (t == -1 || dist[t] > dist[j]))
t = j;
}

for(int j = 1; j <= n; j ++)   //依次更新每个点所到相邻的点路径值
dist[j] = min(dist[j], dist[t] + g[t][j]);
st[t] = true;
}
if(dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}

int main()
{
cin >> n >> m;
memset(g, 0x3f, sizeof(g));
while(m--)
{
int x, y, z;
cin >> x >> y >> z;
g[x][y] = min(g[x][y], z);   //如果发生重边的情况则保留最短的一条边
}
cout << D_() <<endl;
return 0;
}


zxq0408
11天前
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;

typedef pair<int, int> PII;
const int N = 1e6 + 10;

int n, m;
int h[N], e[N], ne[N], idx;
int w[N];   //存放边的权重
int dist[N];
bool st[N];

void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

int D_()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
priority_queue<PII, vector<PII>, greater<PII>> heap;
heap.push({0,1});    //*****first存储距离，second存储节点编号*****

while(heap.size())
{
auto t = heap.top();
heap.pop();
int ver = t.second, distance = t.first;

if(st[ver]) continue;
st[ver] = true;

for(int i =h[ver]; i != -1; i = ne[i])  //***************
{
int j = e[i];
if(dist[j] > distance + w[i])
{
dist[j] = distance + w[i];
heap.push({dist[j], j});
}
}
}
if(dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}

int main()
{
cin >> n >> m;
memset(h, -1, sizeof h);
while(m--)
{
int x, y, z;
cin >> x >> y >>z;
}
cout << D_() << endl;
return 0;
}


zxq0408
11天前
//void *memcpy(void *destin, void *source, unsigned n);
//以source指向的地址为起点，将连续的n个字节数据，复制到以destin指向的地址为起点的内存中。
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 510, M = 10010;

struct Edge
{
int a, b, c;
}edges[M];   //把每个边储存下来

int n, m, k;
int dist[N];
int last[N];  //每次进入第2重循环的dist数组的备份

void bellman_ford()
{
memset(dist, 0x3f, sizeof dist);

dist[1] = 0;
for(int i = 0; i < k; i ++)
{
memcpy(last, dist, sizeof dist);//************

for(int j = 0; j < m; j++)
{
auto e = edges[j];
dist[e.b] = min(dist[e.b], last[e.a] + e.c); //这句容易错，理解使用dist还是last
}
}
}

int main ()
{
cin >> n >> m >> k;
for(int i = 0; i < m; i ++)
{
int x, y , z;
cin >> x >> y >>z;
edges[i] = {x, y, z};
}
bellman_ford();
if(dist[n] > (0x3f3f3f3f)/2)  cout << "impossible" <<endl;
else cout << dist[n] << endl;
return 0;
}


zxq0408
11天前

### 算法思路

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 100010;
int n, m;
int e[N], ne[N], h[N], idx;
int q[N];
int d[N];  //d[i]存储点i的入度

{
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

//判断是否有拓扑排序
bool topsort()
{
int hh = 0, tt = -1;
for(int i = 1; i <= n; i ++)
if(!d[i])
q[++ tt] = i;

while(hh <= tt)
{
int t = q[hh ++];

for(int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
if(--d[j] == 0)
q[++ tt] = j;
}
}
//如果所有点都入队了，说明存在拓扑序列；否则不存在拓扑序列。
return tt == n-1;
}

int main()
{
cin >> n >> m;
memset(h, -1, sizeof(h));// 初始化
while(m--)
{
int x, y;
cin >> x >> y;
d[y] ++;  // y的入度+1
}
if(!topsort()) cout << "-1" <<endl;
else
{
for(int i = 0; i < n; i ++) cout << q[i] <<" ";
cout<<endl;
}
return 0;
}


zxq0408
11天前
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int N = 100010;
int e[N], ne[N], h[N], idx;
int d[N], n, m;    //d[i]存储头结点到i结点最短距离

{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

int bfs()
{
memset(d, -1, sizeof(d));
queue<int> q;
d[1] = 0;
q.push(1);
while(q.size())
{
int t = q.front();
q.pop();
for(int i = h[t]; i !=-1; i = ne[i])
{
int j = e[i]; ////e[i]表示存在一条边由i指向e[i],通过j来将其存储
if(d[j] == -1)   //若果没有遍历过j点
{
//d[j] = d[i] + 1;***************错误写法
d[j] = d[t] + 1;
q.push(j);
}
}
}
return d[n];
}

int main()
{
cin >> n >> m;
memset(h, -1, sizeof(h));
while(m--)
{
int a,b;
cin >> a >>b;
}
cout << bfs() <<endl;
return 0;
}


zxq0408
11天前
// 节点的编号是指上图所画的树中节点的值，范围是从1~n。在本题中，每次输入的a和b就是节点的编号，编号用e[i]数组存储。
// 节点的下标指节点在数组中的位置索引，数组之间的关系就是通过下标来建立连接，下标用idx来记录。idx范围从0开始，如果idx==-1表示空。

// e[i]的值是编号，是下标为i节点的编号。
// ne[i]的值是下标，是下标为i的节点的next节点的下标。
// h[i]存储的是下标，是编号为i的节点的next节点的下标
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 100010, M = N * 2;
int h[N],e[M],ne[M],idx;//e存值，ne存下一个点的地址,h存链表的头
//注意这个N和M，踩过一次坑
int n;
int ans=N;//此处初始化的意思就是在取min时（很有可能）被赋为第一个值
bool st[N];//看看这个点是否走过

void add(int a, int b) // 添加一条边a->b
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

int dfs(int u){
st[u]=true;//说明这个点已经走过去了
int size=0,sum=0;//(初始化）如果为叶子节点的话，那么sum为0，没有子块
//size指u节点的单个子树的值
for(int i=h[u];i!=-1;i=ne[i]){//遍历u的所有子节点
int j=e[i];//j代表u的联通节点，u->j
if(st[j]){//这个点已经遍历过，那么看u的下一个子节点
continue;
}
int s=dfs(j);//得到子树点的个数
size=max(size,s);//比得到所有子树中, 最多的点的个数
sum+=s;//计算u节点所统领的所有子节点
}
size=max(size,n-sum-1);//看看是当前点子树所在的连通块的点数多, 还是父所在的连通块点数多, 获取最多的点数
ans=min(size,ans);//当前点最多的连通块点数, 是否是所有点中的最小值?
return sum+1;//返回u节点+所有u节点统领的节点的综合
}

int main()
{
memset(h, -1, sizeof(h));
cin >> n;
for(int i = 1; i < n; i ++)
{
int a, b;
cin >> a >> b;
}
dfs(1);
cout << ans << endl;
return 0;
}


zxq0408
11天前
#include <iostream>
#include<queue>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 110;
int g[N][N],d[N][N],n,m; //g[N][N]用来存储迷宫,d[x][y]用来存储(x,y)这一点到坐标原点的距离
queue <pair<int,int>> q; //q队列用来存储宽度优先搜素到的路径也就是走迷宫经过哪些点

int bfs()
{
memset(d, -1, sizeof d);  // 将d所有元素初始化为-1,当d[i][j] = -1时代表没走到过
d[0][0] = 0;      //位于原点时距离原点的距离为0
q.push({0, 0});   //将原点入队
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1}; //定义方向向量一共四个方向

while(q.size())   //当队列非空时执行循环
{
auto t = q.front();
q.pop();
//遍历四个方向
for(int i=0;i<4;i++)
{
int x = t.first + dx[i], y = t.second + dy[i];  //四个方向对应的坐标
if(x >= 0 && x < n && y >= 0 && y < m && g[x][y] == 0 && d[x][y] == -1)
{
d[x][y] = d[t.first][t.second] + 1;  //走到下一个点的同时，距离+1
q.push({x, y});  //同时将该点入队
}
}
}
return d[n - 1][m - 1]; //递归回下一个点
}

int main()
{
cin >> n >> m;
//输入迷宫
for(int i = 0; i < n; i ++)
for(int j = 0; j < m; j ++)
cin >> g[i][j];

cout << bfs() <<endl;
return 0;
}


zxq0408
11天前

#### C++ 代码

#include<iostream>
using namespace std;
const int N = 10;
int state[N];
int path[N];
int n;

//dfs(i) 表示的含义是：在 path[i] 处填写数字，然后递归的在下一个位置填写数字。
void dfs(int u)
{
if(u > n)  //数字填充完了，进行输出
{
for(int i = 1; i <= n; i++)  //输出方案
cout << path[i] << " ";
cout << endl;
}
for(int i = 1; i <= n; i++)    // 空位上的数字可能是1~n
{
if(!state[i])    //如果数字i并没有被用过
{
state[i] = 1;  //数字被用，修改状态
path[u] = i;   //将i加入下一位
dfs(u + 1);    //填下一位
state[i] = 0;  //回溯，将i取出
}
}
}

int main()
{
cin >> n;
dfs(1);
return 0;
}


zxq0408
12天前

### 拉链法

#include<iostream>
#include<cstring>
using namespace std;
const int N = 100003;
int h[N], e[N], ne[N], idx;
//h[]散列表保存头节点的下标
// e[]保存值，ne[]保存前一个值的下标，idx是链表的索引

//向哈希表中插入一个数x
void insert(int x)
{
int k = (x % N + N) % N;
e[idx] = x;
ne[idx] = h[k];
h[k] = idx ++;
}

//在哈希表中查找对应元素是否存在
bool find(int x)
{
int k = (x % N + N) % N;
for(int i = h[k]; i != -1; i = ne[i])
{
if(e[i] == x)
return true;
}
return false;
}

int main()
{
int n;
scanf("%d", &n);
memset(h, -1, sizeof h);   //散列表初始化
while(n --)
{
char op[2];
int x;
scanf("%s%d", op, &x);
if(*op == 'I') insert(x);
else
{
if(find(x)) cout << "Yes" <<endl;
else cout << "No" <<endl;
}
}
return 0;
}


### 开放寻址法

#include<iostream>
#include<cstring>
using namespace std;
const int N = 200003, null_ = 0x3f3f3f3f;
int h[N];

// 如果x在哈希表中，返回x的下标；如果x不在哈希表中，返回x应该插入的位置
int find(int x)
{
int t = (x % N + N) % N;
while(h[t] != null_  &&  h[t] != x)
{
t ++;
if(t == N) t = 0;
}
return t;
}
int main()
{
int n;
scanf("%d", &n);
memset(h, 0x3f, sizeof h);
while(n --)
{
char op[2];
int x;
scanf("%s%d", op, &x);
if(*op == 'I') h[find(x)] = x;
else
{
if(h[find(x)] == null_) cout << "No" <<endl;
else cout << "Yes" <<endl;
}
}
return 0;
}