取模最短路

2019-04-14 19:21发布

站内文章 / 模拟电子
11731 0 940
题意：给你一个大小为n的集合S，集合里有n个互不相同正整数.有q个询问，每次询问是否能选择S中的一些数字 ( 同一个数字可以选择多次,也可以任何数字都不选)，使它们相加的和为m.
思路：因为给的数据很大，所以不能用背包。那么我们使用取模最短路的思想。假设我们是对a[1]进行取模。如果说我们得到了所有模a[1]余r的数中的最小的一个，记为dis[r]，那么如果有数模a[1]余r，那么只要这个数大于dis[r]，这个数就可以被表示。所以我们就用最短路算法寻找每一个dis[r]
代码：#include #include #include #include using namespace std; typedef pair p; const int maxn=20001; const int maxm=50001; const int inf=0x3f3f3f3f; int a[maxn],dis[maxm]; //dis[r]表示所有模a1余r的数中，能被表示出来的最小的数 bool vis[maxm]; priority_queue,greater

> pq; inline void dijkstra(int sz,int s) { memset(dis,inf,sizeof(dis)); memset(vis,false,sizeof(vis)); dis[s]=0; pq.push(p(s,0)); int u,d; while(!pq.empty()) { u=pq.top().first; d=pq.top().second; pq.pop(); if(vis[u]) continue; vis[u]=true; for(int i=1;i<=sz;i++) if(d+a[i]= dis[(x % a[1])]) return true; else return false; } int main() { int T; scanf("%d",&T); int n,q,t; while(T--) { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); dijkstra(n,0); scanf("%d",&q); while(q--) { scanf("%d",&t); if(query(t)) printf("YES "); else printf("NO "); } } return 0; }


热门文章