POJ 1438 混合图定定向为强连通图双连通

84 阅读 0 评论 56 点赞

我是靠谱客的博主无语枕头，这篇文章主要介绍POJ 1438 混合图定定向为强连通图双连通，现在分享给大家，希望可以做个参考。

题意：

给定n个点 m条边 (点标从1开始)

下面m行表示边 u v k (k=1为单向，k=2为双向)

问：

把尽可能多的无向边定向使得最终图保持强连通的性质（任意两点可达）

答案保证有解。

输出所有无向边最终的情况

u v k (k = 2表示不定向 , k = 1表示定向为 u->v)

思路：

1、tarjan：由于图中既有有向边，又有无向边，那么先把有向边视为无向，用双连通求桥，直接输出桥然后删掉该边即可（因为题目保证有解，所以桥一定是无向边）

2、那么图中就只剩下一个个连通块，对于任意连通块（当前是当作边全为无向）我们必然能把所有无向边定向。因为要使得定向后依旧强连通，所以对于任意点u的low[u]值一定<=dfn[u].

1、当前遍历的是树边->若当前边是无向边：假如不满足该等式，则将边反向，若满足则无向边方向正确（定向后直接输出并删边）

2、当前遍历的是后向边-> 容易确定若为无向边就让这边成为后向边。

复制代码

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<queue>
#include<math.h>
#include<vector>
#define N 2005
using namespace std;
int n,m;//n个点 m条边
int low[N],dfn[N],tarjin_time;
bool map[N][N], flag[N][N];
void add(int u,int v,bool bid)
{
map[u][v] = true; flag[u][v] = bid;
}
void tarjin(int u,int pre)
{
low[u]=dfn[u]= ++tarjin_time;
for(int v = 1; v <= n; v++)
{
if(v == pre || !flag[u][v])continue;
if(!dfn[v])
{
tarjin(v,u);
if(low[u]>low[v])low[u]=low[v];
if(low[v]>dfn[u])
{ printf("%d %d 2n", u, v); flag[u][v] = flag[v][u] = false; continue;}
}
else if(low[u]>dfn[v])low[u]=dfn[v];
}
}
void find_edgecut()
{
memset(dfn,0,sizeof(dfn));
tarjin_time=1;
for(int i=1;i<=n;i++)if(!dfn[i])tarjin(i,i);
}
void init(){
for(int i = 1; i <= n; i++)memset(map[i], 0, sizeof(map[i])), memset(flag[i], 0, sizeof(flag[i]));
}
void dfs(int u,int pre)
{
low[u]=dfn[u]= ++tarjin_time;
for(int v = 1; v <= n; v++)
{
if(v == pre || !flag[u][v])continue;
if(!dfn[v])
{
dfs(v,u);
if(low[u]>low[v])low[u]=low[v];
if(flag[v][u])
{
if(low[v]>dfn[u])
{ printf("%d %d 1n", v, u); flag[u][v] = false;}
else
{ printf("%d %d 1n", u, v); flag[v][u] = false;}
}
}
else
{
if(flag[v][u])printf("%d %d 1n", u, v);
flag[u][v] = false;
low[u] = min(low[u], dfn[v]);
}
}
}
int main(){
int u, v, i, k;
while(~scanf("%d %d",&n,&m)){
init();
while(m--){
scanf("%d %d %d", &u, &v, &k);
add(u, v, 1); add(v, u, k==2);
}
find_edgecut();
memset(dfn, 0, sizeof(dfn));tarjin_time = 0;
for(i = 1; i <= n; i++)if(!dfn[i])dfs(i, 0);
}
return 0;
}
/*
4 4
4 1 1
4 2 2
1 2 1
1 3 2
*/

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
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<queue>
#include<math.h>
#include<vector>
#define N 2005
using namespace std;
int n,m;//n个点 m条边
int low[N],dfn[N],tarjin_time;
bool map[N][N], flag[N][N];
void add(int u,int v,bool bid)
{
map[u][v] = true; flag[u][v] = bid;
}
void tarjin(int u,int pre)
{
low[u]=dfn[u]= ++tarjin_time;
for(int v = 1; v <= n; v++)
{
if(v == pre || !flag[u][v])continue;
if(!dfn[v])
{
tarjin(v,u);
if(low[u]>low[v])low[u]=low[v];
if(low[v]>dfn[u])
{ printf("%d %d 2n", u, v); flag[u][v] = flag[v][u] = false; continue;}
}
else if(low[u]>dfn[v])low[u]=dfn[v];
}
}
void find_edgecut()
{
memset(dfn,0,sizeof(dfn));
tarjin_time=1;
for(int i=1;i<=n;i++)if(!dfn[i])tarjin(i,i);
}
void init(){
for(int i = 1; i <= n; i++)memset(map[i], 0, sizeof(map[i])), memset(flag[i], 0, sizeof(flag[i]));
}
void dfs(int u,int pre)
{
low[u]=dfn[u]= ++tarjin_time;
for(int v = 1; v <= n; v++)
{
if(v == pre || !flag[u][v])continue;
if(!dfn[v])
{
dfs(v,u);
if(low[u]>low[v])low[u]=low[v];
if(flag[v][u])
{
if(low[v]>dfn[u])
{ printf("%d %d 1n", v, u); flag[u][v] = false;}
else
{ printf("%d %d 1n", u, v); flag[v][u] = false;}
}
}
else
{
if(flag[v][u])printf("%d %d 1n", u, v);
flag[u][v] = false;
low[u] = min(low[u], dfn[v]);
}
}
}
int main(){
int u, v, i, k;
while(~scanf("%d %d",&n,&m)){
init();
while(m--){
scanf("%d %d %d", &u, &v, &k);
add(u, v, 1); add(v, u, k==2);
}
find_edgecut();
memset(dfn, 0, sizeof(dfn));tarjin_time = 0;
for(i = 1; i <= n; i++)if(!dfn[i])dfs(i, 0);
}
return 0;
}
/*
4 4
4 1 1
4 2 2
1 2 1
1 3 2
*/