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

矩阵操作来处理图

总结:

此类题目有一个明显的特点,是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;
}






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


矩阵操作来处理图