网站下载工具,天津网站建设论坛,建设网站一般多少钱,做旅游网站的文章目录 前言A - Dijkstra Algorithm0x00 算法题目0x01 算法思路0x02 代码实现 B - 最长路0x00 算法题目0x01 算法思路0x02 代码实现 C - 二分图最大匹配0x00 算法题目0x01 算法思路0x02 代码实现 D - 搭配飞行员0x00 算法题目0x01 算法思路0x02 代码实现 E - The Perfect Sta… 文章目录 前言A - Dijkstra Algorithm0x00 算法题目0x01 算法思路0x02 代码实现 B - 最长路0x00 算法题目0x01 算法思路0x02 代码实现 C - 二分图最大匹配0x00 算法题目0x01 算法思路0x02 代码实现 D - 搭配飞行员0x00 算法题目0x01 算法思路0x02 代码实现 E - The Perfect Stall0x00 算法题目0x01 算法思路0x02 代码实现 F - Asteroids0x00 算法题目0x01 算法思路0x02 代码实现 G - Til the Cows Come Home0x00 算法题目0x01 算法思路0x02 代码实现 H - 拓扑排序0x00 算法题目0x01 算法思路0x02 代码实现 总结 前言
最短路Dijkstraspfa图论二分图算法AYIT—ACM训练(模板版) A — Dijkstra B — spfa/Dijkstra C — 二分图 D — 二分图 E — 二分图 F — 二分图 G — Dijkstra H — Topsort A - Dijkstra Algorithm
0x00 算法题目 0x01 算法思路
Dijkstra算法基础模板题 模板演示
int dijkstra()
{memset(dist,0x3f,sizeof dist);dist[1]0;for(int i0;in;i){int t-1;for(int j1;jn;j){if(!st[j] (t-1 || dist[t] dist[j]))tj;}st[t]true;for(int j1;jn;j)dist[j]min(dist[j],dist[t]g[t][j]);}if(dist[n]0x3f3f3f3f) return -1;return dist[n];}0x02 代码实现
朴素版本Dijkstra 代码演示
#includeiostream
#includecstring
#includealgorithmusing namespace std;
const int N 510;
int g[N][N];
bool st[N];
int dist[N];
int n,s,f;int dijkstra()
{memset(dist,0x3f,sizeof dist);dist[s]0;for(int i0;in;i){int t-1;for(int j1;jn;j)if(!st[j] (t-1 || dist[t] dist[j]))tj;st[t]true;for(int j1;jn;j)dist[j]min(dist[j],dist[t]g[t][j]);}if(dist[f]0x3f3f3f3f) return -1;return dist[f];
}int main()
{cinnsf;for(int i1;in;i){for(int j1;jn;j){int x;cinx;if(x-1) g[i][j]0x3f3f3f3f;else g[i][j]x;}}int t dijkstra();couttendl;return 0;
} 运行结果 spfa算法 代码演示
#includeiostream
#includecstring
#includealgorithm
#includequeueusing namespace std;
const int N110,M110*110;
int n,s,f;
bool st[N];
int h[N],w[M],ne[M],e[M],idx;
int dist[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[s]0;queueint q;q.push(s);while(q.size()){int t q.front();q.pop();st[t]false;for(int ih[t];i!-1;ine[i]){int je[i];if(dist[j] dist[t] w[i]){dist[j]dist[t]w[i];if(!st[j]){q.push(j);st[j]true;}}}}if(dist[f]0x3f3f3f3f) return -1;else return dist[f];
}int main()
{cinnsf;memset(h,-1,sizeof h);for(int i1;in;i){for(int j1;jn;j){int x;cinx;//if(x-1) continue;if(x0) add(i,j,x);}}coutspfa()endl;return 0;
} 运行结果
B - 最长路
0x00 算法题目 0x01 算法思路
spfa算法基础模板题 模板演示
int spfa()
{memset(dist, 0x3f, sizeof dist);dist[1] 0;queueint q;q.push(1);while(q.size()){auto t q.front();q.pop();st[t]false;for(int ih[t];i!-1;ine[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];
}0x02 代码实现
spfa算法 代码演示
#includebits/stdc.h
#define endl \nusing namespace std;
const int N 1510,INF 0x3f3f3f3f;
int n,m;
int dist[N];
int g[N][N];
queueint q;void spfa()
{memset(dist,-1,sizeof dist);dist[1]0;q.push(1);while(!q.empty()){int t q.front();q.pop();for(int j1;jn;j){if(g[t][j] dist[j] dist[t] g[t][j]){dist[j] dist[t] g[t][j];q.push(j);}}}}int main()
{cinnm;for(int i1;im;i){int a,b,c;cinabc;g[a][b]max(g[a][b],c);}spfa();coutdist[n]endl;return 0;
}运行结果
C - 二分图最大匹配
0x00 算法题目 0x01 算法思路
二分图模板题 模板演示
//邻接表
bool find(int x)
{for (int i h[x]; i ! -1; i ne[i]){int j e[i];if (!st[j]){st[j] true;if (match[j] 0 || find(match[j])){match[j] x;return true;}}}return false;
}
//邻接矩阵
bool find(int x)
{for(int i0;ig[x].size();i){int j g[x][i];if(!st[j]){st[j]true;if(match[j]0 || find(match[j])){match[j]x;return true;}}}return false;
}0x02 代码实现 代码演示
#includeiostream
#includecstringusing namespace std;const int N 510,M5e410;
int n,m,q;
int h[N],e[M],ne[M],idx;
int match[N];
bool st[N];void add(int a,int b)
{e[idx]b,ne[idx]h[a],h[a]idx;
}bool find(int x)
{for(int ih[x];i!-1;ine[i]){int j e[i];if(!st[j]){st[j]true;if(match[j]0 || find(match[j])){match[j]x;return true;}}}return false;
}int main()
{cinnmq;memset(h,-1,sizeof h);while(q--){int u,v;cinuv;add(u,v);}int res0;for(int i1;in;i){memset(st,false,sizeof st);if(find(i)) res;}coutresendl;return 0;
} 运行结果
D - 搭配飞行员
0x00 算法题目 0x01 算法思路
二分图模板题 模板演示
//邻接表
bool find(int x)
{for (int i h[x]; i ! -1; i ne[i]){int j e[i];if (!st[j]){st[j] true;if (match[j] 0 || find(match[j])){match[j] x;return true;}}}return false;
}
//邻接矩阵
bool find(int x)
{for(int i0;ig[x].size();i){int j g[x][i];if(!st[j]){st[j]true;if(match[j]0 || find(match[j])){match[j]x;return true;}}}return false;
}0x02 代码实现 代码演示
#includeiostream
#includecstring
#includealgorithm
#includebits/stdc.husing namespace std;
const int N 110;int n,m;
int map[N][N];
int match[N];
bool st[N];
vectorint g[N];
bool find(int x)
{for(int i0;ig[x].size();i){int j g[x][i];if(!st[j]){st[j]true;if(match[j]0 || find(match[j])){match[j]x;return true;}}}return false;
}int main()
{scanf(%d %d,n,m);int a,b;while(cinab){g[a].push_back(b);}int res 0;for(int i1;im;i){memset(st,false,sizeof st);if(find(i)) {res;}}coutres;return 0;
} 运行结果
E - The Perfect Stall
0x00 算法题目 0x01 算法思路
二分图模板题 模板演示
//邻接表
bool find(int x)
{for (int i h[x]; i ! -1; i ne[i]){int j e[i];if (!st[j]){st[j] true;if (match[j] 0 || find(match[j])){match[j] x;return true;}}}return false;
}
//邻接矩阵
bool find(int x)
{for(int i0;ig[x].size();i){int j g[x][i];if(!st[j]){st[j]true;if(match[j]0 || find(match[j])){match[j]x;return true;}}}return false;
}0x02 代码实现 代码演示
#includealgorithm
#includebits/stdc.h
using namespace std;
const int N 510,M5e410;
int n,m;
int match[N];
bool st[N];
vectorint g[N];bool find(int x)
{for(int i0;ig[x].size();i){int j g[x][i];if(!st[j]){st[j]true;if(match[j]0 || find(match[j])){match[j]x;return true;}}}return false;
}int main()
{while(~scanf(%d%d,n,m)){memset(st,false,sizeof st);memset(match,0,sizeof match);for(int i1;in;i){g[i].clear();int s;cins;while(s--){int q;cinq;g[i].push_back(q);}}int res0;for(int i1;in;i){memset(st,false,sizeof st);if(find(i)) res;}coutresendl;}return 0;
}运行结果
F - Asteroids
0x00 算法题目 0x01 算法思路
二分图模板题 模板演示
//邻接表
bool find(int x)
{for (int i h[x]; i ! -1; i ne[i]){int j e[i];if (!st[j]){st[j] true;if (match[j] 0 || find(match[j])){match[j] x;return true;}}}return false;
}
//邻接矩阵
bool find(int x)
{for(int i0;ig[x].size();i){int j g[x][i];if(!st[j]){st[j]true;if(match[j]0 || find(match[j])){match[j]x;return true;}}}return false;
}0x02 代码实现 代码演示
#includeiostream
#includecstring
using namespace std;
const int N 510,M5e410;
int n,m,q;
int h[N],e[M],ne[M],idx;
int match[N];
bool st[N];void add(int a,int b)
{e[idx]b,ne[idx]h[a],h[a]idx;
}bool find(int x)
{for(int ih[x];i!-1;ine[i]){int j e[i];if(!st[j]){st[j]true;if(match[j]0 || find(match[j])){match[j]x;return true;}}}return false;
}int main()
{cinnm;memset(h,-1,sizeof h);while(m--){int u,v;cinuv;add(u,v);}int res0;for(int i1;in;i){memset(st,false,sizeof st);if(find(i)) res;}coutresendl;return 0;
} 运行结果
G - Til the Cows Come Home
0x00 算法题目 0x01 算法思路
Dijkstra算法基础模板题 模板演示
int dijkstra()
{memset(dist,0x3f,sizeof dist);dist[1]0;for(int i0;in;i){int t-1;for(int j1;jn;j){if(!st[j] (t-1 || dist[t] dist[j]))tj;}st[t]true;for(int j1;jn;j)dist[j]min(dist[j],dist[t]g[t][j]);}if(dist[n]0x3f3f3f3f) return -1;return dist[n];}0x02 代码实现 代码演示
#includeiostream
#includecstring
#includealgorithm
#includestdbool.husing namespace std;const int N1010,inf 0x3f3f3f3f;int n,m;
bool st[N];
int dist[N];
int g[N][N];int dijkstra()
{memset(dist,inf,sizeof(dist));dist[1] 0;for(int i1;i n;i){int t-1;for(int j1;jn;j)if(!st[j] (t-1 || dist[t] dist[j]))tj;st[t]true;for(int j1;jn;j)dist[j]min(dist[j],dist[t]g[t][j]);}return dist[n];
}int main()
{cinmn;memset(g,inf,sizeof g);for(int i0;im;i){int a,b,c;cinabc; g[a][b]g[b][a]min(g[a][b],c);}cout dijkstra() endl;return 0;
}运行结果
H - 拓扑排序
0x00 算法题目 0x01 算法思路
拓扑排序算法基础模板题 模板演示
bool topsort()
{int hh0,tt-1;for (int i 1; i n; i )if (!d[i])q[ tt] i;while(hhtt){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 ttn-1;
}0x02 代码实现 代码演示
#includeiostream
#includecstring
#includealgorithm
#includequeue
#includevectorusing namespace std;const int N100010;int n,m;
vectorint v[N];
int size,d[N];
int ans[N];void topsort()
{priority_queueint,vectorint,greaterint q;for(int i1;in;i)if(!d[i]) q.push(i);while(!q.empty()){int t q.top();q.pop();ans[size] t;for(auto it : v[t]){d[it]--;if(!d[it]) q.push(it);}}
}int main()
{cinnm;for(int i0;im;i){int a,b;cinab;v[a].push_back(b);d[b];}topsort();for(int i0 ; isize ;i)cout v ans[i] ;return 0;
} 运行结果 总结
这次训练很明显涉及到了最短路Dijkstraspfa图论二分图算法以及topsort算法这次考的比较基础但是让我意识到了算法必须熟练记忆模板是很重要的。
