吉林大学ACM模板：算法与数据结构详解
下载需积分: 25 | PDF格式 | 631KB |
更新于2024-07-22
| 111 浏览量 | 举报
吉林大学ACM模板是一份专门为吉林大学计算机科学与技术学院2005级学生设计的编程竞赛模板，涵盖了广泛的算法和数据结构知识点。这份模板适用于参加ACM/ICPC（国际大学生程序设计竞赛）的学生，帮助他们在比赛中的代码实现更加规范和高效。
1. **图论部分**：
- **深度优先搜索（DFS）**：用于标记有向图的DAG（有向无环图），包括无向图的桥梁查找、连通性分析以及最大团问题的动态规划和DFS方法。
- **最短路径算法**：包括Dijkstra算法（O(E*logE)版本）、Bellman-Ford算法（单源最短路径，O(VE)）、SPFA（更高效的最短路径算法）和第K短路的求解。
- **生成树问题**：如Prim算法求最小生成树，最小生成森林问题（K棵树，O(MlogM)）、有向图最小树形图，以及Steiner Tree（最小生成树）和强连通分量的TARJAN算法。
2. **网络流部分**：
- **二分图匹配**：涉及匈牙利算法（DFS和BFS实现）、HOPcroft-Carp算法、Kuhn-Munkres算法（O(M*M*N)）以及最小割问题（O(N^3)）。
- **流问题**：最大流（Dinic算法，O(V^2*E)和HLPP算法，O(V^3)）、最小费用流（两种时间复杂度，O(V*E*F)和O(V^2*F)）以及割集的多种变体。
3. **数据结构**：
- **日期计算**：基础的日期逻辑，如求某天是星期几。
- **高级数据结构**：左偏树（合并复杂度O(logN)）、树状数组、二维树状数组、Trie树（包括K叉和特定结构）、后缀数组（O(N*LOGN)）等。
这份模板不仅有助于学生掌握图论、网络流和数据结构的核心算法，还提供了实际问题解决的策略，对于提高参赛者的编程技巧和问题解决能力非常有帮助。通过熟练应用这些内容，参赛者能够提升在ACM/ICPC竞赛中的竞争力。
吉林大学 ACM Group
8
for (i = n - 1; i >= 0; i--) {
for (j = 0, k = -1; j < n; j++) if (0 == vis[j]) {
if (k == -1 || deg[j] > deg[k]) k = j;
}
vis[k] = 1, tag[i] = k;
for (j = 0; j<n; j++)
if (0 == vis[j] && g[k][j]) deg[j]++;
}
}
/*==================================================*\
| 稳定婚姻问题 O(n^2)
\*==================================================*/
const int N = 1001;
struct People{
bool state;
int opp, tag;
int list[N]; // man使用
int priority[N]; // woman使用, 有必要的话可以和list合并，
以节省空间
void Init(){ state = tag = 0; }
}man[N], woman[N];
struct R{
int opp; int own;
}requst[N];
int n;
void Input(void);
void Output(void);
void stableMatching(void);
int main(void){
//...
Input();
stableMatching();
Output();
//...
return 0;
}
void Input(void){
scanf("%d\n", &n);
int i, j, ch;
for( i=0; i < n; ++i ) {
man[i].Init();
for( j=0; j < n; ++j ){ //按照man的意愿递减排序
scanf("%d", &ch); man[i].list[j] = ch-1;
}
}
for( i=0; i < n; ++i ) {
woman[i].Init();
for( j=0; j < n; ++j ){ //按照woman的意愿递减排序，
但是，存储方法与man不同！！！！
scanf("%d", &ch); woman[i].priority[ch-1] = j;
}
}
}
void stableMatching(void){
int k;
for( k=0; k < n; +k ){
int i, id = 0;
for( i=0; i < n; ++i )
if( man[i].state == 0 ){
requst[id].opp =
man[i].list[ man[i].tag ];
requst[id].own = i;
man[i].tag += 1; ++id;
}
if( id == 0 ) break;
for( i=0; i < id; ++i ){
if( woman[requst[i].opp].state == 0 ){
woman[requst[i].opp].opp =
requst[i].own;
woman[requst[i].opp].state = 1;
man[requst[i].own].state = 1;
man[requst[i].own].opp =
requst[i].opp;
}
else{
if( woman[requst[i].opp].priority[ woman[requst[i].o
pp].opp ] >
woman[requst[i].opp].priority[requst[i].own] ){ //
man[ woman[requst[i].opp].opp ].state = 0;
woman[ requst[i].opp ].opp =
requst[i].own;
man[requst[i].own].state = 1;
man[requst[i].own].opp =
requst[i].opp;
}
}
}
}
}
void Output(void){
for( int i=0; i < n; ++i ) printf("%d\n", man[i].opp+1);
}
/*==================================================*\
| 拓扑排序
| INIT:edge[][]置为图的邻接矩阵;count[0…i…n-1]:顶点i的入度.
\*==================================================*/
void TopoOrder(int n){
int i, top = -1;
for( i=0; i < n; ++i )
if( count[i] == 0 ){ // 下标模拟堆栈
count[i] = top; top = i;
}
for( i=0; i < n; ++i )
if( top == -1 ) { printf("存在回路\n"); return ; }
else{
int j = top; top = count[top];
printf("%d", j);
for( int k=0; k < n; ++k )
if( edge[j][k] && (--count[k]) == 0 ){
count[k] = top; top = k;
}
}
}
/*==================================================*\
| 无向图连通分支(dfs/bfs 邻接阵)
| DFS / BFS / 并查集
\*==================================================*/
/*==================================================*\
| 有向图强连通分支(dfs/bfs 邻接阵)O(n^2)
\*==================================================*/
//返回分支数,id返回1..分支数的值
//传入图的大小n和邻接阵mat,不相邻点边权0
#define MAXN 100
void search(int n,int mat[][MAXN],int* dfn,int* low,int
now,int& cnt,int& tag,int* id,int* st,int& sp){
int i,j;
dfn[st[sp++]=now]=low[now]=++cnt;
for (i=0;i<n;i++)
if (mat[now][i]){
if (!dfn[i]){
search(n,mat,dfn,low,i,cnt,tag,id,st,sp);
if (low[i]<low[now])
low[now]=low[i];
}
else if (dfn[i]<dfn[now]){
for (j=0;j<sp&&st[j]!=i;j++);
if (j<cnt&&dfn[i]<low[now])
low[now]=dfn[i];
}
}
if (low[now]==dfn[now])
for (tag++;st[sp]!=now;id[st[--sp]]=tag);
}
int find_components(int n,int mat[][MAXN],int* id){
int ret=0,i,cnt,sp,st[MAXN],dfn[MAXN],low[MAXN];
for (i=0;i<n;dfn[i++]=0);
for (sp=cnt=i=0;i<n;i++)
if (!dfn[i])
search(n,mat,dfn,low,i,cnt,ret,id,st,sp);
return ret;
}
//有向图强连通分支,bfs邻接阵形式,O(n^2)
//返回分支数,id返回1..分支数的值
//传入图的大小n和邻接阵mat,不相邻点边权0
#define MAXN 100
int find_components(int n,int mat[][MAXN],int* id){
int ret=0,a[MAXN],b[MAXN],c[MAXN],d[MAXN],i,j,k,t;
剩余46页未读，继续阅读
相关推荐
windrises
- 粉丝: 7
- 资源: 4
我的内容管理
展开
