51nod 1444：破坏道路广度优先搜索

1444 破坏道路

题目来源： CodeForces

基准时间限制：1.5 秒空间限制：131072 KB 分值: 80 难度：5级算法题

取消关注

在某一个国家，那儿有n个城市，他们通过m条双向道路相连。城市从1到n编号。如果城市a和b通过一条道路直接相连，那么他们之间的距离就是一个小时。这个国家的道路网络可以允许你从任意一个城市到达另外的城市。

现在你要破坏尽可能多的道路，但是要保证从城市s1到t1不超过l1小时，并且从城市s2到t2不超过l2小时。

输出最多可以破坏的道路数目，如果没有解，请输出-1

Input

单组测试数据。

第一行有两个整数n,m(1 ≤ n ≤ 3000, n-1 ≤ m ≤ min(3000,n*(n-1)/2) )。

接下来m行，每行有两个整数 ai, bi (1 ≤ ai, bi ≤ n, ai ≠ bi)，表示ai和bi之间有一条道路。

输入保证是一个连通图。

最后两行每行有三个整数s1, t1, l1和 s2, t2, l2, (1 ≤ si, ti ≤ n, 0 ≤ li ≤ n)。

Output

输出一个整数，表示最多可以破坏的道路数目，如果没有解，输出-1。

Input示例

Output示例

无向图直接用广度优先搜索求出两点之间的最小距离，然后剩下的就是要去掉重复边，直接暴力。

代码：

#include <iostream>

#include <algorithm>

#include <cmath>

#include <vector>

#include <string>

#include <cstring>

#include <queue>

#pragma warning(disable:4996)

using namespace std;

int n, m;

int s1, t1, l1;

int s2, t2, l2;

vector<int>connect[3005];

int dis[3005][3005];

int vis[3005];

void bfs()

{

	int i, k, temp, v, size;

	for (i = 1; i <= n; i++)

	{

		memset(vis, 0, sizeof(vis));

		queue<int>q;

		q.push(i);

		vis[i] = 1;

		while (!q.empty())

		{

			temp = q.front();

			q.pop();

			size = connect[temp].size();

			for (k = 0; k < size; k++)

			{

				v = connect[temp][k];

				if (vis[v])continue;

				vis[v] = 1;

				dis[i][v] = dis[i][temp] + 1;

				q.push(v);

			}

		}

	}

}

int main()

{

	//freopen("i.txt","r",stdin);

	//freopen("o.txt","w",stdout);

	int i, j, temp1, temp2;

	scanf("%d%d", &n, &m);

	//fill(dis, INF, sizeof(dis));

	sizeof(dis, 0, sizeof(dis));

	for (i = 1; i <= m; i++)

	{

		scanf("%d%d", &temp1, &temp2);

		connect[temp1].push_back(temp2);

		connect[temp2].push_back(temp1);

	}

	scanf("%d%d%d", &s1, &t1, &l1);

	scanf("%d%d%d", &s2, &t2, &l2);

	bfs();

	int ans = dis[s1][t1] + dis[s2][t2];

	if (dis[s1][t1] > l1 || dis[s2][t2] > l2)

	{

		printf("-1\n");

	}

	else

	{

		for (int i = 1; i <= n; i++)

		{

			for (int j = 1; j <= n; j++)

			{

				if (dis[s1][i] + dis[i][j] + dis[j][t1] <= l1&&dis[s2][i] + dis[i][j] + dis[j][t2] <= l2)

				{

					ans = min(ans, dis[s1][i] + dis[i][j] + dis[j][t1] + dis[s2][i] + dis[j][t2]);

				}

				if (dis[t1][i] + dis[i][j] + dis[j][s1] <= l1&&dis[t2][i] + dis[i][j] + dis[j][s2] <= l2)

				{

					ans = min(ans, dis[t1][i] + dis[i][j] + dis[j][s1] + dis[t2][i] + dis[j][s2]);

				}

				if (dis[s1][i] + dis[i][j] + dis[j][t1] <= l1&&dis[t2][i] + dis[i][j] + dis[j][s2] <= l2)

				{

					ans = min(ans, dis[s1][i] + dis[i][j] + dis[j][t1] + dis[t2][i] + dis[j][s2]);

				}

				if (dis[t1][i] + dis[i][j] + dis[j][s1] <= l1&&dis[s2][i] + dis[i][j] + dis[j][t2] <= l2)

				{

					ans = min(ans, dis[t1][i] + dis[i][j] + dis[j][s1] + dis[s2][i] + dis[j][t2]);

				}

			}

		}

		printf("%d\n", m - ans);

	}

	//system("pause");

	return 0;

}

巴特西

51nod 1444：破坏道路广度优先搜索

最新文章

热门文章

巴特西

51nod 1444：破坏道路 广度优先搜索

最新文章

热门文章

51nod 1444：破坏道路广度优先搜索