65 条题解
-
3
chronix LV 8 @ 8 年前
从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]=priceif(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;
} -
315 年前@
树状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)再进行递归求解!!!(看不懂我也没办法,第一次写) -
13 年前@
加个堆,新手,请指教
-
16 年前@
说一下心路历程
最初的想法是,既然标号小的药只能从标号大的药合成,那就好说啦,直接按照每种合成结果C从大到小排序,先把大号药的最小价格和合成路线都找出来,再向上合成小号药。当所有的合成方法用完,那么输出0号药的最小价格和合成路线,就是答案了。可惜这种方法第一个点过不了,有大神能举个反例不?最后,只能看题解上Dijkstra了。思想是每次都找还没遍历过的当前价值最小的药,因为他们不可能由别的没遍历过药合成出更小的价格了。打上遍历标记之后,依次更新还没遍历过的药的最小价值和合成路数,直到所有的药都被遍历或直到遍历到0号药。
-
18 年前@
额……直觉是树型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;
}
``` -
07 年前@
好题!!!
-
07 年前@
#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");
} -
012 年前@
什么6000个点啊擦1000个点就能过……
-
012 年前@
坑死饿哦啊!!!!!!a b c 竟然有a和b相同的情况,这样就会算重啊!!!
为设么题目没给说,用边表还要特判!用矩阵就没事了... -
012 年前@
haoti
-
015 年前@
总算过了
万恶的读入
就不能给个总数吗
无意用了 seekeof
狂 Wa -
015 年前@
编译通过...
├ 测试数据 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的时候加了两条边 方案数总是比答案大 -
015 年前@
晕,我程序运行了10分钟了,啥都不出,一直在Runing
-
015 年前@
还是要弱弱的问句:为什么只能是dijkstra序而不能是SPFA[/blue]序?
还请大牛解释下先。。 -
015 年前@
编译通过...
├ 测试数据 01:答案正确... 0ms
├ 测试数据 02:答案正确... 0ms
├ 测试数据 03:答案正确... 0ms
├ 测试数据 04:答案正确... 0ms
├ 测试数据 05:答案正确... 0ms
├ 测试数据 06:答案正确... 0ms
├ 测试数据 07:答案正确... 0ms
├ 测试数据 08:答案正确... 0ms
├ 测试数据 09:答案正确... 0ms
├ 测试数据 10:答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分:100 有效耗时:0msDijkstra 秒杀
-
015 年前@
.。占个位置。。
我一直以为有
1 2 3
1 3 2
这种数据的说 -
015 年前@
我靠,标程在自己电脑上测试全对(测试数据输出都一样的),传上来之后输出却错了?!
是不是测评机有问题啊??!!
-
015 年前@
多谢hlq同学帮助!
同志任须努力! -
015 年前@
AC的第400道..
据说是个好题 ^_^ -
016 年前@
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]