T1
一头牛能确定关系,当且仅当它能到达 / 被到达除自己外的所有牛。
于是我们建出有向图,跑 floyd 传递闭包,
然后对于每个点统计他能到达的点数是否为 \(n-1\) 即可。
#include<bits/stdc++.h>
using namespace std;
int n,m,ans;
int dp[131][131];
vector<int> G[4531];
void floyd(){
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(dp[i][k]&&dp[k][j])
dp[i][j]=1;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++) dp[i][i]=1;
for(int i=1,u,v;i<=m;i++)
cin>>u>>v,
G[u].push_back(v),
dp[u][v]=1;
floyd();
for(int i=1;i<=n;i++){
int s=0;
for(int j=1;j<=n;j++)
if(i!=j) s+=(dp[i][j]||dp[j][i]);
if(s==n-1) ans++;
}
cout<<ans;
return 0;
}
T2
bf 的做法是在线 dijkstra,\(O(QN \log N)\) 理论上能过。
我们发现 \(N\) 是很小的,于是考虑 floyd,但在线做会 T 飞。
考虑 floyd 的过程,其实就是枚举中转点进行 dp,
又由于询问的时间是单调不减的,
于是我们可以对于每个询问,将能恢复的点作为中转点跑 floyd,
若 \(x,y\) 已恢复且可联通,答案即为 \(dis(x,y)\),\(O(Q)\)。
#include<bits/stdc++.h>
using namespace std;
int n,m,q;
int tot=1;
int t[231];
int dp[231][231];
void upd(int k){
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);
}
int main(){
cin>>n>>m;
for(int i=0;i<n;i++) cin>>t[i];
for(int i=0;i<n;i++) dp[i][i]=0;
memset(dp,0x3f,sizeof(dp));
for(int i=0,u,v,w;i<m;i++)
cin>>u>>v>>w,dp[u][v]=dp[v][u]=w;
cin>>q;
int cur=0;
while(q--){
int x,y,tt; cin>>x>>y>>tt;
while(t[cur]<=tt&&cur<n) upd(cur),cur++;
if(t[x]>tt||t[y]>tt) cout<<"-1\n";
else if(dp[x][y]==0x3f3f3f3f) cout<<"-1\n";
else cout<<dp[x][y]<<'\n';
}
return 0;
}
习题 T1
思路见 TJ。
#include<bits/stdc++.h>
using namespace std;
int n,m,k;
int c[531],id[100031];
int fa[100031];
int dp[531][531];
struct E{ int u,v,w; }e[200031];
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 uni(int x,int y){ fa[fnd(x)]=fnd(y); }
void floyd(){
for(int p=1;p<=k;p++)
for(int i=1;i<=k;i++)
for(int j=1;j<=k;j++)
dp[i][j]=min(dp[i][j],dp[i][p]+dp[p][j]);
}
int main(){
cin>>n>>m>>k;
for(int i=1;i<=n;i++) fa[i]=i;
for(int i=1;i<=k;i++) cin>>c[i];
for(int i=1;i<=m;i++) cin>>e[i].u>>e[i].v>>e[i].w;
sort(e+1,e+m+1,cmp);
for(int i=1;i<=m;i++)
if(!e[i].w) uni(e[i].u,e[i].v);
for(int i=1,t=1;i<=k;i++){
int x=fnd(t); id[t]=i;
for(int j=t+1;j<t+c[i];j++){
id[j]=i;
if(fnd(j)!=x){ cout<<"No\n"; return 0; }
}
t+=c[i];
}
cout<<"Yes\n";
for(int i=1;i<=k;i++)
for(int j=1;j<=k;j++)
if(i!=j) dp[i][j]=1e9;
for(int i=1;i<=m;i++)
dp[id[e[i].u]][id[e[i].v]]=dp[id[e[i].v]][id[e[i].u]]=min(dp[id[e[i].u]][id[e[i].v]],e[i].w);
floyd();
for(int i=1;i<=k;i++){
for(int j=1;j<=k;j++) cout<<(dp[i][j]==1e9?-1:dp[i][j])<<' ';
cout<<'\n';
}
return 0;
}
标签:Living,39,int,tt,floyd,using,include,Dream,dp
From: https://www.cnblogs.com/XOF-0-0/p/18048837