[原创]图论 [未完成 待续~待修改]
2017-01-26 21:45:01 Tabris_ 阅读数:473
博客爬取于2020-06-14 22:39:11
以下为正文
版权声明:本文为Tabris原创文章,未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/54746580
#图
图的表示方法
矩阵
二维数组 map[i][j] 表示i到j的边 值为边得大小 ,定义一个值代表不存在这条边 一般为0
空间复杂度O(n2)
vector
vectorG[N];
G[i][j] 表示有一条i->j的有向边
1 2 3
| void add(int u,int v){ G[u].push_back(v); }
|
空间复杂度O(e)
前向星
1 2 3 4 5 6 7
| struct edge{ int to,next,w; }G[N<<1]; int head[N],tot; void add(int u,int v,int w){ G[tot].w=w,G[tot].to=v,G[tot].next=head[u],head[u]=tot++; }
|
空间复杂度O(e)
最短路
floyd
不解释
dijkstra
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33
| vector<pair<int ,int > >G[N]; int d[N];
int main(){
while(~scanf("%d%d",&m,&n)){ for(int i=1;i<=n;i++)d[i]=2e9+7,G[i].clear(); d[n]=0; for(int i=1,u,v,w;i<=m;i++){ scanf("%d%d%d",&u,&v,&w); G[u].push_back(make_pair(v,w)); G[v].push_back(make_pair(u,w)); }
priority_queue<pair<int ,int> >q; q.push(make_pair(-d[n],n)); while(!q.empty()){ int u =q.top().second;q.pop(); for(int i=0,v;i<G[u].size();i++){ v=G[u][i].first; if(d[v]>d[u]+G[u][i].second){ d[v]=d[u]+G[u][i].second; q.push(make_pair(-d[v],v)); } }
} if(d[n]==2e9+7) puts("-1"); else printf("%d\n",d[1]);
} return 0; }
|
SPFA
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
| LL d[N]; int inq[N],n,m,q; LL spfa(int s,int t){ for(int i=1;i<=n;i++) d[i]=2e14+7,inq[i]=0;
queue<int >q; q.push(s);d[s]=0,inq[s]=1; while(!q.empty()){ int u =q.front();q.pop(); inq[u]=0; for(int i=head[u],v;i!=-1;i=G[i].next){ v=G[i].to; if(d[v]>d[u]+G[i].w){ d[v]=d[u]+G[i].w; if(inq[v]==1) continue; inq[v]=1; q.push(v); } } }
return d[t]; }
|
强连通
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54
| vector<int>G[N]; vector<pair<int,int> >G2[N];
int low[N],dfn[N],w[N],d[N]; int vis[N],val[N]; int color[N],cnt,tot; int mystack[N],len;
void dfs(int u){vis[u]=1; dfn[u]=low[u]=++cnt; mystack[++len]=u; int gz=G[u].size(); for(int to,i=0;i<gz;i++){ to=G[u][i]; if(vis[to]==0) dfs(to); if(vis[to]==1) low[u]=min(low[u],low[to]); }
if(dfn[u]==low[u]){ ++tot; do{ val[tot]+=w[mystack[len]]; color[mystack[len]]=tot; vis[mystack[len]]=2; }while(mystack[len--]!=u); } }
int n,m; int main(){ scanf("%d%d",&n,&m); cnt=tot=len=0; for(int i=1;i<=n;i++) scanf("%d",&w[i]);
for(int i=1,u,v;i<=m;i++){ scanf("%d%d",&u,&v); G[u].push_back(v); //看是有向图还是无向图 }
//缩点 for(int i=1;i<=n;i++) if(vis[i]==0)dfs(i);
//建新图
for(int i=1,gz;i<=n;i++){vis[i]=0,d[i]=0; gz=G[i].size(); for(int j=0,to;j<gz;j++){ to=G[i][j]; if(color[i]!=color[to]) G2[color[i]].push_back(make_pair(val[color[to]],color[to])); } } return 0; }
|
二分图匹配
算法介绍
最大匹配数:最大匹配的匹配边的数目
最小点覆盖数:选取最少的点,使任意一条边至少有一个端点被选择
最大独立数:选取最多的点,使任意所选两点均不相连
最小路径覆盖数:对于一个 DAG(有向无环图),选取最少条路径,使得每个顶点属于且仅属于一条路径。路径长可以为 0(即单个点)。
定理1:最小点覆盖数 = 最大匹配数(这是 Konig 定理)
定理2:最大独立数 = 顶点数 - 最大匹配数
定理3:最小路径覆盖数 = 顶点数 - 最大匹配数
匈牙利算法求解二分图匹配问题
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85
| int k,n,m; int match[N]; int vis[N]; vector<int >G[N];
int tot,a; int col[N]; //二分图染色 用来判断是不是二分图 bool color(int s){ queue<int>q; q.push(s);col[s]=1; while(!q.empty()){ int u = q.front();q.pop(); tot++; if(col[u]==1) a++; int gz=G[u].size(); for(int i=0,to;i<gz;i++){ to=G[u][i]; if(col[to]==0){ col[to]=3-col[u]; q.push(to); } else if(col[to]==col[u]) return false; } } return true; }
bool findi(int u){ for(int i=0;i<G[u].size();i++){ int v=G[u][i]; if(vis[v]==0){ vis[v]=1; if(match[v]==-1||findi(match[v])){ match[v]=u; return true; } } } return false; }
void init(){ memset(match,-1,sizeof(match)); for(int i=1;i<=n;i++) G[i].clear(),col[i]=vis[i]=0; }
void add(int u,int v){ G[u].push_back(v); G[v].push_back(u); //无向图才需要 }
int maxMATCH(){ int ans = 0; //ans 是最大匹配数, for(int i=1;i<=n;i++){ memset(vis,0,sizeof(vis)); if(findi(i)) ans++; } ans/=2; //对于无向图的话 需要ans/=2; return ans ; }
bool perfectMATCH(){ if(maxMATCH()==n) return true; else return false; }
int main(){ int _; scanf("%d",&_); while(_--){ scanf("%d%d",&n,&m); init();a=0; for(int i=1,u,v;i<=m;i++){ scanf("%d%d",&u,&v); add(u,v); } /**** 根据题意进行balabala */ } return 0; }
|
2-SAT
强连通分支及其应用(2-SAT)总结
2-SAT
强联通分量一个很重要的用途就是解布尔方程可满足性问题(SAT)。需要学习这一部分知识我们需要一点布尔代数的知识。
下文中我们约定(^表示交v表示并)
例如:(a v b v …)^(c v d v …)^…
这样的我们叫做合取范式。其中(a v b v …)这样的叫做子句。类似a,b…叫做文字。
我们把合取范式中一个子句中包含文字不超过两个的问题成为2-SAT问题。在SAT问题中只有这一类我们可以用线性时间内得出答案。
最常规的2-SAT题目分为大致两种,一种是让你判断有没有解,另一种是让你输出一组解。针对这两种给出模版。
在这之前先来介绍一下2-SAT题目的大致解题步骤:
对于2-SAT问题我们需要构建一张有向图每个文字拆为两个节点 例如 a 变为 a, !a
首先我们从题目中总结出来的都是一些比较杂乱的逻辑表达式,不过一般都是两两之间的关系,我们需要做的第一步是化简成用^连接。然后对于每个子句建边。
建边的规则是这样的 a -> b那么在有向图中建一条a到b的边
我们可能得到的子句有:
a v b 我们可以化简 !a->b ^ !b->a
a -> b 直接连边
a 转化为!a -> a
其中每个文字及其的非对应相应的结点,若是出现在文字前有非的关系例如 !a v b 那么变通一下 就化成 a -> b ^ !b -> !a就可以了。
到这里我们要做的事(建图)就完成了,接下来交给模版,我们来看一下模版做了什么:
首先我们对建完的有向图求强连通分支,若是出现有一个逻辑变量和他的反在同一个联通分之内就无解,否则有解。
若a所在的强连通分支的拓扑序在!a之后a为真,否则为反。怎么样很简单吧。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129
| vector<int> G[N]; vector<int> G2[N];
vector<int> S; int vis[N] ; //标记数组 int sccno[N]; //记录数组 sccno[i] 记录 i属于哪个联通分支 int scc_cnt;
int n;
void dfs1(int u){ if(vis[u]) return ; vis[u] = true; for(int i = 0; i < G[u].size(); i++){ dfs1(G[u][i]); } S.push_back(u); }
void dfs2(int u){ if(sccno[u]) return; sccno[u] = scc_cnt; for(int i = 0; i < G2[u].size(); i++){ dfs2(G2[u][i]); } }
void find_scc(int n){ scc_cnt = 0; S.clear(); memset(vis , 0 , sizeof(vis)); memset(sccno , 0 , sizeof(sccno)); for(int i = 0; i < n; i++) dfs1(i); for(int i = n - 1; i >= 0; i--) if(!sccno[S[i]]){ scc_cnt++; dfs2(S[i]); } }
void AddEdge(int u , int v) { G[u].push_back(v); G2[v].push_back(u); }
int main(){ /*** 输入数据 */
/*** 加边 边未两者不能匹配的 example : {u,v} 当选择u的时候一定不能选择v ,需要选择v'; */
find_scc(2 * n); //注意x2
for(int i = 0; i < n; i++){ if(sccno[i] == sccno[i + n]){ //如果有x与x'同时被取或者未取,则匹配失败 puts("NO"); return 0; } }
puts("YES"); for(int i = 0; i < n; i++){ if(sccno[i] > sccno[i + n]){ //相关 i; } else { //相关 i'; } } return 0; } /********************************************************/ /**************************************** 2-SAT kosaraju算法 By 小豪 *****************************************/ const int LEN = 200000+10; vector<int> Map[LEN], rMap[LEN], vs; int n, m, vis[LEN], sccn[LEN];
void dfs(int v){ vis[v] = 1; for(int i=0; i<Map[v].size(); i++) if(!vis[Map[v][i]]) dfs(Map[v][i]); vs.PB(v); }
void rdfs(int v, int f){ vis[v] = 1; sccn[v] = f; for(int i=0; i<rMap[v].size(); i++) if(!vis[rMap[v][i]]) rdfs(rMap[v][i], f); }
int scc(){ memset(vis, 0, sizeof vis); vs.clear(); for(int i=0; i<2*n; i++) if(!vis[i]) dfs(i); memset(vis, 0, sizeof vis); int k = 0; for(int i = vs.size()-1; i>=0; i--) if(!vis[vs[i]]) rdfs(vs[i], k++); return k; }
void addedge(int a, int b){ Map[a].PB(b); rMap[b].PB(a); }
void solve() { scc(); for(int i=0; i<2*n; i+=2) if(sccn[i] == sccn[i+1]){ //printf("No solution.\n"); //无解 return ; } for(int i=0; i<n; i++){ if(sccn[i*2] > sccn[i*2+1]) printf("Yes\n"); else printf("No\n"); } }
|
网络流
网络流各种骚操作
dinic(没有当前弧优化
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76
| const int MAXN = 210; const int MAXM = 210*210; const int INF = 0x3f3f3f3f;
struct Edge { int v, f; int next; } edge[MAXM];
int n, m; int cnt;
int head[MAXN], level[MAXN]; int q[MAXN];
void read_graph(int u, int v, int f) { edge[cnt].v = v, edge[cnt].f = f; edge[cnt].next = head[u], head[u] = cnt++; edge[cnt].v = u, edge[cnt].f = 0; //增加一条反向弧,容量为0 edge[cnt].next = head[v], head[v] = cnt++; } //BFS构建层次网络: int bfs(int s, int t) { //构建层次网络 memset(level, 0, sizeof(level)); level[s] = 1; int front = 0, rear = 1; q[front] = s; while(front < rear) { int x = q[front++]; if(x == t) return 1; for(int e = head[x]; e != -1; e = edge[e].next) { int v = edge[e].v, f = edge[e].f; if(!level[v] && f) { level[v] = level[x] + 1; q[rear++] = v; } } } return 0; } //DFS找寻增广路: int dfs(int u, int maxf, int t) { if(u == t) return maxf; int ret = 0; for(int e = head[u]; e != -1; e = edge[e].next) { int v = edge[e].v, f = edge[e].f; if(level[u] + 1 == level[v] && f) { int Min = min(maxf-ret, f); f = dfs(v, Min, t); edge[e].f -= f; edge[e^1].f += f; ret += f; if(ret == maxf) return ret; } } return ret; }
int Dinic(int s, int t) { //Dinic int ans = 0; while(bfs(s, t)) ans += dfs(s, INF, t); return ans; }
int main() { while(~scanf("%d%d",&m,&n)){ cnt = 0; memset(head, -1, sizeof(head)); for(int x,y,v;m--;){ scanf("%d%d%d",&x,&y,&v); read_graph(x,y,v); } printf("%d\n",Dinic(1,n)); } return 0; }
|
树
树被定义为没有圈的连通图,具有以下几个性质:
- 在树中去掉一条边后所得的图是不连通的。
- 在树中添加一条边后所得的图一定存在圈。
- 树的每一对顶点 U 和 V 之间有且仅有一条路径。
树的直径
树的直径(Diameter)是指树上的最长简单路。
直径的求法:两遍搜索 (BFS or DFS)
任选一点w为起点,对树进行搜索,找出离w最远的点u。
以u为起点,再进行搜索,找出离u最远的点v。则u到v的路径长度即为树的直径。
树的重心
树的重心:找到一个点,其所有的子树中最大的子树节点数最少,那么这个点就是这棵树的重心,删去重心后,生成的多棵树尽可能平衡。
树的重心可以通过简单的两次搜索求出,第一遍搜索求出每个结点的子结点数量son[u],第二遍搜索找出使max{son[u],n-son[u]-1}最小的结点。
实际上这两步操作可以在一次遍历中解决。对结点u的每一个儿子v,递归的处理v,求出son[v],然后判断是否是结点数最多的子树,处理完所有子结点后,判断u是否为重心。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39
| 例题 1655
int n;
vector<int >G[N]; void add(int u,int v){G[u].push_back(v);}
int sz[N],siz,zx;
void dfs(int u,int f=0){ sz[u]=1;int mx=0; int gz=G[u].size(); for(int i=0,to;i<gz;i++){ to = G[u][i]; if(to == f) continue; dfs(to,u); sz[u]+=sz[to]; mx=max(mx,sz[to]); } mx=max(mx,n-sz[u]); if(mx==siz&&u<zx) zx=u; if(mx<siz) zx=u,siz=mx; }
int main(){ int _; for(scanf("%d",&_);_--;){ scanf("%d",&n); for(int i=1,u,v;i<n;i++){ scanf("%d%d",&u,&v); add(u,v);add(v,u); } siz = n*10; dfs(1); printf("%d %d\n",zx,siz); for(int i=1;i<=n;i++) G[i].clear(); } return 0; }
|