[原创]图论 [未完成 待续~待修改]

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)O(n^{2})

vector

vectorG[N];
G[i][j] 表示有一条i->j的有向边

1
2
3
void add(int u,int v){
G[u].push_back(v);
}

空间复杂度O(e)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)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;
}

树被定义为没有圈的连通图,具有以下几个性质:

  1. 在树中去掉一条边后所得的图是不连通的。
  2. 在树中添加一条边后所得的图一定存在圈。
  3. 树的每一对顶点 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;
}