Hexo
0%

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

分层图

当我们要进行图的遍历的时候，有时会进行状态的变化，此时我们可以开多个维度的图，每种维度代表一种状态，当状态改变时就可以转移到另一个维度进行推进；

1.wyh的吃鸡

假设地图为n*n的一个图，图中有且仅有一块X的联通快代表安全区域，有一个起点S代表缩圈的时候的起点，图中C代表的是车（保证车的数量小于等于100），标记为.的代表空地，可以任意通过，O代表障碍物不能通过。每次没有车的时候2s可以走一个格（只能走自己的上下左右4个方向），有车的话时间为1s走一个格

现在告诉你最多能坚持的时间为t秒，问你在t秒内（含t秒）能否从s点到达安全区域，能的话输出YES，并且输出最短时间，不能的话输出NO。

此题为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
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
# include <bits/stdc++.h>
using namespace std;
#define LL long long
LL int n,k;
int sx,sy;
char ju[105][105];//保存图形
bool ask[3][105][105];//标记（第一个维度为不同状态，后面两个维度为坐标）
bool pd[105][105];
struct note{
    int x,y;//坐标
    int s;//时间
    int c;//状态
    inline bool operator < (const note& p) const{
        return s>p.s;
    }
};
//方向
int ax[5],ay[5];

void Clear()
{
    memset(pd,0,sizeof pd);
    memset(ask,0,sizeof ask);
}
int main()

{
    ax[1]=-1,ay[1]=0;//zuo
    ax[2]=1,ay[2]=0;//you
    ax[3]=0,ay[3]=-1;//shang
    ax[4]=0,ay[4]=1;//xia
    int t;
    cin>>t;
    while(t--)
    {
        Clear();
        cin>>n>>k;
        for(int i=0;i<n;++i)
            cin>>ju[i];
        for(int i=0;i<n;++i)
        {
            for(int j=0;j<n;++j)
            {
                if(ju[i][j]=='S')
                {
                    sx=i;
                    sy=j;
                }
            }
        }
        int sum=1e9;
        priority_queue<note>q;
        q.push(note{sx,sy,0,2});
        while(!q.empty())//bfs
        {
            note tmp=q.top();
            q.pop();
            int x=tmp.x, y=tmp.y;
            
            if(ask[tmp.c][x][y]||ju[x][y]=='O')
                continue;
            if(x<0||x>=n||y<0||y>=n) 
                continue;//cout<<tmp.c<<" "<<x<<" "<<y<<" "<<tmp.s<<endl;
            if(ju[x][y]=='X'){
                sum=min(sum,tmp.s);//找到更小的
                continue;
            }
            ask[tmp.c][x][y]=1;
            int c=2;
            if(ju[x][y]=='C')
                c=1;//状态改变
            for(int i=1;i<=4;++i){
                int tx=x+ax[i], ty=y+ay[i];
                q.push({tx,ty,tmp.s+min(tmp.c,c),min(tmp.c,c)});
            }
        }
        if(sum<=k)
            cout<<"YES"<<"\n"<<sum<<"\n";
        else
            cout<<"NO"<<"\n";
    }
}

2.对于每个点都可以选择下一条边是否赋予权值为0,那么我们就可以将图画出k+1层1

代码实现：

我们可以将dis数组开成二维dis[i][j]表示到达i号结点,用了j次免费操作!
比如dis[2][0]表示到达2号结点,没有用免费操作,也就是在第一层图移动。 比如dis[2][3],到达2号结点用了3次免费操作,那么**下一次移动应该在第3/4层图进行!**、

Read more »

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

二分图最大权匹配

二分图中边权和最大的匹配

匈牙利算法

n个顶点，算法复杂度为O（nnn）

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
#include<cstdio>
#include<cstring>
#include<iostream>
#include<queue>
#include<vector>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=505;
int line[N][N];
int girl[N],used[N];
int k,m,n;
bool found(int x)
{
    for(int i=1; i<=n; i++)
    {
        if(line[x][i]&&!used[i])
        {
            used[i]=1;
            if(girl[i]==0||found(girl[i]))
            {
                girl[i]=x;
                return 1;
            }
        }
    }
    return 0;
}
int main()
{
    int x,y;
    while(scanf("%d",&k)&&k)
    {
        scanf("%d %d",&m,&n);
        memset(line,0,sizeof(line));
        memset(girl,0,sizeof(girl));
        for(int i=0; i<k; i++)
        {
            scanf("%d %d",&x,&y);
            line[x][y]=1;
        }
        int sum=0;
        for(int i=1; i<=m; i++)
        {
            memset(used,0,sizeof(used));
            if(found(i)) sum++;
        }
        printf("%d\n",sum);
    }
    return 0;
}
Read more »

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

二分图最大匹配

假定图有n个顶点，m条边

给定一个二分图，有左右两个部分，各部分之间的点没有边连接，要求选出一些边，使得这些边没有公共顶点，且边的数量最大

O（nm）

增广路算法

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
struct augment_path {
  vector<vector<int> > g;
  vector<int> pa;  // 匹配
  vector<int> pb;
  vector<int> vis;  // 访问
  int n, m;         // 两个点集中的顶点数量
  int dfn;          // 时间戳记
  int res;          // 匹配数

  augment_path(int _n, int _m) : n(_n), m(_m) {
    assert(0 <= n && 0 <= m);
    pa = vector<int>(n, -1);
    pb = vector<int>(m, -1);
    vis = vector<int>(n);
    g.resize(n);
    res = 0;
    dfn = 0;
  }

  void add(int from, int to) {
    assert(0 <= from && from < n && 0 <= to && to < m);
    g[from].push_back(to);
  }

  bool dfs(int v) {
    vis[v] = dfn;
    for (int u : g[v]) {
      if (pb[u] == -1) {
        pb[u] = v;
        pa[v] = u;
        return true;
      }
    }
    for (int u : g[v]) {
      if (vis[pb[u]] != dfn && dfs(pb[u])) {
        pa[v] = u;
        pb[u] = v;
        return true;
      }
    }
    return false;
  }

  int solve() {
    while (true) {
      dfn++;
      int cnt = 0;
      for (int i = 0; i < n; i++) {
        if (pa[i] == -1 && dfs(i)) {
          cnt++;
        }
      }
      if (cnt == 0) {
        break;
      }
      res += cnt;
    }
    return res;
  }
};
Read more »

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

最近公共祖先LCA

倍增算法

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
#include<bits/stdc++.h>
using namespace std;
#define N 500005
#define endl "\n"
int head[N], to[N<<1], nex[N<<1], cnt=1;
int fa[N][21], dep[N];
void add(int x, int y){
	to[cnt] = y;
	nex[cnt] = head[x];
	head[x] = cnt++;
}
void dfs(int rt, int f){
	dep[rt] = dep[f] + 1;
	fa[rt][0] = f;
	for(int i = 1; (1 << i) <= dep[rt]; i++){ //进制由小到大递推 
		fa[rt][i] = fa[fa[rt][i - 1]][i - 1];
	}
	for(int i = head[rt]; i; i = nex[i]){
		if(to[i] == f){
			continue;
		}
		dfs(to[i], rt);
	}
}
int LCA(int x, int y){
	if(dep[x] < dep[y]){
		swap(x, y);
	}
	for(int i = 20; i >= 0; i--){ //进制由大到小开始组合 
		if(dep[fa[x][i]] >= dep[y]){
			x = fa[x][i];
		}
	} 
	if(x == y){ //注意特判 
		return x;
	}
	for(int i = 20; i >= 0; i--){ //进制从小到大开始组合 
		if(fa[x][i] != fa[y][i]){
			x = fa[x][i];
			y = fa[y][i];
		}
	}
	return fa[x][0]; //这一步尤其考虑，为什么x,y不是LCA，二期父节点一定是LCA 
}
int main(){
	ios::sync_with_stdio(false);
	int n, m, s;
	while(cin >> n >> m >> s){
		memset(head, 0, sizeof(head));
		cnt = 1;
		int x, y;
		for(int i = 0; i < n - 1; i++){
			cin >> x >> y;
			add(x, y);
			add(y, x);
		}
		dfs(s, 0);
		for(int i = 0; i < m; i++){
			cin >> x >> y;
			cout << LCA(x, y) << endl;
		}
	}
	return 0;
}

Tarjan算法

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
#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
#define N 500005
int head[N], to[N<<1], nex[N<<1], cnt ;
int visit[N], fa[N];
int qhead[N<<1], qnex[N<<1], qcnt = 1, qid[N<<1], ans[N], qto[N<<1];
void add_edge(int x, int y){
	to[cnt] = y;
	nex[cnt] = head[x];
	head[x] = cnt++;
}
void add_query(int x, int y, int w){
	qto[qcnt] = y;
	qnex[qcnt] = qhead[x];
	qid[qcnt] = w;
	qhead[x] = qcnt++;
}
int findx(int x){
	if(fa[x] == x){
		return x;
	}
	return fa[x] = findx(fa[x]);
}
void tarjan(int rt, int f){
	for(int i = head[rt]; i; i = nex[i]){
		if(to[i] == f)continue;
		tarjan(to[i], rt);
		fa[to[i]] = rt;
	}
	visit[rt] = 1;
	for(int i = qhead[rt]; i; i = qnex[i]){
		if(visit[qto[i]] == 0)continue; 
		ans[qid[i]] = findx(qto[i]);
	}
	
}
int main(){
	ios::sync_with_stdio(false);
	int n, m, s;
	while(cin >> n >> m >> s){
		int x, y;
		memset(head, 0, sizeof(head));
		cnt = 1, qcnt = 1;
		memset(qhead, 0, sizeof(qhead));
		for(int i = 1; i < n; i++){
			cin >> x >> y;
			add_edge(x, y);
			add_edge(y, x);
			fa[i] = i;
		}
		fa[n] = n;
		for(int i = 1; i <= m; i++){
			cin >> x >> y;
			add_query(x, y, i);
			add_query(y, x, i);
		}
		tarjan(s, 0);
		for(int i = 1; i <= m; i++){
			cout << ans[i] << endl;
		}
	}
	return 0;
}
Read more »

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

树的重心

如果在树中选择某个节点并删除，这棵树将分为若干棵子树，统计子树节点数并记录最大值。取遍树上所有节点，使此最大值取到最小的节点被称为整个树的重心。

  • 树的重心如果不唯一，则至多有两个，且这两个重心相邻。
  • 以树的重心为根时，所有子树的大小都不超过整棵树大小的一半。
  • 树中所有点到某个点的距离和中，到重心的距离和是最小的；如果有两个重心，那么到它们的距离和一样。
  • 把两棵树通过一条边相连得到一棵新的树，那么新的树的重心在连接原来两棵树的重心的路径上。
  • 在一棵树上添加或删除一个叶子，那么它的重心最多只移动一条边的距离
Read more »