65 条题解

  • 3
    @ 2016-08-13 10:51:32

    从0点开始DFS
    best[]记录最佳值,way[]记录方法数
    对于环的处理:
    vis[]标记,若vis[x]=1,则best[x]=price[x]
    #include <cstdio>
    #include <queue>

    struct edge{
    int v;
    edge *link;
    };

    int n,m,top=0;
    int vis[1010]={0},price[1010];
    int best[1010],way[1010];
    edge graph[1010]={0};
    edge node[100000];

    void add(int u,int v){
    edge *l=&node[top++];
    l->v=v;
    l->link=graph[u].link;
    graph[u].link=l;
    }

    typedef std::pair<int,int> pii;

    inline pii dfs(int u){

    edge *l=&graph[u];
    int s1,s2,c1,c2;
    pii q1,q2,q;
    if(best[u]>0)
    return std::make_pair(best[u],way[u]);
    q.first=99999999;
    vis[u]=1;
    while(l->link){
    l=l->link,s1=l->v;
    l=l->link,s2=l->v;
    //vis[x]=1 →best[x]=price

    if(vis[s1]==1)
    q1.first=price[s1],q1.second=1;
    else
    q1=dfs(s1);
    if(vis[s2]==1)
    q2.first=price[s2],q2.second=1;
    else
    q2=dfs(s2);

    if(q.first==q1.first+q2.first){
    q.second+=q1.second*q2.second;
    }
    if(q.first>q1.first+q2.first){
    q.first=q1.first+q2.first;
    q.second=q1.second*q2.second;
    }
    }
    if(q.first==price[u])
    q.second++;
    if(q.first>price[u])
    q.first=price[u],q.second=1;
    vis[u]=0;
    best[u]=q.first;
    way[u]=q.second;
    return q;
    }

    int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    best[i]=-1;
    for(int i=0;i<n;i++)
    scanf("%d",&price[i]);
    int T1,T2,T3;
    while(scanf("%d%d%d",&T1,&T2,&T3)!=EOF){
    add(T3,T1);
    add(T3,T2);
    }
    pii ans=dfs(0);
    printf("%d %d",ans.first,ans.second);
    return 0;
    }

  • 3
    @ 2009-08-29 08:41:41

    树状DP

    环的处理:对与 1 2 3

    2 3 1

    数据 欲求药水3的最优值,因为药水3需要用到药水1,药水1需要用到药水3,那么

    dp[1]+dp[2]>min(dp[3])即以药水1,2混合得来的绝对不是药水3的最优值。因为

    药水1已经包含3的最优值,3包含了3的最优值,这样由1,2的得来的

    dp[3]=dp[2]+dp[3]+其他药水最优值,如果去掉DP[2]与其他药水最优值绝对更优

    这种环的处理只要加个BOOLEAN判断,在递归求解时对于已经递归的药水不再进行求解(FALSE)!只有(TRUE)再进行递归求解!!!(看不懂我也没办法,第一次写)

  • 1
    @ 2021-10-14 21:25:31

    加个堆,新手,请指教

    #include<bits/stdc++.h>
    using namespace std;
    #define P pair<int,int> 
    #define v first 
    #define x second
    const int N=1010;
    vector<P>g[N];
    int dis[N],num[N],vis[N];
    priority_queue<P,vector<P>,greater<P> >q;
    int main(){
        int n,m,a,b,c;
        scanf("%d",&n);
        for(int i=0;i<n;i++){
            scanf("%d",&dis[i]);
            num[i]=1;
            q.push(make_pair(dis[i],i));
        }
        while(~scanf("%d%d%d",&a,&b,&c)){
            g[a].push_back(make_pair(c,b));
            if(a==b) continue;
            g[b].push_back(make_pair(c,a));
        }
        while(!q.empty()){
            P f=q.top();q.pop();vis[f.x]=1;
            if(f.v!=dis[f.x]) continue;
            for(int i=0;i<g[f.x].size();i++){
                P s=g[f.x][i];
                if(!vis[s.x]) continue;
                if(dis[s.v]>f.v+dis[s.x]){
                    num[s.v]=num[f.x]*num[s.x];
                    q.push(make_pair(dis[s.v]=f.v+dis[s.x],s.v));
                }
                else if(dis[s.v]==f.v+dis[s.x])
                    num[s.v]+=num[f.x]*num[s.x];
            }
        }
        printf("%d %d\n",dis[0],num[0]);
        return 0;
    }
    
  • 1
    @ 2019-05-09 16:51:01

    说一下心路历程
    最初的想法是,既然标号小的药只能从标号大的药合成,那就好说啦,直接按照每种合成结果C从大到小排序,先把大号药的最小价格和合成路线都找出来,再向上合成小号药。当所有的合成方法用完,那么输出0号药的最小价格和合成路线,就是答案了。可惜这种方法第一个点过不了,有大神能举个反例不?

    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    
    using namespace std;
    
    typedef struct
    {
        int a,b,c;
    }un;
    
    int n,m=0;
    int p[1000];
    un u[1000000];
    int t[1000];
    
    bool comp(un x,un y)
    {
        return x.c>y.c;
    }
    
    int main()
    {
        cin>>n;
        int i;
        for(i=0;i<n;i++)
        {
            cin>>p[i];
            t[i]=1;
        }
        int a,b,c;
        while(scanf("%d%d%d",&a,&b,&c)!=EOF)
        {
            u[m].a=a;
            u[m].b=b;
            u[m].c=c;
            m++;
        }
        sort(u,u+m,comp);
        for(i=0;i<m;i++)
        {
            if(p[u[i].c]>p[u[i].a]+p[u[i].b])
            {
                p[u[i].c]=p[u[i].a]+p[u[i].b];
                t[u[i].c]=t[u[i].a]*t[u[i].b];
            }
            else if(p[u[i].c]==p[u[i].a]+p[u[i].b])
            {
                t[u[i].c]+=t[u[i].a]*t[u[i].b];
            }
        }
        cout<<p[0]<<' '<<t[0]<<endl;
        return 0;
    }
    

    最后,只能看题解上Dijkstra了。思想是每次都找还没遍历过的当前价值最小的药,因为他们不可能由别的没遍历过药合成出更小的价格了。打上遍历标记之后,依次更新还没遍历过的药的最小价值和合成路数,直到所有的药都被遍历或直到遍历到0号药。

    #include <iostream>
    #include <cstdio>
    #include <cstring>
    
    using namespace std;
    
    int n;
    int p[1000];
    int un[1000][1000];
    int w[1000];
    bool vis[1000]={0};
    
    int main()
    {
        cin>>n;
        int i,j,k;
        memset(un,-1,sizeof(un));
        for(i=0;i<n;i++)
        {
            cin>>p[i];
            w[i]=1;
        }
        while(scanf("%d%d%d",&i,&j,&k)!=EOF)
        {
            un[i][j]=k;
            un[j][i]=k;
        }
        int mi;
        for(i=0;i<n;i++)
        {
            mi=1e9;
            k=0;
            for(j=0;j<n;j++)
            {
                if(!vis[j]&&mi>p[j])
                {
                    k=j;
                    mi=p[j];
                }
            }
            vis[k]=true;
            for(j=0;j<n;j++)
            {
                if(vis[j])
                {
                    if(p[un[j][k]]>p[j]+p[k])
                    {
                        p[un[j][k]]=p[j]+p[k];
                        w[un[j][k]]=w[j]*w[k];
                    }
                    else if(p[un[j][k]]==p[j]+p[k])
                    {
                        w[un[j][k]]+=w[j]*w[k];
                    }
                }
            }
        }
        cout<<p[0]<<' '<<w[0]<<endl;
        return 0;
    }
    
  • 1
    @ 2016-06-13 22:08:13

    额……直觉是树型DP,结果存在环……只好用Dijkstra。
    好题,不过要注意a==b的情况,不要算重了。
    ```c++
    #include<cstdio>
    #include<cstring>
    #include<vector>
    #include<queue>
    using namespace std;
    const int INF = 2147483647;

    struct Ing
    {
    int a,b;
    Ing(int x=0,int y=0) : a(x),b(y) {};
    };

    struct Po
    {
    int pr,u;
    Po(int a=0,int b=0) : pr(a),u(b) {}
    bool operator< (const Po &x) const { return pr>x.pr || (pr==x.pr && u > x.u) ;}
    };

    vector<Ing> ingredients[1010];
    bool vis[1010];
    int n,price[1010];
    int min_price[1010];
    long long int scheme_num[1010];

    void Dijkstra()
    {
    memset(vis,0,sizeof(vis));
    priority_queue<Po> q;
    for(int i=0;i<n;i++)
    {
    min_price[i]=price[i];
    scheme_num[i]=1;
    q.push(Po(price[i],i));
    }
    while(!q.empty())
    {
    int now=(q.top()).u;q.pop();
    if(vis[now]) continue;
    vis[now]=true;
    for(int i=0;i<(int)ingredients[now].size();i++)
    if(vis[ingredients[now][i].a]&&min_price[ingredients[now][i].b]>=min_price[now]+min_price[ingredients[now][i].a])
    {
    scheme_num[ingredients[now][i].b] = min_price[ingredients[now][i].b]==min_price[now]+min_price[ingredients[now][i].a] ?
    scheme_num[ingredients[now][i].b]+scheme_num[ingredients[now][i].a]*scheme_num[now] : scheme_num[ingredients[now][i].a]*scheme_num[now];
    min_price[ingredients[now][i].b]=min_price[now]+min_price[ingredients[now][i].a];
    q.push(Po(min_price[ingredients[now][i].b],ingredients[now][i].b));
    }
    }
    }

    int main()
    {
    /*freopen("in","r",stdin);*/
    memset(min_price,-1,sizeof(min_price));
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    scanf("%d",&price[i]);
    int a,b,c;
    while(scanf("%d%d%d",&a,&b,&c)==3)
    {
    ingredients[a].push_back(Ing(b,c));
    if(a!=b)ingredients[b].push_back(Ing(a,c));
    }
    Dijkstra();
    printf("%d %lld\n",min_price[0],scheme_num[0]);
    return 0;
    }
    ```

  • 0
    @ 2018-04-14 19:14:43

    好题!!!

  • 0
    @ 2018-02-07 18:19:16

    #include<iostream>
    #include<cstdio>
    #include<cstdlib>
    #include<cstring>
    #include<string>
    #include<algorithm>
    #include<cmath>
    #include<map>
    #include<vector>
    #include<stack>
    using namespace std;
    const int inf= 1 << 28;
    int N,M,val[1005],mmp[1005][1005],cnt[1005];
    bool flag[1005];
    void init()
    {
    for(int i=0;i<=N;i++)
    {
    for(int j=0;j<=N;j++)
    {
    mmp[i][j]=inf;
    }
    cnt[i]=1;
    }
    memset(flag,true,sizeof(flag));
    }
    void read()
    {
    scanf("%d",&N);
    for(int i=0;i<N;i++)
    scanf("%d",&val[i]);
    init();
    int x,y,to;
    while(scanf("%d%d%d",&x,&y,&to)!=EOF)
    {
    mmp[x][y]=mmp[y][x]=to;
    }
    }
    void dij()
    {
    int i,j,k;
    for(i=0;i<N;i++)
    {
    int minn=inf,p;
    for(j=0;j<N;j++)
    {
    if(val[j]<minn&&flag[j])
    minn=val[p=j];
    }
    flag[p]=false;
    for(j=0;j<N;j++)
    {
    if(!flag[j]&&mmp[p][j]<inf)//注意是!flag[j]
    {
    if(val[mmp[p][j]]>val[p]+val[j])
    {
    val[mmp[p][j]]=val[p]+val[j];
    cnt[mmp[p][j]]=(cnt[p]*cnt[j]);
    }
    else if(val[mmp[p][j]]==val[p]+val[j])
    {
    cnt[mmp[p][j]]+=(cnt[p]*cnt[j]);
    }
    }
    }
    }
    printf("%d %d\n",val[0],cnt[0]);
    }
    int main()
    {
    read();
    dij();
    system("pause");
    }

  • 0
    @ 2013-04-26 20:29:20

    什么6000个点啊擦1000个点就能过……

  • 0
    @ 2012-10-22 21:39:22

    坑死饿哦啊!!!!!!a b c 竟然有a和b相同的情况,这样就会算重啊!!!

    为设么题目没给说,用边表还要特判!用矩阵就没事了...

  • 0
    @ 2012-09-23 16:07:18

    haoti

  • 0
    @ 2009-11-11 19:13:19

    总算过了

    万恶的读入

    就不能给个总数吗

    无意用了 seekeof

    狂 Wa

  • 0
    @ 2009-11-07 16:35:07

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

    调了两天 没注意 重复构图了

    a=b的时候加了两条边 方案数总是比答案大

  • 0
    @ 2009-08-28 15:28:40

    晕,我程序运行了10分钟了,啥都不出,一直在Runing

  • 0
    @ 2009-08-22 21:10:13

    还是要弱弱的问句:为什么只能是dijkstra序而不能是SPFA[/blue]序?

    还请大牛解释下先。。

  • 0
    @ 2009-08-13 11:42:45

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

    Dijkstra 秒杀

  • 0
    @ 2009-08-08 21:55:45

    .。占个位置。。

    我一直以为有

    1 2 3

    1 3 2

    这种数据的说

  • 0
    @ 2009-07-10 10:16:03

    我靠,标程在自己电脑上测试全对(测试数据输出都一样的),传上来之后输出却错了?!

    是不是测评机有问题啊??!!

  • 0
    @ 2009-06-13 21:14:27

    多谢hlq同学帮助!

    同志任须努力!

  • 0
    @ 2009-06-11 23:31:54

    AC的第400道..

    据说是个好题 ^_^

  • 0
    @ 2009-06-04 17:48:11

    type

    link=^node;

    node=record

    r,l:longint;

    next:link;

    end;

    var

    visit,a,kind :array[0..1000]of longint;

    n,i,x,y,z :longint;

    g :array[0..1000]of link;

    procedure make(x,y,z:longint);

    var

    p :link;

    begin

    if visit[z]=0 then begin visit[z]:=1;new(g[z]);g[z]:=nil; end;

    new(p);

    p^.r:=x;

    p^.l:=y;

    p^.next:=g[z];

    g[z]:=p;

    end;

    procedure work(i:longint);

    var

    p,q :link;

    begin

    p:=g[i];

    kind[i]:=1;

    while pnil do

    begin

    if kind[p^.r]=0 then

    if visit[p^.r]=0 then kind[p^.r]:=1 else work(p^.r);

    if kind[p^.l]=0 then

    if visit[p^.l]=0 then kind[p^.l]:=1 else work(p^.l);

    if a[p^.r]+a[p^.l]

信息

ID
1285
难度
6
分类
动态规划 | 图结构 | 最短路 点击显示
标签
递交数
1477
已通过
394
通过率
27%
被复制
4
上传者