TheSun

6327

xiusike1

NatWist
Alexshwing

TheSun
6天前
#include <cstdio>

typedef long long LL;

LL qadd(LL a, LL b, LL p)
{
LL res = 0;
while (b)
{
if (b & 1) res = (res + a) % p;
a = (a + a) % p;
b >>= 1;
}
return res;
}

int main()
{
LL a, b, p;
scanf("%lld%lld%lld", &a, &b, &p);

return 0;
}



TheSun
6天前
#include <iostream>
#include <algorithm>
#include <queue>
#include <unordered_map>

using namespace std;

int bfs(string start)
{
//定义目标状态
string end = "12345678x";
//定义队列和dist数组
queue<string> q;
unordered_map<string, int> d;
//初始化队列和dist数组
q.push(start);
d[start] = 0;
//转移方式
int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};

while(q.size())
{
auto t = q.front();
q.pop();
//记录当前状态的距离，如果是最终状态则返回距离
int distance = d[t];
if(t == end) return distance;
//查询x在字符串中的下标，然后转换为在矩阵中的坐标
int k = t.find('x');
int x = k / 3, y = k % 3;

for(int i = 0; i < 4; i++)
{
//求转移后x的坐标
int a = x + dx[i], b = y + dy[i];
//当前坐标没有越界
if(a >= 0 && a < 3 && b >= 0 && b < 3)
{
//转移x
swap(t[k], t[a * 3 + b]);
//如果当前状态是第一次遍历，记录距离，入队
if(!d.count(t))
{
d[t] = distance + 1;
q.push(t);
}
//还原状态，为下一种转换情况做准备
swap(t[k], t[a * 3 + b]);
}
}
}
//无法转换到目标状态，返回-1
return -1;
}

int main()
{
string c, start;
//输入起始状态
for(int i = 0; i < 9; i++)
{
cin >> c;
start += c;
}

cout << bfs(start) << endl;

return 0;
}



TheSun
7天前
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 2010, M = 10010;

int n, m;
int h[N], w[M], e[M], ne[M], idx;
int dist[N], cnt[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++;
}

bool spfa()
{
queue<int> q;

for (int i = 1; i <= n; i ++ )
{
st[i] = true;
q.push(i);
}

while (q.size())
{
int t = q.front();
q.pop();

st[t] = false;

for (int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
if (dist[j] > dist[t] + w[i])
{
dist[j] = dist[t] + w[i];
cnt[j] = cnt[t] + 1;

if (cnt[j] >= n) return true;
if (!st[j])
{
q.push(j);
st[j] = true;
}
}
}
}

return false;
}

int main()
{
scanf("%d%d", &n, &m);

memset(h, -1, sizeof h);

while(m--)
{
int a, b, c;
cin >> a >> b >> c;
}

if(spfa()) puts("Yes");
else puts("No");

return 0;

}



TheSun
7天前
#include<iostream>
#include<cstring>

using namespace std;

const int N = 510 , M = 100010;
int n1,n2,m;
int h[N],ne[M],e[M],idx;
bool st[N];
int match[N];

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

int find(int x)
{
//遍历自己喜欢的女孩
for(int i = h[x] ; i != -1 ;i = ne[i])
{
int j = e[i];
if(!st[j])//如果在这一轮模拟匹配中,这个女孩尚未被预定
{
st[j] = true;//那x就预定这个女孩了
//如果女孩j没有男朋友，或者她原来的男朋友能够预定其它喜欢的女孩。配对成功
if(!match[j]||find(match[j]))
{
match[j] = x;
return true;
}

}
}
//自己中意的全部都被预定了。配对失败。
return false;
}

int main()
{
memset(h,-1,sizeof h);

cin>>n1>>n2>>m;
while(m--)
{
int a,b;
cin>>a>>b;
}

int res = 0;
for(int i = 1; i <= n1; i ++)
{
//因为每次模拟匹配的预定情况都是不一样的所以每轮模拟都要初始化
memset(st,false,sizeof st);
if(find(i)) res++;
}

printf("%d\n", res);

return 0;
}



TheSun
7天前
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;
const int N = 1e5 + 10, M = 2e5 + 10; // 无向图, 所以最大边数是2倍
int e[M], ne[M], h[N], idx; // 使用邻接表
int st[N]; // 判断状态，是否 1 2

// 初始化邻接表
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

// dfs 来进行染色
bool dfs(int u, int color) {
st[u] = color;  // 首先给这个点染色

for(int i = h[u]; i != -1; i = ne[i]){  // 寻找相应的邻接表
int j = e[i];
if(!st[j]) {
if(!dfs(j, 3 - color)) return false;
}else if(st[j] == color) return false;
}

return true;
}

int main(){
int n, m;
scanf("%d%d", &n, &m);

memset(h, -1, sizeof h);
while (m --){
int a, b;
scanf("%d%d", &a, &b);
}

bool flag = true;
for(int i = 1; i <= n; i ++){
if(!st[i]){
if(!dfs(i, 1)){
flag = false;
break;
}
}
}

if(flag) puts("Yes");
else puts("No");
return 0;
}



TheSun
8天前

kruskal算法

1. 将所有的边按照权重从小到大进行排序；
2. 枚举每条边a,b 和 权重 c, 如果不连通就把这条边加入到所存在的边的集合S
note:

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010, M = 200010;
int n, m;
int p[N];

struct Edge
{
int a, b, w;
bool operator< (const Edge &W) const
{
return w < W.w;
}
}edges[M];

int find(int x)
{
if(p[x] != x) p[x] = find(p[x]);
return p[x];
}

int main()
{
cin >> n >> m;

for(int i = 0; i < m; i ++)
{
int a, b, w;
scanf("%d%d%d", &a, &b, &w);
edges[i] = {a, b, w};
}

sort(edges, edges + m);

for(int i = 1; i <= n; i ++)
{
p[i] = i;
}

int res = 0, cnt = 0;
for(int i = 0; i < m; i ++)
{
int a = edges[i].a, b = edges[i].b, w = edges[i].w;
a = find(a), b = find(b);
if(a != b)
{
p[a] = b;
res += w;
cnt ++;
}
}

if( cnt < n - 1) puts("impossible");
else printf("%d\n", res);

return 0;
}


TheSun
9天前

### Prim 算法– 基于贪心

dist[i]设置为无穷大
dist[1] = 0

for i in 0..n-1
1. 找到不在s集合中，距离s集合最近的点t
2. 将这个点t放入集合中
3. 利用这个点t， 更新不在集合s中的点

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 510, INF = 0x3f3f3f3f;
int n, m;

int g[N][N];
int dist[N];
bool st[N];

int prim()
{
memset(dist, 0x3f, sizeof dist);

int res = 0;

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

if(i && dist[t] == INF) return INF;
if(i) res += dist[t];

for(int j = 1; j <= n; j ++)
{
dist[j] = min(dist[j], g[t][j]);
}
st[t] = true;
}

return res;
}

int main()
{
scanf("%d%d", &n, &m);

memset(g, 0x3f, sizeof g);

while (m -- )
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
g[a][b] = g[b][a] = min(g[a][b], c);
}

int t = prim();

if (t == INF) puts("impossible");
else printf("%d\n", t);

return 0;
}



TheSun
12天前
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 100010;

int n, m;
int h[N], w[N],e[N], ne[N], idx;
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 spfa()
{
memset(dist, 0x3f, sizeof dist);

dist[1] = 0;

queue<int> q;
q.push(1);
st[1] = true;

while(q.size())
{
int t = q.front();
q.pop();
st[t] = false;

for(int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
if(dist[j] > dist[t] + w[i])
{
dist[j] = dist[t] + w[i];
if(!st[j])
{
q.push(j);
st[j] = true;
}
}
}
}

return dist[n];
}

int main()
{
scanf("%d%d", &n, &m);

memset(h, -1, sizeof h);

while(m--)
{
int a, b, c;
cin >> a >> b >> c;
}

int t = spfa();

if(t == 0x3f3f3f3f) puts("impossible");
else printf("%d\n", t);

return 0;

}



TheSun
12天前
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 210, INF = 1e9;

int n, m, q;
int d[N][N];

void floyd()
{
for (int k = 1; k <= n; k ++ )
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n; j ++ )
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}

int main()
{
scanf("%d%d%d", &n, &m, &q);

//初始化存储矩阵
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n; j ++ )
if (i == j) d[i][j] = 0;
else d[i][j] = INF;

//输入边
while (m -- )
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
d[a][b] = min(d[a][b], c); //保存最小的边
}

//处理询问
floyd();

//查询结果
for(int i = 0; i < q; i ++ )
{
int a, b;
scanf("%d%d", &a, &b);

int t = d[a][b];
if (t > INF / 2) puts("impossible"); //由于有负权边存在所以约大过INF/2也很合理
else printf("%d\n", t);
}

return 0;
}



TheSun
12天前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 510, M = 10010;

int n, m, k;
int dist[N];
int backup[N];

struct Edge
{
int a;
int b;
int w;
}edges[M];

void bellman_ford()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;

for (int i = 0; i < k; i++)
{//k次循环

memcpy(backup, dist, sizeof dist);

for (int j = 0; j < m; j++) {//遍历所有边
int a = edges[j].a, b = edges[j].b, w = edges[j].w;
dist[b] = min(dist[b], backup[a] + w);
//使用backup:避免给a更新后立马更新b, 这样b一次性最短路径就多了两条边出来
}
}

}

int main()
{
cin >> n >> m >> k;

for(int i = 0; i < m; i ++)
{
int a, b, w;
cin >> a >> b >> w;
edges[i] = {a, b, w};
}

bellman_ford();

//if dist[n] > 最大数值的2倍
if (dist[n] > 0x3f3f3f3f / 2) puts("impossible");
else printf("%d\n", dist[n]);

return 0;
}