UESTC 1633 去年春恨却来时，落花人独立，微雨燕双飞 Dijkstra+构造

去年春恨却来时，落花人独立，微雨燕双飞 Dijkstra+构造

Source

2017 UESTC Training for Graph Theory

UESTC 1633 去年春恨却来时，落花人独立，微雨燕双飞

My Solution

题意：给出一个大小为n的集合S，集合里有n个互不相同正整数.
有q个询问，每次询问是否能选择S中的一些数字 ( 同一个数字可以选择多次,也可以任何数字都不选)，
使它们相加的和为m.

Dijkstra+构造
对于S集合中的数，例如a1，考虑到如果x能够被表示出来，那么x+a1也一定能被表示出来。
故设d[r]为所有模a1余r的数中，能被表示出来的最小的数。
故可以表示出一个a1个节点a1*n条边的有向图。
d[0] = 0,丢入priority_queue<ii, vector, greater>，然后对于pq.top()的点连出的n条边进行松弛操作。
如果 d[u] + a[i] < d[(d[u] + a[i])] 则刷新并丢入队列。
跑出来的d[i]，如果d[i] != INF则都是可以表示出来的。
对于每个询问判断 q >= d[q % a[1]]即可。
时间复杂度 O(mlogn)
空间复杂度 O(n)， 不用存边。

#include 
#include 
#include 
#include 
using namespace std;
typedef long long LL;
typedef pair<int, int> ii;
const int MAXN = 2e3 + 8;
const int MAXM = 5e4 + 8;
const int INF = 1e9 + 8;
int a[MAXN], dis[MAXM];
bool vis[MAXM];
priority_queue<ii, vector, greater> pq;

inline void dijkstra(int sz, int src)
{
    for(int i = 0; i < MAXM; i++){
        dis[i] = INF;
    }
    memset(vis, false, sizeof vis);
    dis[src] = 0;
    pq.push(ii(0, src));
    int u, v, w, d, i;
    while(!pq.empty()){
        u = pq.top().second;
        d = pq.top().first;
        pq.pop();
        if(vis[u]) continue;
        vis[u] = true;
        for(i = 1; i <= sz; i++){
            if(d + a[i] < dis[(d + a[i]) % a[1]]){ dis[(d + a[i]) % a[1]] = d + a[i]; pq.push(ii(d + a[i], (d + a[i]) % a[1])); } } } } inline bool query(int x) { if(x >= dis[(x % a[1])]) return true;
    else return false;
}

int main()
{
    #ifdef LOCAL
    freopen("b.txt", "r", stdin);
    //freopen("b.out", "w", stdout);
    int T = 1;
    while(T--){
    #endif // LOCAL
    //ios::sync_with_stdio(false); cin.tie(0);

    int n, q, t, i;
    scanf("%d", &n);
    for(i = 1; i <= n; i++){
        scanf("%d", &a[i]);
    }
    dijkstra(n, 0);
    scanf("%d", &q);
    while(q--){
        scanf("%d", &t);
        if(query(t)) puts("YES");
        else puts("NO");
    }



    #ifdef LOCAL
    cout << endl;
    }
    #endif // LOCAL
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx