0712最短路选写

[CF1842D] Tenzing and His Animal Friends

Description

Tenzing 有 \(n\) 个朋友，每次举办聚会可以邀请一些朋友，有如下限制：

• \(1\) 必须参加，\(n\) 不能参加。

• 有 \(m\) 条限制 \((u, v, w)\)，表示 \(u\) 和 \(v\) 中只有一个在聚会中的总时间不超过 \(w\)。

最大化聚会总时间，并给出相应方案，即给出总聚会时间，每次聚会给出参与聚会的人和单次聚会时长。

Solution

我们考虑建图做法，首先我们可以把限制 \((u, v, w)\) 建边，而后我们考虑因为 \(n\) 不能参加聚会，所以 $u\to n $ 也有相应限制，我们考虑类似从 \(n\) 开始扩散的做法，即 \(u\) 在 \(w\) 时刻前必须从 \(n\) 走到 \(u\)，因而这样向前推可以得任何点必须在他的父节点等待 \(w_i\) 时刻前被到达，因而对于整张图考虑即相应总聚会时间最大值为 \(1\to n\) 的最短路。考虑将 \(n\) 作为起点用迪杰斯特拉算法跑最短路。不合法状态即 \(1\to n\) 最短路为极大值。

而后我们考虑构造，对于任何一个点 \(i\) 他的状态取决于当前的 \(dis_i\) 是否大于 0，大于 0 则状态为 1，反之为 0。我们考虑枚举一个时刻 \(T\) 的 \(T'=\min ({dis_k},k\in{u})\)，则在从当前时刻过渡到这个时刻所有点的 \(dis\) 均被去掉 \(T\)，因而将这个时刻和所有点的状态存进 vector 中维护即可。当 \(dis_1\) 为 0 时结束更新答案。

Code

#include<bits/stdc++.h>
using namespace std;

#define int long long
const int inf=4557430888798830398;
const int N=5e5+7;
vector<pair<int,int> > G[N];
int dis[N<<2];
bool _vis[N<<2];
int n,m,k;
int a[N];
//const int inf=1e9;

struct node{
	int dis,id;
	friend bool operator < (node a,node b){
		return a.dis>b.dis;
	}
};

void Dj(int s){
	memset(_vis,0,sizeof _vis);
	priority_queue<node> q;
	memset(dis,0x3f,sizeof dis);
	dis[s]=0;
  q.push({0,s});
	while(!q.empty()){
		int u=q.top().id;
		q.pop();
		if(_vis[u]) continue;
		_vis[u]=1;
		for(auto i:G[u]){
			int k=i.first,w=i.second;
			if(dis[k]>dis[u]+w){
				dis[k]=dis[u]+w;
				q.push({dis[k],k});
			}
		}
	}
}

struct node2 {
    int sta[110],t;
};

vector<node2> ans;

signed main(){
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=m;i++){
		int u,v,w;scanf("%lld%lld%lld",&u,&v,&w);
		G[u].push_back(make_pair(v,w)),G[v].push_back(make_pair(u,w));
	}
	Dj(n);
	if(dis[1]>=inf) return printf("inf"),0;
	printf("%lld ",dis[1]);
  while(dis[1]!=0){
	  int _min=inf;
		for(int i=1;i<=n;i++) if(dis[i]>0&&dis[i]<_min) _min=dis[i];
		node2 a;
		for(int i=1;i<=n;i++) a.sta[i]=dis[i]>0;
		a.t=_min;
		ans.push_back(a);
		for(int i=1;i<=n;i++) dis[i]-=_min;
	}
	printf("%lld\n",ans.size());
	for(auto it:ans){
	  for(int i=1;i<=n;i++){
			printf("%lld",it.sta[i]);
		}
	  printf(" %lld\n",it.t); 
	}
  return 0;
}

[CF715B] Complete The Graph

Description

给 \(n\) 点 \(m\) 边，要求你修改 \(m\) 条边中边权为 \(0\) 的边， 使满足 \(S\to T\) 的最短路长度是 \(L\)，且输出答案的时候边为 \(0\) 的边的权值必须在 \([1,1\times 10^{18}]\) 内。

Solution

我们考虑一个暴力做法，即首先我们把边权不为 \(0\) 的边的编号存进一个 vector 内，考虑仅在图中存边权不为 \(0\) 的边。而后我们跑 \(S\to T\) 的最短路极为 \(dis_t\)，我们考虑加边对这样一个 \(dis_t\) 的影响，即只会使得 \(dis_t\) 变小或不变。而后我们考虑若 \(dis_t<L\) 则显然不合法输出 NO，若 \(dis_t=L\) 则我们不希望边权为 \(0\) 的边对这张已经合法的图有任何影响，则所有边权为 \(0\) 的边权值改为极大值即可。

而后我们考虑 \(dis_t>L\) 的情况。首先，若最短路变化了那么证明从 \(S\) 到 \(T\) 的最短路经过该边，于是我们可以通过以下方式来使得最短路恰好等于 \(L\)。

而后我们考虑不断枚举边权为 \(0\) 的并且把其边权设为 \(1\) 并加入图中，这样可以使得最短路尽可能短（此时尽可能短直到 \(dis_t<L\) 时考虑修改权值，并不代表一直使最短路尽可能短，换言之这样的策略是找到一条关键边使得 \(S\) 到 \(T\) 的最短路恰好满足情况），那么我们考虑对于每次枚举跑一次最短路，若此时 \(dis_t<L\)，那么显然这种情况是不合法的，我们考虑把它补到 \(L-dis_t\)。此时恰好使得当前图合法，因而其他没枚举到的边不需要不能影响该图的最短路，因而和上面一样赋值为极大值即可。

这种贪心的思路足够通过本题。

Code

#include<bits/stdc++.h>
using namespace std;

#define int long long
const int N=5e4+7;
vector<pair<int,int> > G[N];
vector<int> vec;
int dis[N<<2];
bool _vis[N<<2];
int n,m;
int u[N],v[N],w[N];
const int inf=1e18;
int p,l,s,t;

struct node{
	int dis,id;
	friend bool operator < (node a,node b){
		return a.dis>b.dis;
	}
};

void Dj(int s){
	memset(_vis,0,sizeof _vis);
	priority_queue<node> q;
	memset(dis,0x3f,sizeof dis);
	dis[s]=0;
	q.push({0,s});
	while(!q.empty()){
		int u=q.top().id;
		q.pop();
		if(_vis[u]) continue;
		_vis[u]=1;
		for(auto i:G[u]){
			int k=i.first,w=i.second;
			if(dis[k]>dis[u]+w){
				dis[k]=dis[u]+w;
				q.push({dis[k],k});
			}
		}
	}
}

void print()
{
	puts("YES");
	for(int i=1;i<=m;i++){
		if(!w[i]){
			if(i<p)
			printf("%lld %lld %lld\n",u[i],v[i],1ll);
			if(i==p)
			printf("%lld %lld %lld\n",u[i],v[i],l-dis[t]+1);
			if(i>p)
			printf("%lld %lld %lld\n",u[i],v[i],inf);
		}
		else printf("%lld %lld %lld\n",u[i],v[i],w[i]);
	}
}

signed main(){
  scanf("%lld%lld%lld%lld%lld",&n,&m,&l,&s,&t);
  for(int i=1;i<=m;i++){
    scanf("%lld%lld%lld",&u[i],&v[i],&w[i]);
    if(!w[i]){vec.push_back(i);continue;}
    G[u[i]].push_back(make_pair(v[i],w[i]));G[v[i]].push_back(make_pair(u[i],w[i]));
  }
  Dj(s);
//  printf("dis[t]=%d\n",dis[t]);
  if(dis[t]<l) return printf("NO\n"),0;
  if(dis[t]==l){
    printf("YES\n");
    for(int i=1;i<=m;i++){
      printf("%lld %lld %lld\n",u[i],v[i],w[i]==0?inf:w[i]);
    }
    return 0;
  }
  for(int i:vec){
    G[u[i]].push_back(make_pair(v[i],1));
    G[v[i]].push_back(make_pair(u[i],1));
    Dj(s);
		if(dis[t]>l) continue;
		p=i;
		print();
		return 0;
  }
  puts("NO");
  return 0;
}