[문제 풀이] [POJ 3417] 어두 운 연쇄 [LCA + 트 리 차이 점]

제목 설명
POJ 3417
Dark 는 방향 이 없 는 그림 입 니 다. 그림 에는 n 개의 노드 와 두 개의 변 이 있 는데 하 나 는 주요 변 이 라 고 부 르 고 다른 하 나 는 부가 변 이 라 고 부 릅 니 다.Dark 는 주요 변 이 있 고 Dark 의 임 의 두 노드 사이 에 주요 변 으로 만 구 성 된 경로 가 존재 합 니 다.또 다 크 는 m 개의 부가 변 이 있다.
당신 의 임 무 는 다 크 를 연결 되 지 않 는 두 부분 으로 자 르 는 것 입 니 다.처음에는 Dark 의 부가 변 이 무적 상 태 였 고, 주요 변 을 선택 하여 차단 할 수 밖 에 없 었 다.메 인 사 이 드 를 차단 하면 다 크 는 방어 모드 로 들 어가 주요 사 이 드 는 무적 이 되 고 부가 사 이 드 는 차단 된다.하지만 당신 의 능력 은 Dark 의 부가 변 을 하나 더 차단 할 수 밖 에 없습니다.
지금 당신 은 모두 몇 가지 방안 이 Dark 를 처치 할 수 있 는 지 알 고 싶 습 니 다.주의 하 세 요. 메 인 사 이 드 를 첫 번 째 로 자 른 후에 도 Dark 를 두 동강 이 났 습 니 다. 추가 사 이 드 를 잘라 야 Dark 를 처치 할 수 있 습 니 다.
사실 이 문 제 는 누 드 나무 에 차이 가 나 는 문제 이다. 사실은 부가 변 은 비 나무 변 이다. 모든 비 나무 변 에 대해 x, y 와 그들의 최근 공공 조상 을 하나의 고리 로 연결시킨다.우 리 는 고리 의 가장 자 리 를 하나 더 하고, 여 기 는 나무의 차이 로 처리한다.
하나의 가중치 가 0 인 변 에 대해 이 변 을 제거 한 후에 다른 임의의 추가 변 을 제거 할 수 있 습 니 다. 그래서 ans + = m 는 하나의 가중치 가 1 인 변 에 대해 이 변 을 제거 한 후에 비 나무 변 을 제거 하면 됩 니 다. 방안 이 유일 하기 때문에 ans +;가중치 가 1 보다 큰 변 에 대해 서 는 분명히 성공 할 수 없다.
코드 는 다음 과 같 습 니 다:

#include

using namespace std;

const int maxn = 1e5+7;

int n,m,head[maxn],cnt=0,dep[maxn],f[maxn][21];
int size[maxn];
long long ans=0;
struct edge
{
	int to,pre;
}e[maxn*2];

inline void add(int x,int y)
{
	e[++cnt].pre=head[x];
	e[cnt].to=y;
	head[x]=cnt;
}

void dfs(int x,int fa)
{
	dep[x]=dep[fa]+1;
	for(int i=1;i<=20;++i)
		f[x][i]=f[f[x][i-1]][i-1];
		
	for(int i=head[x];i;i=e[i].pre)
	{
		int v=e[i].to;
		if(v==fa) continue;
		f[v][0]=x;
		dfs(v,x);
	}
}

int lca(int x,int y)
{
	if(dep[x]=0;--i)
	{
		if(dep[f[x][i]]>=dep[y]) x=f[x][i];
		if(x==y) return x;
	}
	for(int i=20;i>=0;--i)
	{
		if(f[x][i]!=f[y][i])
		{
			x=f[x][i];
			y=f[y][i];
		}
	}
	return f[x][0];
}

void aaa(int x,int fa)
{
	for(int i=head[x];i;i=e[i].pre)
	{
		int v=e[i].to;
		if(v==fa) continue;
		aaa(v,x);
		size[x]+=size[v];
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

당신 의 임 무 는 다 크 를 연결 되 지 않 는 두 부분 으로 자 르 는 것 입 니 다.처음에는 Dark 의 부가 변 이 무적 상 태 였 고, 주요 변 을 선택 하여 차단 할 수 밖 에 없 었 다.메 인 사 이 드...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

[문제 풀이] [POJ 3417] 어두 운 연쇄 [LCA + 트 리 차이 점]

좋은 웹페이지 즐겨찾기