首页 > 代码库 > BZOJ 2612 [Poi2003]Sums（最短路）

BZOJ 2612 [Poi2003]Sums（最短路）

2024-11-18 04:42:02   202人阅读

 

【题目链接】 http://www.lydsy.com/JudgeOnline/problem.php?id=2612

 

【题目大意】

　　给定a数组，问num能否被表示为a[1]*x[1]+a[2]*x[2]+……+a[n]*x[n]，x为非负整数

 

【题解】

　　设a1为最小数字，
　　若方程a[1]*x[1]+a[2]*x[2]+……+a[n]*x[n]=k存在非负整数解，那么k+a1也必然有解。
　　建立a1个点的图，点编号为0到a1-1,i向(i+aj)%a1连边，边权为aj，求src为0的最短路，
　　如果dis[k%a1]<=k，那么k有解。

 

【代码】

#include <cstdio>#include <algorithm>#include <vector>#include <utility>#include <queue> using namespace std;const int N=50010,INF=0x3f3f3f3f;namespace DIJKSTRA{    typedef pair<int,int>P;    priority_queue<P,vector<P>,greater<P> >Q;    int a[N],d[N],n,m;    void Initialize(){        int x,i;        sort(a,a+n); m=a[0];        for(i=1;i<m;i++)d[i]=INF;Q.push(P(0,0));        while(!Q.empty()){            P t=Q.top();Q.pop();            if(d[t.second]<t.first)continue;            for(x=t.second,i=1;i<n;i++){                if(d[x]+a[i]<d[(x+a[i])%m])Q.push(P(d[(x+a[i])%m]=d[x]+a[i],(x+a[i])%m));            }        }    }    bool Check(int x){return d[x%m]<=x;}    int Cal(int k){for(int i=0;i<m;i++)if(d[(k+i)%m]<=k+i)return k+i;}}int main(){    using namespace DIJKSTRA;    scanf("%d",&n);    for(int i=0;i<n;i++)scanf("%d",&a[i]);    Initialize(); int k;    scanf("%d",&k);    while(k--){        int x;        scanf("%d",&x);        if(Check(x))puts("TAK");        else puts("NIE");    }return 0;}

BZOJ 2612 [Poi2003]Sums（最短路）


联系
我们