hdu7055 /2021“MINIEYE杯”中国大学生算法设计超级联赛(7) 1007 Link with Limit
2021/9/1 22:06:14
本文主要是介绍hdu7055 /2021“MINIEYE杯”中国大学生算法设计超级联赛(7) 1007 Link with Limit,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
https://acm.hdu.edu.cn/showproblem.php?pid=7050
题意相当于问n个点n条边的有向图(可能有自环),是否所有的环的平均值相等
用tarjan找环效果不甚理想,还是std的拓扑排序妙
#include<bits/stdc++.h> using namespace std; #define N 100001 int to[N]; int dfn[N],low[N],id; int st[N],top; bool in[N]; double last,now; int sum; const double eps=1e-8; bool equal(double a,double b) { return fabs(a-b)<eps; } void tarjan(int u) { low[u]=dfn[u]=++id; st[++top]=u; in[u]=true; int t=to[u]; if(!dfn[t]) { tarjan(t); low[u]=min(low[u],low[t]); } else if(in[t]) low[u]=min(low[u],dfn[t]); if(low[u]==dfn[u]) { if(st[top]==u) { in[u]=false; top--; return; } while(st[top]!=u) { in[st[top]]=false; now+=st[top--]; sum++; } now+=st[top--]; sum++; in[u]=false; } } int main() { //freopen("input.txt","r",stdin); //freopen("my.txt","w",stdout); int T,n; int self,who; bool tag; scanf("%d",&T); while(T--) { scanf("%d",&n); for(int i=1;i<=n;++i) { dfn[i]=0; in[i]=false; } id=0; self=0; for(int i=1;i<=n;++i) { scanf("%d",&to[i]); if(to[i]==i) { ++self; who=i; } } if(self>1) { printf("NO\n"); continue; } last=-1; if(self==1) { last=who; dfn[who]=1; } tag=true; for(int i=1;i<=n && tag;++i) { if(dfn[i]) continue; now=0; top=sum=0; tarjan(i); if(!sum) continue; now/=sum; if(!equal(now,last) && !equal(last,-1)) tag=false; last=now; } if(tag) printf("YES\n"); else printf("NO\n"); } }View Code
#include <stdio.h> #include <queue> #define MN 100000 typedef long long ll; int n,a[MN+5],din[MN+5]; void solve(){ scanf("%d",&n); for(int i=1;i<=n;i++){ din[i] = 0; } for(int i=1;i<=n;i++){ scanf("%d",&a[i]); din[a[i]]++; } std::queue<int> Q; for(int i=1;i<=n;i++){ if(din[i]==0) Q.push(i); } while(!Q.empty()){ int u = Q.front(); Q.pop(); din[a[u]]--; if(din[a[u]]==0){ Q.push(a[u]); } } ll p=-1,q=-1; for(int i=1;i<=n;i++){ if(din[i]==0) continue; ll tp=0,tq=0; for(;din[i];i=a[i]){ tp += i; tq++; din[i] = 0; } if(p==-1){ p = tp; q = tq; }else{ if(p*tq!=q*tp){ puts("NO"); return; } } } puts("YES"); return; } int main(){ int T; scanf("%d",&T); while(T--) solve(); }View Code
这篇关于hdu7055 /2021“MINIEYE杯”中国大学生算法设计超级联赛(7) 1007 Link with Limit的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-11-02Java管理系统项目实战入门教程
- 2024-11-02Java监控系统项目实战教程
- 2024-11-02Java就业项目项目实战:从入门到初级工程师的必备技能
- 2024-11-02Java全端项目实战入门教程
- 2024-11-02Java全栈项目实战:从入门到初级应用
- 2024-11-02Java日志系统项目实战:初学者完全指南
- 2024-11-02Java微服务系统项目实战入门教程
- 2024-11-02Java微服务项目实战:新手入门指南
- 2024-11-02Java项目实战:新手入门教程
- 2024-11-02Java小程序项目实战:从入门到简单应用