BZOJ 3373 [Usaco2004 Mar]Lying Livestock 说谎的牲畜

题目大意

给你N个点，每个点都有一个权值，还给你M个关系，每个关系形如：“A比B大”且拥有一个编号。问将编号为几的关系反向可以使得所有关系不出现环。

我被题意杀了……这题看到上面我写的题意就大概明白了……枚举每个编号，删除所有这个编号的边并将其反向，之后Tarjan判环。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

#define N 110
#define M 1010

struct edge{int u,v,id;}e[M];

int n,m,dep[N],low[N],st[N],top,cnt,ans;
int to[M],nex[M],head[N],tot;
bool ins[N],LYING;

void tarjan(int pos)
{
	st[++top]=pos,ins[pos]=true,dep[pos]=low[pos]=++cnt;
	for(int i=head[pos];i;i=nex[i])
	{
		if(!dep[to[i]]) tarjan(to[i]),low[pos]=min(low[pos],low[to[i]]);
		else if(ins[to[i]]) low[pos]=min(low[pos],dep[to[i]]);
	}
	if(low[pos]==dep[pos])
	{
		if(st[top]!=pos) LYING=true;
		do
		{
			ins[st[top]]=false;
		}while(st[top--]!=pos);
	}
}

inline void AE(int tx,int ty)
{
	to[++tot]=ty,nex[tot]=head[tx],head[tx]=tot;
}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;++i) scanf("%d%d%d",&e[i].id,&e[i].u,&e[i].v);
	for(int i=1;i<=n;++i)
	{
		memset(head,0,sizeof head);
		memset(dep,0,sizeof dep);
		top=cnt=tot=0;
		for(int j=1;j<=m;++j)
		{
			if(e[j].id!=i)
				AE(e[j].u,e[j].v);
			else
				AE(e[j].v,e[j].u);
		}
		LYING=false;
		for(int j=1;j<=n;++j)
			if(!dep[j])
				tarjan(j);
		if(!LYING) ans++;
	}
	printf("%d\n",ans);
	return 0;
}