首页 > 其他分享 >Living-Dream 系列笔记 第39期

Living-Dream 系列笔记 第39期

时间:2024-03-02 16:56:13浏览次数:42  
标签:Living 39 int tt floyd using include Dream dp

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

相关文章

  • Living-Dream 周考总结 第3期
    Link,第四场没打。T1\(100\),没挂分。\(\operatorname{lcm}(x,y)=\dfrac{x}{\gcd(x,y)}\timesy\)#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;signedmain(){ //freopen("as01.in","r",stdin); //freopen("as0......
  • Living-Dream 周考总结 第4期
    Link。T1\(100\),没挂分。依题计算即可。#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;signedmain(){ //freopen("as01.in","r",stdin); //freopen("as01.out","w",stdout); ios::sync_with_stdio(0); ......
  • Living-Dream 周考总结 第1期
    Link。T1依题计算即可,\(O(1)\)。#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;signedmain(){ ios::sync_with_stdio(0); doublen;cin>>n,n=ceil(n/5.0); cout<<setprecision(2)<<fixed; if(n<=100)cout<<0.58......
  • Living-Dream 周考总结 第2期
    Link,第二场没打。T1\(100\),没挂分。依题计算即可,\(O(1)\)。#include<bits/stdc++.h>usingnamespacestd;doublen,a,b;intmain(){ //freopen("as01.in","r",stdin); //freopen("as01.out","w",stdout); cin>>n>&......
  • 常用日期和时间标准对比:HTML, ISO 8601, RFC 3339, RFC 5322
    1.HTML,ISO8601,RFC3339,RFC5322对比日期和时间,对于不同系统和平台之间的数据交换和互操作至关重要。本文将对比HTML标准、ISO8601、RFC3339和RFC5322,为读者提供参考。表格文字版见文末-附1.1.标准链接HTML标准:https://html.spec.whatwg.org/multipage......
  • Codeforces 839E Mother of Dragons
    令\(s_u\)为点\(u\)分配到的权值。结论:最后选出来有权值的肯定是一个最大团。考虑反证,如果\(x,y\)间没有连边,则\(x,y\)的贡献是独立的,若\(\sum\limits_{(u,x)\inE}s_u\ge\sum\limits_{(v,y)\inE}s_v\),那么就可以把\(s_y\)给\(s_x\),否则把\(s_x\)给\(s_......
  • day51 动态规划part8 代码随想录算法训练营 139. 单词拆分
    题目:139.单词拆分我的感悟:背包最后一part,不错!!这题不好,不写了。理解难点:状态转移方程如何写听课笔记:首次代码及思考过程:classSolution:defwordBreak(self,s:str,wordDict:List[str])->bool:#可以用多次-->完全背包#物品是worDict集......
  • p3990-solution
    P3990Solutionlink一次只能跳一步的情况下:\(dp_{i,j}=dp_{i-1,j-1}+dp_{i-1,j}+dp_{i-1,j+1}\)接下来考虑能跳奇数步:你发现跳\(3\)步相当于先跳一个奇数\(1\)再跳一个\(2\),跳\(5\)步相当于先跳一个奇数\(3\)再跳一个\(2\)也就是说能够一步跳到\((i,j)\)的一定能......
  • Rainypaster's Daily Notebook
    写在前面记录一天生活,防颓废。因为学校要求,被迫开工,众所周知,一篇文章应该放一个头图吧。有任何问题请联系本人微信公众号:yexc的编程成长日记,大部分时候cnblogs不在线。记录2-29摘要:今天是2.29号的疯狂星期四!下一次要28年后啦~!||英语爆炸啥也不说了,上图。《小蓝本......
  • Qt Cannot open include file: 'QtConcurrent': No such file or directory
    假期手痒用Qt写了个便笺程序,其中文件操作用到了QtConcurrent模块。噼里啪啦,一通猛如虎的操作下来,代码写完了,愉快地build+run一套,结果报错了:(Cannotopenincludefile:'QtConcurrent':Nosuchfileordirectory编译不过一声吼,操起鼠标查google。官方文档就是这么写的看......