Hexo
0%

Posted on In ,
Symbols count in article: 5k Reading time ≈ 5 mins.

网络流

  • 有向图G(V,E)
  • 有且仅有一个顶点S，它的入度为0，称为源点
  • 有且仅有一个顶点T，它的出度为0，称为汇点
  • 每一条弧都有非负数，叫做该边的容量；
  • 称为网络流图，记为G=(V,E,C)

网络流模型例子

想要将一些水从S运到T，必须经过一些水站，连接水站的是管道，每条管道都有它的最大能容纳的水量，求S到T最多能流多少流量。

可行流

  • 每一条狐，都有$\ f[i][j] \ \le\ c[i][j]\ $；即对于每条边，流经该边的流量不得超过该边的容量(不撑爆水管)。
  • 流量平衡：除源点S和汇点T以外的所有的点vi，即流入的流量等于流出的流量，即中转点不截流量
  • 对于源点S和汇点T有：S流出的流量等于T流入的流量

增广路

增广路上的弧的流量通过一定规则的修改，可以令整个流量放大，也就是多流流量

  • 可行流中，若$\ f[i][j]\ =\ c[i][j]\ $ ,则称$<v_i,v_j>$为饱和弧，否则为非饱和弧。若$f[i][j] \ = \ 0$，则称为零流弧，否则称为非零流弧

最大流

Read more »

Posted on In ,
Symbols count in article: 893 Reading time ≈ 1 mins.

拓扑排序

给一个有向无环图排序

每次删除一个入度边个数为 0 的点，并刷新其他点的出度边个数

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
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=2e4+10;
#define p 80112002
int n,m;
vector<int>se[maxn];
int in[maxn],out[maxn];
queue<int>line;
ll dp[maxn];

int main()
{
   cin>>n>>m;
   for(int i=1;i<=m;++i)
   {
    int a,b;
    cin>>a>>b;
    se[b].push_back(a);
    ++in[a];//入度
    ++out[b];//出度
   }
   for(int i=1;i<=n;++i)
   {
    if(!in[i])
    {
    dp[i] = 1;
    line.push(i);//放入度为0的点
    }
   }
    
   while(!line.empty())
   {
    int now = line.front();
    line.pop();
    for(int i=0;i<se[now].size();++i)
    {
      int next = se[now][i];
      --in[next];
      dp[next] = (dp[now] + dp[next])%p;
      if(!in[next])
      {
        line.push(next);
      }
    }
   }
   ll sum=0;
   for(int i=1;i<=n;++i)
   {
    if(!out[i])
    {
      sum = (sum+dp[i])%p;
    }
   }
   cout<<sum<<endl;
}
Read more »

Posted on In ,
Symbols count in article: 1.4k Reading time ≈ 1 mins.

双向bfs

适用于知道起点和终点的状态下使用，从两个方向开始bfs，

可以设置两个队列，一个队列保存从起点开始搜索的状态，另一个队列用来保存从终点开始搜索的状态，如果某一个状态下出现相交的情况，那么就出现了答案

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
#include <iostream>
#include <queue>
#define P pair<int, int>
using namespace std;
//记录下当前状态, 从前往后搜索值为1，从后往前搜索值为2，如果某状态下，当前节点和准备扩展节点的状态相加为3，说明相遇
queue <P> q1, q2; 
int r, c, ans, dis[45][45], vst[45][45];
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
char m[45][45];

void dbfs() {
	bool flag;
	q1.push(P(1, 1)), dis[1][1] = 1, vst[1][1] = 1; //从前搜
	q2.push(P(r, c)), dis[r][c] = 1, vst[r][c] = 2; //从后搜
	while(!q1.empty() && !q2.empty()) {
		int x0, y0;
		if(q1.size() > q2.size()) { //每次扩展搜索树小的队列 flag=1扩展前搜的队列，flag=0扩展后搜的队列
			x0 = q2.front().first, y0 = q2.front().second;
			q2.pop();
			flag = 0;
		}else {
			x0 = q1.front().first, y0 = q1.front().second;
			q1.pop();
			flag = 1;
		}
		for(int i = 0; i < 4; i++) {
			int nx = x0 + dx[i];
			int ny = y0 + dy[i];
			if(nx >= 1 && nx <= r && ny >= 1 && ny <= c && m[nx][ny] == '.') {
				if(!dis[nx][ny]) {
					dis[nx][ny] = dis[x0][y0] + 1;
					vst[nx][ny] = vst[x0][y0];
					if(flag) q1.push(P(nx, ny));
					else q2.push(P(nx, ny));
				}else {
					if(vst[x0][y0] + vst[nx][ny]== 3) { //相遇
						ans = dis[nx][ny] + dis[x0][y0];
						return;
					}
				}
			}
		}
	}
}

int main() {
	cin >> r >> c;
	for(int i = 1; i <= r; i++)
		for(int j = 1; j <= c; j++)
			cin >> m[i][j];
	dbfs(); 
	cout << ans << "\n";
	return 0;
}


Read more »

Posted on In ,
Symbols count in article: 1.6k Reading time ≈ 1 mins.

欧拉图

欧拉回路：通过图中每条边恰好一次的回路

欧拉通路：通过图中每条边恰好一次的通路

欧拉图：具有欧拉回路的图

半欧拉图：具有欧拉通路但不具有欧拉回路的图

欧拉图中所有顶点的度数都是偶数

  • 无向图是欧拉图当且仅当：

    • 非零度顶点是连通的

    • 顶点的度数都是偶数

  • 无向图是半欧拉图当且仅当：

    • 非零度顶点是连通的

    • 恰有 2 个奇度顶点

  • 有向图是欧拉图当且仅当：

    • 非零度顶点是强连通的

    • 每个顶点的入度和出度相等

  • 有向图是半欧拉图当且仅当：

    • 非零度顶点是弱连通的

    • 至多一个顶点的出度与入度之差为 1

    • 至多一个顶点的入度与出度之差为 1

    • 其他顶点的入度和出度相等

求欧拉回路

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
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
int ans[200];
int top;
int N,M;
int mp[200][200];
void dfs(int x)
{
    int i;
    top++;
    ans[top]=x;
    for (i=1; i<=N; i++)
    {
        if(mp[x][i]>0)
        {
            mp[x][i]=mp[i][x]=0;///删除此边
            dfs(i);
            break;
        }
    }
}

void fleury(int x)
{
    int brige,i;
    top=1;
    ans[top]=x;///将起点放入Euler路径中
    while(top>=0)
    {
        brige=0;
        for (i=1; i<=N; i++) /// 试图搜索一条边不是割边（桥）
        {
            if(mp[ans[top]][i]>0)///存在一条可以扩展的边
            {
                brige=1;
                break;
            }
        }
        if (!brige)/// 如果没有点可以扩展，输出并出栈
        {
            printf("%d ", ans[top]);
            top--;
        }
        else     /// 否则继续搜索欧拉路径
        {
            top--;///为了回溯
            dfs(ans[top+1]);
        }
    }
}

int main()
{
    int x,y,deg,num,start,i,j;
    scanf("%d%d",&N,&M);
    memset(mp,0,sizeof (mp));
    for(i=1;i<=M; i++)
    {
        scanf("%d%d",&x,&y);
        mp[x][y]=1;
        mp[y][x]=1;
    }
    num=0;
    start=1;///这里初始化为1
    for(i=1; i<=N; i++)
    {
        deg=0;
        for(j=1; j<=N; j++)
        {
            deg+=mp[i][j];
        }
        if(deg%2==1)///奇度顶点
        {
            start=i;
            num++;
        }
    }
    if(num==0||num==2)
    {
        fleury(start);
    }
    else
    {
        puts("No Euler path");
    }
    return 0;
}
Read more »

Posted on In , ,
Symbols count in article: 2.4k Reading time ≈ 2 mins.

最短路径

Floyd算法

不能有负环

适用于任何图

1
2
3
4
5
6
7
for (k = 1; k <= n; k++) {
  for (x = 1; x <= n; x++) {
    for (y = 1; y <= n; y++) {
      f[x][y] = min(f[x][y], f[x][k] + f[k][y]);
    }
  }
}

Bellman-Ford算法

可以求出有负权的图的最短路，并可以对最短路不存在的情况进行判断

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
struct Edge {
  int u, v, w;
};

vector<Edge> edge;

int dis[MAXN], u, v, w;
const int INF = 0x3f3f3f3f;

bool bellmanford(int n, int s) {
  memset(dis, 0x3f, sizeof(dis));
  dis[s] = 0;
  bool flag = false;  // 判断一轮循环过程中是否发生松弛操作
  for (int i = 1; i <= n; i++) {
    flag = false;
    for (int j = 0; j < edge.size(); j++) {
      u = edge[j].u, v = edge[j].v, w = edge[j].w;
      if (dis[u] == INF) continue;
      // 无穷大与常数加减仍然为无穷大
      // 因此最短路长度为 INF 的点引出的边不可能发生松弛操作
      if (dis[v] > dis[u] + w) {
        dis[v] = dis[u] + w;
        flag = true;
      }
    }
    // 没有可以松弛的边时就停止算法
    if (!flag) {
      break;
    }
  }
  // 第 n 轮循环仍然可以松弛时说明 s 点可以抵达一个负环
  return flag;
}

队列优化

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
struct edge {
  int v, w;
};

vector<edge> e[maxn];
int dis[maxn], cnt[maxn], vis[maxn];
queue<int> q;

bool spfa(int n, int s) {
  memset(dis, 63, sizeof(dis));
  dis[s] = 0, vis[s] = 1;
  q.push(s);
  while (!q.empty()) {
    int u = q.front();
    q.pop(), vis[u] = 0;
    for (auto ed : e[u]) {
      int v = ed.v, w = ed.w;
      if (dis[v] > dis[u] + w) {
        dis[v] = dis[u] + w;
        cnt[v] = cnt[u] + 1;  // 记录最短路经过的边数
        if (cnt[v] >= n) return false;
        // 在不经过负环的情况下，最短路至多经过 n - 1 条边
        // 因此如果经过了多于 n 条边，一定说明经过了负环
        if (!vis[v]) q.push(v), vis[v] = 1;
      }
    }
  }
  return true;
}

Dijkstra算法

Read more »