HDU 4034 图论 Floyd

最新推荐文章于 2018-11-10 10:27:39 发布

codeforces_sphinx

最新推荐文章于 2018-11-10 10:27:39 发布

阅读量1k

点赞数

分类专栏： HDU ACM-图论文章标签： oo

本文链接：https://blog.csdn.net/codeforces_sphinx/article/details/7185292

版权

HDU 同时被 2 个专栏收录

43 篇文章

订阅专栏

ACM-图论

8 篇文章

订阅专栏

本文介绍了一种利用Floyd算法进行图优化的方法，通过遍历所有顶点判断是否存在更短路径，进而删除多余的直接连接边。代码实现采用C++，并提供了测试数据。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

/*******************************************************************************
   前几天真TMD NC死了。。。一次Floyd就完事，每次观察dp[i, k] + dp[k, j]和dp[i, j]的值，若
dp[i, k] + dp[k, j] < dp[i, j]，显然无解，因为尼玛的都不是最短路的图。。。如果
dp[i, k] + dp[k, j] == dp[i, j]，那就把i-->j这条边给删了，因为可以通过k为中间点走，所以多
余了～
*******************************************************************************/
#include <iostream>
#include <functional>
#include <algorithm>
#include <complex>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <iomanip>
#include <sstream>
#include <utility>
#include <bitset>
#include <cctype>
#include <cstdio>
#include <limits>
#include <memory>
#include <string>
#include <vector>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <list>
#include <map>
#include <set>
using namespace std;

#define LOWBIT(x) ( (x) & ( (x) ^ ( (x) - 1 ) ) )
#define CLR(x, k) memset((x), (k), sizeof(x))
#define CPY(t, s) memcpy((t), (s), sizeof(s))
#define SC(t, s) static_cast<t>(s)
#define LEN(s) static_cast<int>( strlen((s)) )
#define SZ(s) static_cast<int>( (s).size() )

typedef double LF;
typedef __int64 LL;		//VC
typedef unsigned __int64 ULL;

typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef pair<double, double> PDD;

typedef vector<int> VI;
typedef vector<char> VC;
typedef vector<double> VF;
typedef vector<string> VS;

template <typename T>
T sqa(const T & x)
{
	return x * x;
}
template <typename T>
T gcd(T a, T b)
{
	if (!a || !b)
	{
		return max(a, b);
	}
	T t;
	while (t = a % b)
	{
		a = b;
		b = t;
	}
	return b;
};

const int INF_INT = 0x3f3f3f3f;
const LL INF_LL = 0x7fffffffffffffffLL;		//15f
const double oo = 10e9;
const double eps = 10e-7;
const double PI = acos(-1.0);

#define  ONLINE_JUDGE

const int MAXN = 104;

int test, n, dp[MAXN][MAXN];
bool hs[MAXN][MAXN];

bool floyd()
{
	for (int k = 0; k < n; ++k)
	{
		for (int i = 0; i < n; ++i)
		{
			if (i == k)
			{
				continue ;
			}
			for (int j = 0; j < n; ++j)
			{
				if (k == j || i == j)
				{
					continue ;
				}
				if (dp[i][k] + dp[k][j] < dp[i][j])
				{
					return false;
				}
				if (dp[i][k] + dp[k][j] == dp[i][j])
				{
					hs[i][j] = false;
				}
			}
		}
	}
	return true;
}
void ace()
{
	int cas = 1;
	int res = 0;
	for (cin >> test; test--; ++cas)
	{
		cin >> n;
		for (int i = 0; i < n; ++i)
		{
			for (int j = 0; j < n; ++j)
			{
				cin >> dp[i][j];
				if (i == j)
				{
					dp[i][j] = 0;
				}
			}
		}
		CLR(hs, true);
		for (int i = 0; i < n; ++i)
		{
			for (int j = 0; j < n; ++j)
			{
				if (0 == dp[i][j])
				{
					hs[i][j] = false;
				}
			}
		}
		cout << "Case " << cas << ": ";
		if (!floyd())
		{
			cout << "impossible" << endl;
			continue ;
		}
		res = 0;
		for (int i = 0; i < n; ++i)
		{
			for (int j = 0; j < n; ++j)
			{
				res += hs[i][j];
			}
		}
		cout << res << endl;
	}
	return ;
}
int main()
{
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	ace();
	return 0;
}
/*******************************************************************************
Test Data...

3
3
0 1 1
1 0 1
1 1 0
3
0 1 3 
4 0 2
7 3 0
3
0 1 4
1 0 2
4 2 0
*******************************************************************************/