Wpp


私信TA

用户名:AbertW

访问量:860

签 名:

等  级
排  名 452
经  验 3240
参赛次数 1
文章发表 8
年  龄 0
在职情况 学生
学  校 北京工商大学
专  业

  自我简介:

解题思路:
    逆向思维+并查集
注意事项:
    sort的自定义函数如果判断条件为>=会出错,对sort不了解所以不知道原因是什么?
参考代码:

/*
 *国王的烦恼:逆向思维
 *	抗议条件:前一天可以到达,而后一天不能,即联通性发生改变
 *	如果直接用并查集会发现没有删除两点联通的函数
 *	实际上条件的关键是联通性的改变,可以逆向思考:天数逆向,那么
 *状态的改变实际上就是前一天联通而后一天不连通,而建造的那一天即
 *是原题桥不能使用的那一天 
 */
 
#include<cstdio>
#include<algorithm>
using namespace std;

const int Max_N = 1e4+10;
const int Max_M = 1e5+10;

struct Brige
{
	int u,v;
	int day;
	Brige(){}
	Brige(int u_,int v_,int day_)
	{
		u = u_; v = v_; day = day_;
	}
}brige[Max_M];

int n,m;
int cur_day;
int par[Max_N];
int height[Max_N];
void init(int n);
int find(int x);
void unite(int x, int y);
bool same(int x, int y);
void solve();
bool cmp(const Brige &b1, const Brige &b2);

int main()
{
	scanf("%d%d",&n,&m);
	for( int i=0; i<m; i++ )
	{
		scanf("%d%d%d",&brige[i].u,&brige[i].v,&brige[i].day);
		cur_day = max( cur_day, brige[i].day);
	}
	
	solve();
	
	return 0;
}

void init(int n)
{
	for( int i=1; i<=n; i++ )
	{
		par[i] = i;
		height[i] = 0;
	}
}

int find( int x )
{
	return x==par[x] ? x : par[x] = find(par[x]);
}

void unite(int x, int y)
{
	x = find(x); y = find(y);
	if( x==y )
		return;
	if( height[x]<height[y] )
	{
		par[x] = y;	
	} 
	else
	{
		par[y] = x;
		if( height[x]==height[y] )	height[x]++;
	}
}

bool same(int x, int y)
{
	return find(x)==find(y);
}

bool cmp(const Brige &b1, const Brige &b2)
{
	return b1.day>b2.day;// 用>=作为条件会出错,原因是?
}

void solve()
{
	init(n);
	sort(brige,brige+m,cmp);
	
	int i = 0, ans = 0;
	bool flag;
	while( cur_day>0 && i<m )
	{
		flag = false;
		for( ; i<m; i++ )
		{
			if( cur_day != brige[i].day )
			{
				cur_day = brige[i].day;
				break;
			}
			int u = brige[i].u, v = brige[i].v;
			bool temp = same(u,v);
			unite(u,v);
			if( flag )	continue;
			if( temp^same(u,v) )
			{
				ans++;	flag = true;
			}
		}
	}
	printf("%d\n",ans);
}

希望有大佬解答

 

0.0分

1 人评分

  评论区