20186gdoi13

图论

Posted on Edited on In Valine:
Symbols count in article: 5k Reading time ≈ 5 mins.
Thematic003

单源最短路径

例题

例题1：LuoguP3371

例题2：LuoguP4779

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <bits/stdc++.h>
using namespace std;

struct Edge
  {
  	int y,z;
  };
struct Node
  {
  	int now,dis;
  	bool operator < (const Node &a) const
  	  {
  	  	return a.dis<dis;
	  }
  };
bool vis[100005];
vector <Edge> V[100005];
priority_queue <Node> Q;
int a,b,n,m,x,y,z,d[100005];

void Dijkstra(int start)
  {
  	for (int i=1;i<=n;i++) d[i]=99999999;
	d[start]=0;
	Q.push((Node){start,0});
	while (!Q.empty())
	  {
	  	int now=Q.top().now;
	  	Q.pop();
	  	if (vis[now]) continue;
	  	vis[now]=true;
	  	for (int i=0;i<V[now].size();i++)
	  	  {
	  	  	int next=V[now][i].y;
	  	  	int nfar=V[now][i].z;
	  	  	if (d[next]>d[now]+nfar) 
                          d[next]=d[now]+nfar,Q.push((Node){next,d[next]});
		  }
	  }
  }

int main()
  {
  	scanf("%d%d%d%d",&n,&m,&x,&y);
  	while (m--)
  	  {
  	  	scanf("%d%d%d",&a,&b,&z);
  	  	V[a].push_back((Edge){b,z});
  	  	V[b].push_back((Edge){a,z});
	  }
	Dijkstra(x);
	printf("%d",d[y]);
	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
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
#include <bits/stdc++.h>
using namespace std;

struct Edge
  {
  	int y,z;
  };
queue <int> Q;
bool vis[100005];
vector <Edge> V[500005];
int n,m,x,y,a,b,z,d[100005];

void SPFA(int start)
  {
  	for (int i=1;i<=n;i++) d[i]=99999999;
  	Q.push(start);
  	d[start]=0;
  	vis[start]=true;
  	while (!Q.empty())
  	  {
  	  	int now=Q.front();
  	  	Q.pop();
  	  	vis[now]=false;
  	  	for (int i=0;i<V[now].size();i++)
  	  	  {
  	  	  	int next=V[now][i].y;
  	  	  	int nfar=V[now][i].z;
  	  	  	if (d[next]>d[now]+nfar)
  	  	  	  {
  	  	  	  	d[next]=d[now]+nfar;
  	  	  	  	if (!vis[next]) vis[next]=true,Q.push(next);
			  }
		  }
	  }
  }

int main()
  {
  	scanf("%d%d%d%d",&n,&m,&x,&y);
  	while (m--)
  	  {
  	  	scanf("%d%d%d",&a,&b,&z);
  	  	V[a].push_back((Edge){b,z});
	  }
	SPFA(x);
	printf("%d",d[y]);
	return 0;
  }

强连通分量 & 缩点

例题：LuoguP2341

代码

全局变量

1
2
3
4
5
6
7
8
9
// Tarjan
stack <int> S;
bool inst[MAXN];
vector <int> V[MAXN];
int n,m,col,cnt,dfn[MAXN],low[MAXN],color[MAXN];

//Extra
int colt[MAXN];
vector <int> V2[MAXN];

初始化

1
2
3
4
5
6
7
8
9
10
11
void inti(void)
  {
    cnt=col=0;
  memset(dfn,0,sizeof(dfn));
    memset(low,0,sizeof(low));
    memset(colt,0,sizeof(colt));
  memset(color,0,sizeof(color));
    memset(inst,false,sizeof(inst));
    for (int i=0;i<MAXN;i++) V[i].clear();
    for (int i=0;i<MAXN;i++) V2[i].clear();
  }

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
void Tarjan(int now)
  {
    dfn[now]=low[now]=++cnt;
    inst[now]=true;
    S.push(now);
    for (int i=0;i<V[now].size();i++)
      {
        int next=V[now][i];
        if (!dfn[next])
          {
            Tarjan(next);
            low[now]=min(low[now],low[next]);
      }
    else if (inst[next]) low[now]=min(low[now],dfn[next]);
    }
  if (dfn[now]==low[now])
    {
      col++;
      int s;
      do
        {
          s=S.top();
          S.pop();
          inst[s]=false;
          color[s]=col;
            
          // Extra：记录每个强连通分量内的节点数 
          // colt[col]++;
            
      } while (s!=now);
    }
  }

Extra：重新建图

1
2
3
4
5
6
7
8
9
10
11
12
13
void ReGraph(void)
  {
    int acolor;
  for (int i=1;i<=n;i++)
    {
        acolor=color[i];
        for (int j=0;j<V[now].size();j++) 
          {
            bcolor=color[V[i][j]];
            if (acolor!=bcolor) V2[acolor].push_back(bcolor);
          }
      }
  }

主函数

1
2
3
4
5
6
7
8
9
int main()
  {
    inti();
  /* Input */
    for (int i=1;i<=n;i++) if (!dfn[i]) Tarjan(i); //Tarjan图不一定联通 
    // ReGraph();
    /* Output */
    return 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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <bits/stdc++.h>
using namespace std;

const int MAXN=10005;

stack <int> S;
bool inst[MAXN];
vector <int> V[MAXN];
int n,m,col,cnt,dfn[MAXN],low[MAXN],color[MAXN],colt[MAXN],du[MAXN];

void inti(void)
  {
    cnt=col=0;
    memset(du,0,sizeof(du));
    memset(dfn,0,sizeof(dfn));
    memset(low,0,sizeof(low));
    memset(colt,0,sizeof(colt));
    memset(color,0,sizeof(color));
    memset(inst,false,sizeof(inst));
    for (int i=0;i<MAXN;i++) V[i].clear();
  }

void Tarjan(int now)
  {
    dfn[now]=low[now]=++cnt;
    inst[now]=true;
    S.push(now);
    for (int i=0;i<V[now].size();i++)
      {
        int next=V[now][i];
        if (!dfn[next])
          {
            Tarjan(next);
            low[now]=min(low[now],low[next]);
      }
    else if (inst[next]) low[now]=min(low[now],dfn[next]);
    }
  if (dfn[now]==low[now])
    {
      col++;
      int s;
      do
        {
          s=S.top();
          S.pop();
          inst[s]=false;
          color[s]=col;
          colt[col]++;
      } while (s!=now);
    }
  }

void ReGraph(void)
  {
    for (int i=1;i<=n;i++)
    for (int j=0;j<V[i].size();j++)
      if (color[i]!=color[V[i][j]])
      du[color[i]]++;
  } 

int main()
  {
    int x,y,ans=0;
  inti();
    scanf("%d%d",&n,&m);
    while (m--)
      {
        int x,y;
    scanf("%d%d",&x,&y);
        V[x].push_back(y);
    }
  for (int i=1;i<=n;i++) if (!dfn[i]) Tarjan(i);
  ReGraph();
  for (int i=1;i<=col;i++) if (du[i]==0)
    {
        if (ans) return printf("0")&0;
      ans=colt[i];
    }
  return printf("%d",ans)&0;
  }

割点

例题：LuoguP3388

代码

Tarjan

1
2


割边

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void Tarjan(int now,int last)
  {
    dfn[now]=low[now]=++cnt;
    for (int i=0;i<V[now].size();i++)
      {
        int next=V[now][i];
        if (!dfn[next])
          {
            work(next,now);
            low[now]=min(low[now],low[next]);
            if (low[next]>dfn[now]) /*SaveRoad*/
          }
        else if (next!=last&&dfn[next]<dfn[now])
          low[now]=min(low[now],dfn[next]);
      }
  }