题解 - Vijos

3

chronix LV 8 @ 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

hxlong LV 10 @ 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

zwz LV 7 @ 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

Lifi LV 10 @ 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

qig159357 LV 8 @ 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

天神塞勒涅 LV 10 @ 2018-04-14 19:14:43

好题！！！

0

Amove LV 8 @ 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

wyc4662 LV 10 @ 2013-04-26 20:29:20

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

0

silence_sure LV 8 @ 2012-10-22 21:39:22

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

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

0

write LV 7 @ 2012-09-23 16:07:18

haoti

0

yzl609271536 LV 10 @ 2009-11-11 19:13:19

总算过了

万恶的读入

就不能给个总数吗

无意用了 seekeof

狂 Wa

0

我最正直 LV 8 @ 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

ljz_yal LV 6 @ 2009-08-28 15:28:40

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

0

sdfasd LV 9 @ 2009-08-22 21:10:13

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

还请大牛解释下先。。

0

peng7621260 LV 9 @ 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

JoshuaBraynt LV 8 @ 2009-08-08 21:55:45

.。占个位置。。

我一直以为有

1 2 3

1 3 2

这种数据的说

0

zh314513 LV 7 @ 2009-07-10 10:16:03

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

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

0

G_D_inferno LV 10 @ 2009-06-13 21:14:27

多谢hlq同学帮助！

同志任须努力！

0

cgy4ever LV 10 @ 2009-06-11 23:31:54

AC的第400道..

据说是个好题 ^_^

0

578559967 LV 10 @ 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]

题解

65 条题解

佳佳的魔法药水

信息

状态

开发

支持

题解

65 条题解

佳佳的魔法药水

信息

状态

开发

支持

还没有账户？

登录