2017年ACM模板（常用）弱渣整理 三、图论

一、拓扑排序

#include<cstdio> #include<cstring> #include<queue> using namespace std; const int maxn = 1000; struct Node{ int indegree;//入度数 int num; //排序number int id; //编号 }N[maxn]; int V,E; int d[maxn][maxn];//邻接矩阵 /*初始化*/ void Init() { for(int i=0; i<V; i++) { N[i].indegree = 0; N[i].num = NULL; N[i].id = i; } memset(d,0,sizeof(d)); return; } int main() { scanf("%d%d",&V,&E); Init(); int s,t; for(int i=0; i<E; i++) { scanf("%d%d",&s,&t); d[s][t] = 1; N[t].indegree++;//子结点的入度加一 } int counter = 0; queue<Node> q; for(int i=0; i<V; i++) { if(!N[i].indegree) { q.push(N[i]); } } while(!q.empty()) { Node v = q.front(); q.pop(); N[v.id].num = counter++; for(int i=0; i<V; i++) { if(d[v.id][i]) { if((--(N[i].indegree))==0) { q.push(N[i]); } } } } for(int i=0; i<V; i++) { printf("%d ",N[i].num); } return 0; }

---

二、BFS

void bfs(int s) { queue<int>q; //用队列实现 q.push(s); //插入开始顶点 for(int i=0;i<n;i++) { d[i] = INF; //初始化为INF } d[s] = 0; while(!q.empty()) { int v = q.front(); q.pop(); for(int i=1;i<=n;i++) { if(metrix[v][i]&&d[i]==INF) { d[i] = d[v] + 1; q.push(i); } } } }

---

三、最短路径问题

1.Bellman-Ford算法

#include<cstdio> #include<cstring> #include<vector> using namespace std; const int maxn = 1000; const int INF = 10000000; int n,e; int d[maxn],pre[maxn]; struct edge{ int from,to,cost; }; edge es[maxn]; void init(int s) { for(int i=0; i<n; i++) { d[i] = INF; pre[i] = NULL; } d[s] = 0; return; } void Bellman_Ford(int s) { init(s); while(true) { bool updata = false; for(int i=0; i<e; i++) { edge e = es[i]; if(d[e.from]!=INF && d[e.to] > d[e.from] +e.cost) { d[e.to] = d[e.from] + e.cost;//更新最短路径 pre[e.to] = e.from; //更新父结点 updata = true; } } if(!updata) break; } } int main() { scanf("%d%d",&n,&e); int s,t,c; for(int i=0; i<e; i++) { scanf("%d%d%d",&s,&t,&c); es[i].from = s; es[i].to = t; es[i].cost = c; } Bellman_Ford(0); for(int i=0; i<n; i++) { printf("%d ",d[i]); } printf("\n"); for(int i=0; i<n; i++) { printf("%d ",pre[i]); } return 0; }

判断负圈：

bool find_negative_loop() { memset(d,0,sizeof(d)); for(int i=0; i<n; i++) { for(int j=0; j<e; j++) { egde e = es[j]; if(d[e.to] > d[e.from] + e.cost) { d[e.to] = d[e.from] + e.cost; if(i == V - 1) return true;//如果第n次仍然更新了，则存在负圈 } } } return false; }

2.Dijksta算法

#include<cstdio> #include<queue> #include<vector> using namespace std; const int maxn = 1000; const int INF = 99999999; struct edge{ int to,cost; edge(int to, int cost) : to(to), cost(cost){} }; typedef pair<int,int> P;//first是最短路径，second是顶点的编号 int d[maxn]; int V,E; vector<edge> G[maxn]; void dijkstra(int s) { priority_queue<P,vector<P>,greater<P> > q; fill(d, d + V, INF); d[s] = 0; q.push(P(0,s)); while(!q.empty()) { P p = q.top(); q.pop(); int v = p.second; if(d[v] < p.first) continue; for(int i=0; i<G[v].size(); i++) { edge e = G[v][i]; if(d[e.to] > d[v] + e.cost) { d[e.to] = d[v] + e.cost; q.push(P(d[e.to],e.to)); } } } } int main() { scanf("%d%d",&V,&E); int s,t,c; for(int i=0;i<E;i++) { scanf("%d%d%d",&s,&t,&c); G[s].push_back(edge(t,c)); } dijkstra(0); for(int i=0; i<V; i++) { printf("%d ",d[i]); } return 0; }

3. 任意结点对最短路

Floyd-Warshall算法

/*初始化*/ void Init() { for(int i=0; i<V; i++) { for(int j=0; j<V; j++) { if(i==j) d[i][j] = 0; else if(!cost[i][j]) { d[i][j] = INF; } else d[i][j] = cost[i][j]; } } return; } void warshall_floyd() { for(int k=0; k<V; k++) { for(int i=0; i<V; i++) { for(int j=0; j<V; j++) { d[i][j] = min(d[i][j], d[i][k] + d[k][j]); } } } return; }

4.无权最短路径

使用BFS即可。

---

四、最小生成树

Kruskal算法：（并查集）

int kruskal() { sort(es, es+E, cmp); init_union_find(V); int res = 0; for(int i=0; i<E; i++) { edge e = es[i]; if(!same(e.u, e.v)) { unite(e.u, e.v); res += e.cost; } } return res; }

---

五、欧拉图

先判断一个图是否为连通图，如果不是，那么直接输出“No”；如果是，那么就需要再判断每一个顶点的度数，如果奇点的数目为0或2则输出”Yes”，否则输出”No”。 连通图的判断使用并查集

---

六、最大流问题

Ford-Fulkerson算法

#include<cstdio> #include<cstring> #include<vector> #include<algorithm> using namespace std; const int maxn = 1000+10; const int INF = 1000000000; struct edge{ int to, cap, rev; }; vector<edge> G[maxn]; bool used[maxn]; int V,E; /*向图中增加一条从s到t为cap的边*/ void add_edge(int from, int to, int cap) { G[from].push_back((edge){to, cap, G[to].size()}); G[to].push_back((edge){from, 0, G[from].size() - 1}); } /*通过DFS找增广路*/ int dfs(int v, int t, int f) { if(v == t) return f; used[v] = true; for(int i=0; i<G[v].size(); i++) { edge &e = G[v][i]; if(!used[e.to] && e.cap > 0) { int d = dfs(e.to, t, min(f, e.cap)); if(d > 0) { e.cap -= d; G[e.to][e.rev].cap += d; return d; } } } return 0; } /*求解从s到t的最大流*/ int max_flow(int s, int t) { int flow = 0; for(; ;) { memset(used, 0, sizeof(used)); int f = dfs(s, t, INF); if(f == 0) return flow; flow += f; } } int main() { scanf("%d%d",&V,&E); int s,t,e; for(int i=0; i<E; i++) { scanf("%d%d%d",&s,&t,&e); add_edge(s, t, e); } printf("%d\n", max_flow(0, V-1)); return 0; }