题意：判断一个无向图是否三连通？
思路：枚举每个点，删去后用Tarjan判断图中是否存在割点，如果存在则该图不满足三连通性。
// #include<bits/stdc++.h> #include <cstdio> #include <iostream> #include <algorithm> #include <cstring> // for memset #include <vector> // vector<int>().swap(v); #define IOS ios_base::sync_with_stdio(0); cin.tie(0) #define lowbit(x) (x&(-x)) using namespace std; typedef long long ll; int del,root; bool cut; int dfn[510], low[510]; vector<int> e[510]; int n,m; int tot; void Tarjan(int u,int p) { if(cut) return; dfn[u]=low[u]= ++tot; int son=0; for(vector<int>::iterator it=e[u].begin();it!=e[u].end();it++) { int v=*it; if(v==p || v==del) continue; if(!dfn[v]) { son++; Tarjan(v,u); low[u]=min(low[u],low[v]); if((u == root && son > 1) || (u != root && low[v] >= dfn[u])) { cut=true; return; } }else{ low[u]=min(low[u],dfn[v]); } } } int main(void) { while (scanf("%d%d", &n, &m) != EOF && n) { for (int i = 0; i < n; ++i) e[i].clear(); for (int i = 0; i < m; ++i) { int u, v; scanf("%d%d", &u, &v); e[u].push_back(v); e[v].push_back(u); } cut = 0; for (int i = 0; i < n; ++i) { del = i; memset(dfn, 0, sizeof(dfn)); tot = 0; root = !i; Tarjan(root, -1); if (cut) break; for (int j = 0; j < n; ++j) { if (j != del && !dfn[j]) { cut = 1; break; } } if (cut) break; } printf("%s\n", cut ? "NO" : "YES"); } return 0; }
题意：老板决定大裁员，每开除一个人，同时要将其下属一并开除，以及下属的下属... ... 给出开除掉每个人的贡献值和各种从属关系，求最小裁员数及最大贡献值和。
定义一个有向图 G=(V,E) 的闭合图是该有向图的一个点集，且该点集的所有出边都还指向该点集。即闭合图内的任意点的任意后继也一定在闭合图中。
// 最大权闭合图的求解方法是： 1.先构造网络流N，添加源点s，从s到正权值点做一条边，容量为点的权值。 2.添加汇点t，从负权值点到t做一条边，容量为点的权值的绝对值。 3.原来的边的容量统统设为无穷大。 4.求解最小割，最大权=正权值之和-最小割权值 5.残余网络中的点的个数即为裁员个数。
感觉网络流不是很好理解，这个题先码上过段时间再来理解
// #include<bits/stdc++.h> #include <cstdio> #include <iostream> #include <algorithm> #include <cstring> // for memset #include <vector> // vector<int>().swap(v); #include <set> // multiset set<int,greater<int>> //big->small #include <map> #include <stack> // top() #include <queue> // front() // priority_queue<T,vector<T>,greater<T> > #include <cmath> // auto &Name : STLName Name. using namespace std; typedef long long ll; struct edge { int to,rev; ll cap; edge(int to,ll cap, int rev) :to(to), cap(cap), rev(rev){} }; vector<edge> G[5015]; int level[5015]; int iter[5015]; 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)); } void bfs(int s) { memset(level, -1, sizeof(level)); queue<int> que; level[s] = 0; que.push(s); while (!que.empty()) { int v = que.front(); que.pop(); for (int i = 0; i < G[v].size(); ++i) { edge& e = G[v][i]; if (e.cap > 0 && level[e.to] < 0) { level[e.to] = level[v] + 1; que.push(e.to); } } } } ll dfs(int v, int t, ll f) { if (v == t){ return f;} for (int& i = iter[v]; i < G[v].size(); ++i) { edge& e = G[v][i]; if (e.cap > 0 && level[v] < level[e.to]) { ll 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; } ll max_flow(int s, int t) { ll flow = 0; for (;;) { bfs(s); if (level[t] < 0){ return flow; } memset(iter, 0, sizeof(iter)); ll f; while ((f = dfs(s, t, 0x3f3f3f3f3f3f3f3f)) > 0) { flow += f; } } } int vertex_count, visited[MAX_V]; // 遍历残余网络 void solve(int v) { ++vertex_count; visited[v] = true; for (int i = 0; i < int(G[v].size()); ++i) { const edge &e = G[v][i]; if (e.cap > 0 && !visited[e.to]) { solve(e.to); } } } int main(void) { int n, m, w; ll W = 0; scanf("%d%d", &n, &m); const int s = 0, t = n + 1; for (int i = 1; i <= n; i++) { scanf("%d", &w); if (w > 0) { W += w; add_edge(s, i, w); } if (w < 0) { add_edge(i, t, -w); } } int u, v; for (int i = 0; i < m; ++i) { scanf("%d%d", &u, &v); add_edge(u, v, 0x3f3f3f3f3f3f3f3f); } ll max_profit = W - max_flow(s, t); solve(s); printf("%d %I64d\n", --vertex_count, max_profit); return 0; }
题意：求无向图的最小割。
思路：Stoer-Wagner算法
哎这道题还是一头雾水，还是先码上，滚去复习图论的知识点了 555 菜到无法呼吸
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define MAX_N 500 + 16 #define INF 0x3f3f3f3f int G[MAX_N][MAX_N]; int v[MAX_N]; // v[i]代表节点i合并到的顶点 int w[MAX_N]; // 定义w(A,x) = ∑w(v[i],x)，v[i]∈A bool visited[MAX_N]; // 用来标记是否该点加入了A集合 int stoer_wagner(int n) { int min_cut = INF; for (int i = 0; i < n; ++i) { v[i] = i; // 初始还未合并，都代表节点本身 } while (n > 1) { int pre = 0; // pre用来表示之前加入A集合的点（在t之前一个加进去的点） memset(visited, 0, sizeof(visited)); memset(w, 0, sizeof(w)); for (int i = 1; i < n; ++i) { int k = -1; for (int j = 1; j < n; ++j) // 选取V-A中的w(A,x)最大的点x加入集合 { if (!visited[v[j]]) { w[v[j]] += G[v[pre]][v[j]]; if (k == -1 || w[v[k]] < w[v[j]]) { k = j; } } } visited[v[k]] = true; // 标记该点x已经加入A集合 if (i == n - 1) // 若|A|=|V|（所有点都加入了A），结束 { const int s = v[pre], t = v[k]; // 令倒数第二个加入A的点（v[pre]）为s，最后一个加入A的点（v[k]）为t min_cut = min(min_cut, w[t]); // 则s-t最小割为w(A,t)，用其更新min_cut for (int j = 0; j < n; ++j) // Contract(s, t) { G[s][v[j]] += G[v[j]][t]; G[v[j]][s] += G[v[j]][t]; } v[k] = v[--n]; // 删除最后一个点（即删除t，也即将t合并到s） } // else 继续 pre = k; } } return min_cut; } int main() { int n, m; while (scanf("%d%d", &n, &m) != EOF) { memset(G, 0, sizeof(G)); while (m--) { int u, v, w; scanf("%d%d%d", &u, &v, &w); G[u][v] += w; G[v][u] += w; } printf("%d\n", stoer_wagner(n)); } return 0; }
原文：https://www.cnblogs.com/jaszzz/p/13061936.html