首页 > 代码库 > 2016 ACM/ICPC Asia Regional Dalian Online
2016 ACM/ICPC Asia Regional Dalian Online
1009 Sparse Graph（hdu5876）
由于每条边的权值都为1，所以最短路bfs就够了，只是要求转置图的最短路，所以得用两个set来维护，一个用来存储上次扩散还没访问的点，一个用来存储这一次扩散还没访问的点。
算法：bfs+set
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<string.h> 5 #include<queue> 6 #include<vector> 7 #include<stack> 8 #include<set> 9 using namespace std; 10 const int maxn=200100; 11 const int INF=0x3f3f3f3f; 12 int t,n,m,u,v; 13 int head[maxn];int tot; 14 int di[maxn]; 15 struct Edge 16 { 17 int to,next; 18 }edge[maxn]; 19 void init() 20 { 21 tot=0; 22 memset(head,-1,sizeof(head)); 23 } 24 void add(int u,int v) 25 { 26 edge[tot].to=v; 27 edge[tot].next=head[u]; 28 head[u]=tot++; 29 } 30 struct node 31 { 32 int num,dis; 33 }; 34 35 void bfs(int beg) 36 { 37 set<int>s,e; 38 set<int>::iterator it; 39 queue<node>q; 40 for(int i=1;i<=n;i++) 41 s.insert(i),di[i]=INF; 42 node temp,nex; 43 temp.num=beg,temp.dis=0; 44 q.push(temp); 45 s.erase(beg); 46 while(!q.empty()) 47 { 48 temp=q.front();q.pop(); 49 for(int i=head[temp.num];i!=-1;i=edge[i].next) 50 { 51 int v=edge[i].to; 52 if(s.find(v)==s.end()) 53 continue; 54 s.erase(v);e.insert(v); 55 } 56 for(it=s.begin();it!=s.end();it++) 57 { 58 nex.num=*it;nex.dis=temp.dis+1; 59 di[nex.num]=min(nex.dis,di[nex.num]); 60 q.push(nex); 61 } 62 s.swap(e);e.clear(); 63 } 64 } 65 int main() 66 { 67 //freopen("input.txt","r",stdin); 68 scanf("%d",&t); 69 while(t--) 70 { 71 scanf("%d%d",&n,&m); 72 init(); 73 for(int i=0;i<m;i++){ 74 scanf("%d%d",&u,&v); 75 add(u,v); 76 add(v,u); 77 } 78 int pos; 79 scanf("%d",&pos); 80 bfs(pos); 81 if(n!=pos){ 82 for(int i=1;i<=n;i++) 83 { 84 if(i==pos)continue; 85 if(i!=n) 86 printf("%d ",di[i]!=INF?di[i]:-1); 87 else 88 printf("%d\n",di[i]!=INF?di[i]:-1); 89 } 90 91 }else{ 92 for(int i=1;i<=n-2;i++) 93 { 94 if(1!=(n-1)) 95 printf("%d ",di[i]!=INF?di[i]:-1); 96 else 97 printf("%d\n",di[i]!=INF?di[i]:-1); 98 } 99 100 }101 } 102 return 0;103 }
1010 Weak Pair（hdu5877）
题意是要求所有节点的权值与其祖先节点权值相乘小于或等于k的总共有多少对，一开始知道必须得进行dfs，也知道可以马上建一个数组b[n]来记录每个节点需要和小于多少的数相乘才会小于看，但是在查询有多少个祖先节点小于b[i]时没有找到方法，后来才知道，可以将数据离散化后存进树状数组，只保留当前节点的父节点在树状数组当中，一旦离开这个节点，就把这个节点的权值在树状数组中删除
算法：dfs+离散化+BIT
1 #include<iostream> 2 #include<algorithm> 3 #include<cstdio> 4 #include<string.h> 5 #include<vector> 6 #include<queue> 7 #include<stack> 8 using namespace std; 9 #define ll long long10 const int maxn=100100;11 int n;12 ll k,a[maxn];13 vector<int>son[maxn];14 ll ran[maxn];15 ll b[maxn];16 int in[maxn];17 ll B[maxn];18 int low_bit(int x)19 {20 return x&(-x);21 }22 ll Sum(int x){23 ll s1 = 0;24 while (x) s1 += B[x], x -= low_bit(x);25 return s1;26 }27 void Add(int x, int d){28 while (x<=n) B[x] += d,x += low_bit(x);29 }30 void init(int n)31 {32 for(int i=1;i<=n;i++){33 son[i].clear();34 }35 memset(in,0,sizeof(in));36 }37 ll dfs(int rt)38 {39 Add(ran[rt],1);40 ll ans=0;41 for(int i=0;i<son[rt].size();i++){42 int nex=son[rt][i];43 ans+=dfs(nex);44 }45 Add(ran[rt], -1);46 ll num=upper_bound(a+1,a+1+n,b[rt])-a-1;47 ans+=Sum(num);48 return ans;49 }50 int main()51 {52 //freopen("input.txt","r",stdin);53 int t; scanf("%d", &t);54 while(t--)55 {56 scanf("%d%lld",&n,&k);57 init(n);58 for(int i=1;i<=n;i++){59 scanf("%lld",&a[i]);60 ran[i] = a[i];61 if (a[i] != 0)62 b[i] = k / a[i];63 else64 b[i] = 0;65 }66 67 int u,v;68 for(int i=1;i<=n-1;i++){69 scanf("%d%d",&u,&v);70 son[u].push_back(v);71 in[v]++;72 }73 sort(a+1,a+1+n);74 unique(a+1,a+1+n);75 for(int i=1;i<=n;i++){76 ran[i]=lower_bound(a+1,a+n+1,ran[i])-a;77 }78 int root=1;79 for(int i=1;i<=n;i++){80 if(in[i]==0)81 root=i;82 }83 ll ans=dfs(root);84 printf("%lld\n",ans);85 }86 return 0;87 }
2016 ACM/ICPC Asia Regional Dalian Online
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。