【ybtoj 11.13 S组】【二分】【BFS】D. 道路与航线

• 题面
• 解题思路
• Code
• • 方法一
  • 方法二

ybtoj 11.13 S组 D. 道路与航线

样例
样例输入1

4 6 1 4 
2 3 0 
1 2 1 
3 4 1 
4 3 0 
2 1 1 
1 3 1

样例输出1

3 5

样例2
去掉第一个c和第一个b。见选手附加文件。比完赛就没大数据了((((

出题人良心，数据范围明明3*10^6，于是40分卡了一小时

方法一：二分答案，然后暴力bfs就好了
方法二：用vis[i]标记起点能不能到达 i

• 如果 s 能走到 i，i 能走到 j ，那么 s 也能走到 j
• 如果s 不能走到 i，i 能走到 j，但是不能保证后面加入边时 s 不能走到 i ：将 i 和 j 连起来，下次连到 i 时，再做一个小bfs(i)

#include 
#define N 3001000

using namespace std;

struct DT{
	int to, next;
}a[N * 2];
int n, m, S, T, l, r, mid, ans;
int num, head[N], v[N], x[N], y[N], id[N];
queue q;

void add(int x, int y) {
	a[++ num] = (DT){ y, head[x] }, head[x] = num;
}

int check(int m) {
	memset(head, 0, sizeof(head));
	num = 0;
	for(int i = 1; i <= m; i ++) {
		add(x[i], y[i]);
		if(!id[i]) add(y[i], x[i]);
	}
	
	memset(v, 0, sizeof(v));
	while(!q.empty()) q.pop();
	q.push(S);
	while(!q.empty()) {
		int x = q.front();
		for(int i = head[x]; i; i = a[i].next) {
			int y = a[i].to;
			if(!v[y]) v[y] = 1, q.push(y);
			if(y == T) return 1;
		}
		q.pop();
	}
	return 0;
}

int main() {
	freopen("road.in", "r", stdin);
	freopen("road.out", "w", stdout);
	scanf("%d %d %d %d", &n, &m, &S, &T);
	for(int i = 1; i <= m; i ++)
		scanf("%d %d %d", &x[i], &y[i], &id[i]);
	l = 1, r = m;
	while(l <= r) {
		mid = (l + r) / 2;
		if(check(mid)) 
			ans = mid, r = mid - 1;
		else l = mid + 1;
	}
	printf("%d ", ans);
	l = 1, r = m, swap(S, T);
	while(l <= r) {
		mid = (l + r) / 2;
		if(check(mid)) 
			ans = mid, r = mid - 1;
		else l = mid + 1;
	}
	printf("%d", ans);
}

#include 
#define N 3001000

using namespace std;

struct DT{
	int to, next;
}a[N * 2];
int n, m, S, T, v[N], w[N][3];
int num, head[N];
queue q;

void add(int x, int y) {
	a[++ num] = (DT){ y, head[x] }, head[x] = num;
}

int check(int x, int y, int T) {
	if(!v[x]) add(x, y);
	if(v[x] && !v[y]) {
		v[y] = 1, q.push(y);
		while(!q.empty()) {
			int xx = q.front();
			for(int i = head[xx]; i; i = a[i].next)
				if(!v[a[i].to]) q.push(a[i].to), v[a[i].to] = 1;
			q.pop();
		}
	}
	return v[T];
}

int find(int x, int y) {
	v[x] = 1;
	for(int i = 1; i <= m; i ++) {
		if(check(w[i][0], w[i][1], y)) return i;
		if(w[i][2] == 0 && check(w[i][1], w[i][0], y))
			return i;
	}
	return -1;
}

int read()
{
	char c = getchar();
	while(c<'0' || c>'9') c=getchar();
	int t = 0;
	while(c>='0' && c<='9')
	{
		t = t*10+c-'0';
		c=getchar();
	}
	return t;
}

int main() {
	freopen("road.in", "r", stdin);
	freopen("road.out", "w", stdout);
	n = read(), m = read(), S = read(), T = read();
	for(int i = 1; i <= m; i ++)
		w[i][0] = read(), w[i][1] = read(), w[i][2] = read();
	printf("%d ", find(S, T));
	
	memset(v, 0, sizeof(v));
	memset(head, 0, sizeof(head));
	num = 0;
	
	printf("%d", find(T, S));
}