Living-Dream 系列笔记 第40期

T1

bf 的做法是 \(n\) 次 floyd，实测可以卡过。

然后我们发现当点 \(u\) 为重要点时，当且仅当存在 \((a,b)\) 使得 \(u\) 为它们的唯一中转点。

于是我们令 \(vis_{i,j}\) 表示 \((i,j)\) 的唯一中转点，

接着在 floyd 的松弛操作中若能松弛则更新其为当前中转点 \(k\)，

否则若没有更优（即相等）则说明前面的重要点与 \(k\) 可相互替换，直接清空。

最后开个桶记录答案即可，时间复杂度 \(O(n^3)\)。

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

int n,m;
int dp[231][231];
int vis[231][231];
bool l[231];
int tot,ans[231];
 
void floyd(){
	for(int k=1;k<=n;k++)
		for(int i=1;i<=n;i++)
				for(int j=1;j<=n;j++){
					if(i==j||i==k||j==k) continue;
					if(dp[i][j]>dp[i][k]+dp[k][j]) dp[i][j]=dp[i][k]+dp[k][j],vis[i][j]=k;
					else if(dp[i][j]==dp[i][k]+dp[k][j]) vis[i][j]=0;
				}	
}

signed main(){
	ios::sync_with_stdio(0);
	cin>>n>>m;
	memset(dp,0x3f,sizeof(dp));
	for(int i=1;i<=n;i++) dp[i][i]=0;
	for(int i=1,u,v,w;i<=m;i++) cin>>u>>v>>w,dp[u][v]=dp[v][u]=w;
	floyd();
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			if(vis[i][j]) ans[vis[i][j]]++;
	for(int i=1;i<=n;i++) if(ans[i]) tot++;
	if(!tot) cout<<"No important cities.";
	else for(int i=1;i<=n;i++) if(ans[i]) cout<<i<<' ';
	return 0;
}

T2

法一：按曼哈顿距离 \(\div 2\) 建图跑 floyd 取 \(\max\) 即可，转移时也取 \(\max\)。

#include<bits/stdc++.h>
#define int long long
#define x first
#define y second
using namespace std;

int n;
double ans=-1e9,dp[131][131];
pair<int,int> p[131];

void floyd(){
	for(int k=1;k<=n;k++)
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				dp[i][j]=min(dp[i][j],max(dp[i][k],dp[k][j]));
}

signed main(){
	ios::sync_with_stdio(0);
	cin>>n;
	for(int i=1;i<=n;i++) cin>>p[i].x>>p[i].y;
	for(int i=1;i<=n;i++)
		for(int j=i+1;j<=n;j++)
			dp[i][j]=dp[j][i]=abs(p[i].x-p[j].x)+abs(p[i].y-p[j].y);
	floyd();
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			ans=max(ans,dp[i][j]);
	cout<<(int)(ceil(ans/2.0));
	return 0;
}

法二：同样方式建图跑 kruskal 即可。

#include<bits/stdc++.h>
#define int long long
#define x first
#define y second
using namespace std;

int n,tot;
int fa[131];
double ans,dp[131][131];
pair<int,int> p[131];
struct E{ int u,v,w; }e[10031];

bool cmp(E x,E y){ return x.w<y.w; } 
int fnd(int x){ return (fa[x]==x?x:fa[x]=fnd(fa[x])); }
void kruskal(){
	for(int i=1;i<=tot;i++){
		if(fnd(e[i].u)!=fnd(e[i].v)){
			fa[fnd(e[i].u)]=fnd(e[i].v);
			ans=max(ans,(double)e[i].w);
		}
	}
}

signed main(){
	ios::sync_with_stdio(0);
	cin>>n;
	for(int i=1;i<=n;i++) cin>>p[i].x>>p[i].y;
	for(int i=1;i<=n;i++) fa[i]=i;
	for(int i=1;i<=n;i++)
		for(int j=i+1;j<=n;j++)
			e[++tot]={i,j,abs(p[i].x-p[j].x)+abs(p[i].y-p[j].y)};
	sort(e+1,e+tot+1,cmp);
	kruskal();
	cout<<(int)(ceil(ans/2.0));
	return 0;
}

法三：二分时间用并查集 check 即可。

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

int n,tot;
int fa[131];
double ans;
pair<int,int> p[131];

int fnd(int x){ return (fa[x]==x?x:fa[x]=fnd(fa[x])); }
bool check(int x){
	for(int i=1;i<=n;i++)
		for(int j=i+1;j<=n;j++)
			if(abs(p[i].first-p[j].first)+abs(p[i].second-p[j].second)<=x*2.0)
				fa[fnd(i)]=fnd(j);
	int cnt=0;
	for(int i=1;i<=n;i++) if(fa[i]==i) cnt++;
	return cnt==1;
}

signed main(){
	ios::sync_with_stdio(0);
	cin>>n;
	for(int i=1;i<=n;i++) cin>>p[i].first>>p[i].second;
	int l=0,r=1e9+1;
	while(l+1<r){
		for(int i=1;i<=n;i++) fa[i]=i;
		int mid=(l+r)>>1;
		if(check(mid)) r=mid;
		else l=mid;
	}
	cout<<r;
	return 0;
}