[构造] UOJ134. 【UR #9】App 管理器

想通了就很简单。

首先原图不考虑定向,一定是双联通的,否则不可能定向使得强连通。

所以其实很容易就能构造得到强连通。

对于一条边 \((u,v)\) 考虑给他定向,若 \(u\)\(v\) 有路,则可以定向为 \(v\to u\) , 若 \(v\)\(u\) 有路,则可以 \(u\to v\)

由于原图双联通,所有不管之前怎么定向,两种情况总满足一种。

这样就一定能构造出来。

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
#include<cstdio>
using namespace std;
const int maxn=5005;
int n,m,ans[maxn],U[maxn],V[maxn],D[maxn],g[maxn][maxn];
int fir[maxn],son[maxn*2],nxt[maxn*2],tot;
int clk[maxn],Tim;
void add(int x,int y){
son[++tot]=y; nxt[tot]=fir[x]; fir[x]=tot;
g[x][y]++;
}
void dfs(int x){
clk[x]=Tim;
for(int j=fir[x];j;j=nxt[j])
if(clk[son[j]]!=Tim&&g[x][son[j]]) dfs(son[j]);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
scanf("%d%d%d",&U[i],&V[i],&D[i]);
add(U[i],V[i]);
if(!D[i]) add(V[i],U[i]);
}
for(int i=1;i<=m;i++)
if(!D[i]){
g[U[i]][V[i]]--;
Tim++; dfs(U[i]);
g[U[i]][V[i]]++;
if(clk[V[i]]!=Tim) ans[i]=0, g[V[i]][U[i]]--;
else ans[i]=1, g[U[i]][V[i]]--;
}
for(int i=1;i<=m;i++) printf("%d\n",ans[i]);
return 0;
}