首页 > 代码库 > 矩阵操作来处理图

矩阵操作来处理图

2024-07-02 12:32:58   223人阅读

总结：

此类题目有一个明显的特点，是n个点或者n*n的矩阵，否则无法做矩阵运算

点数不能太大，因为矩阵操作的复杂度是O(N^3)的，所以大概最多只能有100个点
结果和移动次数有关，且一次只能移动一个点（经过一条边）

Codeforces Round #236 (Div. 2)——Strictly Positive Matrix


题意：

给一个n*n的矩阵a，保证a[i][i]>0，所有元素非负

若干次幂之后，问时候能保证矩阵中不含有零


分析：

首先说明一点，矩阵的数值是没有多少关系的，只有零和大于零的数有区别，不妨把大于零的数变成1。对于a*a，可以考虑到，如果求出来a[i][j]大于零，那么相当于i通过一个点可以到达j，那么a^k就可以理解为经过k个点，所有点能不能互相到达。矩阵保证了对角线均大于零，也就是说点i可以通过点i到达i，所以最后的结果就是求一下所有点是不是能互相到达即可（i如果能经过k个点到达j，那么经过大于k个点也能到达j）

所以，问题转化成求整个图的连通性


第一种方法，参照大神的代码，使用bitset来实现floyd算法
const int MAXN = 2100;

bitset<MAXN> ipt[MAXN];

int main()
{
//    freopen("in.txt", "r", stdin);
	int n;
	while (~RI(n))
	{
		REP(i, n) REP(j, n) 
		{
			int t;
			RI(t);
			ipt[i][j] = !!t;
		}
		bool ok = true;
		REP(k, n) REP(i, n) 
			if (ipt[i][k])
				ipt[i] |= ipt[k];
		REP(i, n) REP(j, n) if (ipt[i][j] == 0) ok = false;
		if (ok) puts("YES");
		else puts("NO");
	}
	return 0;
}

第二种方法，参照大神，如果点1能到达所有点，切所有点都能到达点1，那么整个图连通
const int MAXN = 2100;

vector<int> G[MAXN], RG[MAXN];
bool vis[MAXN], rvis[MAXN];
void dfs(int u)
{
	vis[u] = true;
	REP(i, G[u].size())
	{
		int v = G[u][i];
		if (!vis[v])
			dfs(v);
	}
}

void rdfs(int u)
{
	rvis[u] = true;
	REP(i, RG[u].size())
	{
		int v = RG[u][i];
		if (!rvis[v])
			rdfs(v);
	}
}
int main()
{
//    freopen("in.txt", "r", stdin);
	int n;
	while (~RI(n))
	{
		CLR(vis, false); CLR(rvis, false);
		REP(i, n)
		{
			G[i].clear();
			RG[i].clear();
		}
		REP(i, n) REP(j, n) 
		{
			int t;
			RI(t);
			if (t)
			{
				G[i].push_back(j);
				RG[j].push_back(i);
			}
		}
		dfs(0); rdfs(0);
		bool ok = true;
		REP(i, n) if (!vis[i]) ok = false;
		REP(i, n) if (!rvis[i]) ok = false;
		if (ok) puts("YES");
		else puts("NO");
	}
	return 0;
}












福州大学第十一届程序设计竞赛——Nostop


题意：

给一个有向图，从点1出发，每次走一条边，K次之后必须在点N。每条边有一个花费，求最后的最小花费，不能到达输出-1

分析：

特点：点数比较少（可以保留所有的结果即cost矩阵），操作步骤比较多，每次的操作一致（均是走一步）
状态->操作->状态->操作->状态。。。
这个题和上个题的区别在于，这个题目给定了k，所以不能直接判断可达（而且没有保证点的自环）。

注意一点，long long的INF需要单独修改
const LL INF = 1e18;
const int MAXN = 60;

struct Matric
{
	LL a[MAXN][MAXN];
	int n;
} ipt;
Matric operator* (Matric x, Matric y)
{
	Matric ret; ret.n = x.n;
	REP(i, x.n) REP(j, x.n) ret.a[i][j] = INF;
    REP(i, x.n) REP(j, x.n) REP(k, x.n)
        ret.a[i][j] = min(ret.a[i][j], x.a[i][k] + y.a[k][j]);
    return ret;
}
Matric pow(Matric a, int b)
{
	Matric ret; ret.n = a.n;
	bool flag = false;
	while (b)
	{
		if (b & 1)
		{
			if (flag) ret = ret * a;
			else ret = a;
			flag = true;
		}
		a = a * a;
		b >>= 1;
	}
	return ret;
}
int main()
{
//    freopen("in.txt", "r", stdin);
	int T, v, e, k, a, b, d;
	RI(T);
	REP(kase, T)
	{
		RIII(v, e, k);
		ipt.n = v;
		REP(i, v) REP(j, v) ipt.a[i][j] = INF;
		REP(i, e)
		{
			RIII(a, b, d);
			a--; b--;
			ipt.a[a][b] = min(ipt.a[a][b], (LL)d);
		}
		ipt = pow(ipt, k);
		if (ipt.a[0][v - 1] != INF)
			cout << ipt.a[0][v - 1] << endl;
		else
			puts("-1");
	}
	return 0;
}






还有一个可以解决的是：求出从起点到每个点的路径数量


矩阵操作来处理图


联系
我们