UOJ134 App 管理器 做题记录

给定一个 $n$ 个点 $m$ 条边的图 $G$，有一些边有向，剩下的边无向。你要给每条无向边定向使得定向后的有向图 $H$ 强连通。输出方案。

$1\le n,m\le 5000$。

Jerry Wen 定理，考虑找有解的若干必要/充分条件，再证明这些条件的并是充要的：

• 若把所有有向边看作无向边，则 $G$ 一定是一个点双；
• 若把所有无向边看作双向边（两条有向边：$u\to v$ 和 $v\to u$），则 $G$ 一定强连通；

这些条件的并显然是必要的，考虑证明它们的并是充要的：

• 必要性显然；

• 充分性：

  考虑反证。若某个时刻满足这两个条件，且对于某条无向边 $(u,v)$，无论如何定向都不能同时满足这两个条件，则：

  • 由于第一个条件定向后一定仍满足，所以一定是不满足第二个条件；

  • 由于定向前满足第二个条件，定向后不满足，所以 $u\to v$ 与 $v\to u$ 一定都要被经过，那么图一定是长这样的：

    

    但是这样显然可以把这两个环合并得到一个大环，不需要走 $(u,v)$ 这条边。

    所以不存在这种情况。

    Q.E.D.

由于题目保证了一定有解，所以第一个条件一定满足，只用判断第二个条件是否满足。

那么直接枚举每条边，$O(n+m)$ 判断哪种定向合法即可，时间复杂度 $O(m(n+m))$。注意判合法只要判断定向后 $u$ 和 $v$ 能否互相到达。

代码如下：

#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

const int S=5005;

struct node
{
	int x,y,t;
}ed[S];

int n,m;
vector<int> g[S];
bool vis[S];
int ans[S];

bool chk(int u,int v,int ban)
{
	vis[u]=true;
	if(u==v) return true;
	for(int i:g[u])
	{
		if(i==ban) continue;
		int too=-1;
		if(ed[i].x==u)
		{
			if(ed[i].t==0||ed[i].t==1) too=ed[i].y;
		}
		else
		{
			if(ed[i].t==0||ed[i].t==2) too=ed[i].x;
		}
		if(v!=-1&&!vis[too]&&chk(too,v,ban)) return true;
	}
	return false;
}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++) scanf("%d%d%d",&ed[i].x,&ed[i].y,&ed[i].t);
	for(int i=1;i<=m;i++) g[ed[i].x].push_back(i),g[ed[i].y].push_back(i);
	for(int i=1;i<=m;i++)
	{
		if(ed[i].t==0)
		{
			for(int j=1;j<=n;j++) vis[j]=false;
			if(chk(ed[i].y,ed[i].x,i)) ed[i].t=1,ans[i]=0;
			else ed[i].t=2,ans[i]=1;
		}
		else ans[i]=0;
	}
	for(int i=1;i<=m;i++) printf("%d\n",ans[i]);
	return 0;
}