全图中第K小路径/团问题（有向/无向）

程序员文章站 2024-03-02 22:03:28

...

问题概述：

最近频繁遇见图上的第 $k$ 小问题，比如无向图的第 $k$ 小团、有向图上的第 $k$ 小路径，无向图上的第 $k$ 小最短路问题。

然后这类方法的解决方法都比较相近，主要思考方向是先将边或单点加入堆中，然后每次弹出一个最小值，再用最小值去更新到一个新的状态，并将新状态加入到堆中，一直到计算到 $k$ 次为止。

主要思想就是这样，但是具体操作上，对于不同的问题，涉及到不同的处理方式，主要就是关于算重和算漏的问题。如何不重不漏地计算成为此类问题的关键。

1. 无向图第k小团

题意: 给出一个 $n$ 个点的无向图，每个点都有一个权重，求出图中第 $k$ 小的团，找不到输出 $-1$ 。团的定义为完全图。 $(1\leq n\leq 100,1\leq k\leq 10^6)$

思路: 此类的问题的思路比较统一，先定一个状态，然后再将这个状态丢入堆中，去更新其它状态。

我们定状态为团的权重，并用 $bitset$ 记录团中所有出现的点，并记录每个团中编号最大的节点。

我们更新时每次选一个编号比当前团中任意节点都大的一个节点加入团中。判断一个点是否可以加入团，只需判断这个点的邻接矩阵和记录团中点的 $bitset$ 进行与运算，如果最终结果仍然是团中点的 $bitset$ ，则证明当前点和团中所有点都有连边，因此加入这个点仍可以构成一个团。

总结: 此处运用 $bitset$ 去存储团的状态，以及判断点能否加入一个团中。每次往团中加入的点必须比原有点的编号都要大，由此避免重复计算。

代码:

#include <bits/stdc++.h>
#define __ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define rep(i,a,b) for(int i = a; i <= b; i++)
#define LOG1(x1,x2) cout << x1 << ": " << x2 << endl;
#define LOG2(x1,x2,y1,y2) cout << x1 << ": " << x2 << " , " << y1 << ": " << y2 << endl;
#define LOG3(x1,x2,y1,y2,z1,z2) cout << x1 << ": " << x2 << " , " << y1 << ": " << y2 << " , " << z1 << ": " << z2 << endl;
typedef long long ll;
typedef double db;
const int N = 100+10;
const db EPS = 1e-9;
using namespace std;

char s[N];
int n,k;
ll w[N];
bitset<105> mp[N];
struct Node{
    ll w; int id;
    bitset<105> vis;
    Node() {w = id = 0;vis.reset();}
    bool operator < (Node xx) const {
        return w > xx.w;
    }
};

priority_queue<Node> q;

int main()
{
    scanf("%d%d",&n,&k);
    rep(i,1,n) scanf("%lld",&w[i]);
    rep(i,1,n){
        scanf("%s",s+1);
        rep(j,1,n)
            if(s[j] == '1') mp[i].set(j);
    }
    while(q.size()) q.pop();
    Node empty; ll ans = 0;
    q.push(empty);
    while(q.size()){
        Node x = q.top(); q.pop();
        k--;
        if(k == 0) {ans = x.w; break;}
        rep(i,x.id+1,n)
            if(x.vis[i] == 0 && (x.vis&mp[i]) == x.vis){
                Node nw = x;
                nw.w += w[i];
                nw.vis[i] = 1;
                nw.id = i;
                q.push(nw);
            }
    }
    if(k != 0) printf("-1\n");
    else printf("%lld\n",ans);
    return 0;   
}

2. 有向图第k小路径

题意: 给出一个 $n$ 个点 $m$ 条边的有向图，每条边都有一个权重。一共有 $q$ 组询问，每次询问 $k$ ，表示询问图中第 $k$ 小的路径。 $(1\leq n,m,q,k\leq 5*10^4)$

思路: $q$ 组询问，我们离线下来，只用求出最大的那个 $k$ 的答案即可。

然后一样的套路，定状态。一条路径的表示，无非是起点和终点， $(u,v)$ ，但是如果这样定状态的话，会发现不好更新，难道更新 $v$ 的所有出边，如果更新 $v$ 的所有出边很容易 $T$ ？

因此我们令 $u$ 为 $v$ 的前驱，状态定义为 $(u,v,id,w)$ 表示 $u$ 是 $v$ 的前驱，且 $v$ 是 $u$ 的第 $id$ 条出边，当前路径权重为 $w$ 。

然后每次更新 $u$ 的第 $id+1$ 条出边，或者更新 $v$ 的第一条出边即可，记得将每个点的出边排序。

代码:

#include <bits/stdc++.h>
#define __ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define rep(i,a,b) for(int i = a; i <= b; i++)
#define LOG1(x1,x2) cout << x1 << ": " << x2 << endl;
#define LOG2(x1,x2,y1,y2) cout << x1 << ": " << x2 << " , " << y1 << ": " << y2 << endl;
#define LOG3(x1,x2,y1,y2,z1,z2) cout << x1 << ": " << x2 << " , " << y1 << ": " << y2 << " , " << z1 << ": " << z2 << endl;
typedef long long ll;
typedef double db;
const db EPS = 1e-9;
const int N = 5*1e4+10;
using namespace std;

int n,m,qn,Q[N],maxn;
ll ans[N];
vector<pair<ll,int> > v[N];
struct Node{
	int u,v,id;
	ll w;
	Node() {}
	Node(int x,int y,int d,ll z):u(x),v(y),id(d),w(z) {}
	bool operator < (Node xx) const {
		return w > xx.w;
	}
};

priority_queue<Node> q;

void solve(){
	while(q.size()) q.pop();
	int ct = 0;
	rep(i,1,n) sort(v[i].begin(),v[i].end());
	rep(i,1,n){
		if(v[i].size())
			q.push({i,v[i][0].second,0,v[i][0].first});
	}
	while(q.size()){
		Node x = q.top(); q.pop();
		ct++;
		ans[ct] = x.w;
		if(ct == maxn) break;
		if(v[x.v].size()){
			q.push({x.v,v[x.v][0].second,0,x.w+(v[x.v][0].first)});
		}
		if((int)v[x.u].size() > (int)(x.id+1)){
			q.push({x.u,v[x.u][x.id+1].second,x.id+1,x.w-v[x.u][x.id].first+v[x.u][x.id+1].first});
		}	
	}
	rep(i,1,qn){
		printf("%lld\n",ans[Q[i]]);
	}
}

int main()
{
	int _; scanf("%d",&_);
	while(_--){
		scanf("%d%d%d",&n,&m,&qn);
		rep(i,0,n) v[i].clear();
		rep(i,1,m){
			int x,y; ll w; scanf("%d%d%lld",&x,&y,&w);
			v[x].push_back(make_pair(w,y));
		}
		maxn = 0;
		rep(i,1,qn){
			scanf("%d",&Q[i]);
			maxn = max(maxn,Q[i]);
		}
		solve();
	}
	return 0;
}

3. 无向图的第k小最短路

题意: $n$ 个点， $m$ 条边的有权无向图，询问图中第 $k$ 大的最短路，注意路径 $(u,v)$ 被计算，仅当这条路径是 $(u,v)$ 之间的最短路，保证有解。 $(2\leq n,m\leq 2*10^5,1\leq k\leq 400)$

思路: 无向图中的问题，主要难点在于如何才能避免算重。

我们注意到此题是两点之间的最短路，而两点之间只会有一条最短路，路径端点相同且长度相同算一条。因此我们将路径两点存入 $map$ ，当且仅当路径两点第一次在一条路径中出现时，才更新答案。

因此状态就是路径的起点和终点以及路径的权重，每次选择终点的出边进行状态更新即可。

代码:

#include <bits/stdc++.h>
#define __ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define rep(i,a,b) for(int i = a; i <= b; i++)
#define LOG1(x1,x2) cout << x1 << ": " << x2 << endl;
#define LOG2(x1,x2,y1,y2) cout << x1 << ": " << x2 << " , " << y1 << ": " << y2 << endl;
#define LOG3(x1,x2,y1,y2,z1,z2) cout << x1 << ": " << x2 << " , " << y1 << ": " << y2 << " , " << z1 << ": " << z2 << endl;
typedef long long ll;
typedef double db;
const int N = 2*1e5+100;
const int M = 4*1e5+100;
const db EPS = 1e-9;
using namespace std;
 
int n,m,k;
vector<pair<ll,int> > v[N];
struct Node{
	ll w; int u,v;
	Node(ll a,int b,int c) : w(a), u(b), v(c) {}
	bool operator < (Node xx) const {
		return w > xx.w;
	}
};
map<pair<int,int>,int> mp;
vector<Node> temp;
priority_queue<Node> q;
 
void dijsktra(){
	int cnt = 0;
	mp.clear();
	while(q.size()) q.pop();
	rep(i,1,n) q.push({0,i,i});
	while(q.size()){
		Node tp = q.top(); q.pop();
		if(mp.find(make_pair(tp.u,tp.v)) != mp.end()) continue;
		if(tp.u != tp.v && mp.find(make_pair(tp.u,tp.v)) == mp.end() && mp.find(make_pair(tp.v,tp.u)) == mp.end()){
			cnt++;
			if(cnt == k){
				printf("%lld\n",tp.w);
				return;
			}
		}
		mp[make_pair(tp.u,tp.v)] = 1;
		int rt = 0;
		for(pair<ll,int> &thp:v[tp.v]){
			rt++;
			if(rt+cnt > k) break;
			int y = thp.second;
			if(mp.find(make_pair(tp.u,y)) != mp.end()) continue;
			q.push({tp.w+thp.first,tp.u,y});
		}
	}
}
 
int main()
{
	scanf("%d%d%d",&n,&m,&k);
	rep(i,1,m){
		int x,y; ll w; scanf("%d%d%lld",&x,&y,&w);
		temp.push_back({w,y,x});
	}
	sort(temp.begin(),temp.end());
	int siz = temp.size();
	for(int i = siz-1; i >= max(siz-1-k,0); i--){
		int x = temp[i].u, y = temp[i].v, w = temp[i].w;
		v[x].push_back(make_pair(w,y));
		v[y].push_back(make_pair(w,x));
	}
	rep(i,1,n) sort(v[i].begin(),v[i].end());
	dijsktra();
	return 0;
}

4. 无向图的第k小路径

题意: 给出一个 $n$ 个点， $m$ 条边的一个图，询问图中第 $k$ 小的路径。由于并没有遇到过这样的题，只能自行 $\text{YY}$ ，因此没有数据范围。

思路: 无向图的第 $k$ 小路径，最大的问题就在于很容易计算重复。那么如何定状态才能避免算重呢？

第一个思路是对于路径 $(u,v)$ ，仅当 $v>u$ 时才更新答案。这样可以对于所有非环路径进行一个去重，避免计算重复。

第二个思路就是如何解决环的问题。我们对一条路径经过的所有边进行一个 $hash$ ，将 $hash$ 值和路径权值一起存入 $map$ ，对于路径 $(u,v)$ ，当 $u==v$ 时，我们判断当前这条路径的 $hash$ 值和路径总权值是否在 $map$ 中出现过，如果是第一次出现则记录答案。

不过这只是一个口头思路，正确性我也不会证明，只是我目前为止还没有找到反例去 $hack$ 这种做法。如果大家遇到过这个问题请在评论区留下题号，或者对这个做法有任何 $hack$ 思路的话，都可以在评论区表达自己的想法，谢谢大家。

相关标签：第k小团第k小路径第k小最短路

上一篇：主席树单点更新区间第k大

下一篇： Java Object类的方法们 java