三十二测
无秒
2020-07-27 19:07:41
第一题travel，开始实在是看不出有啥子算法，所以就开始暴力。这很明显的bfs但是真的贼难打呀,所以先去做下一题了。后来见证了hsx大佬通过迭代加深（后面A了还来改成什么玄学剪枝，通过图的稠密度来剪枝），太强了。而更强的是，这题是思维题！如果把换乘变成另一种想法，即从一条线上一点到另一点（也就是可能换乘的点嘛）距离为1，然后算1到n最小的距离-1就是答案。把这个当做例子抽象画，就是一条链（路），当我们要求有多少个边时，可以转化成有多少个点-1。反正亦然。
代码：（注释中的输入方法也是可以的，这是在数据最后有换行的情况下，getline强一点）
```cpp
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<queue>
#include<algorithm>
#include<cstring>
using namespace std;
int n,m,tot,a;
string s;
int t[501],f[501][501];
char ch;
inline void read(int &x)
{
x=0;ch=getchar();
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
}
int main()
{
freopen("travel.in","r",stdin);
freopen("travel.out","w",stdout);
memset(f,0x3f,sizeof(f));
read(m);read(n);
while(m--)
{
tot=0;
/*read(a);
t[++tot]=a;
while(ch!='\n')
{
read(a);
t[++tot]=a;
}*/
getline(cin,s);
for(int i=0;i<s.length();i++)
{
a=0;
while(s[i]>='0'&&s[i]<='9')
{
a=(a<<1)+(a<<3)+(s[i]^48);
++i;
}
t[++tot]=a;
}
for(int i=1;i<=tot;i++)
{
f[i][i]=0;
for(int j=i+1;j<=tot;j++)
f[t[i]][t[j]]=1;
}
}
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
f[i][j]=min(f[i][k]+f[k][j],f[i][j]);
if(f[1][n]==1061109567) printf("NO");
else printf("%d",f[1][n]-1);
return 0;
}
```
第二题convey。这题注意一下细节就差不多了。因为是消耗，所以不能直接加，然后就可以自然而然的想到用1减去它，就是经过后的值比上之前的值了，然后算Floyd的时候一直乘找最大值就行了，最后用初值一乘就行了。
代码：
```cpp
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<algorithm>
using namespace std;
int n,m,x,y;
double a;
double num[101],d[101][101];
int main()
{
freopen("convey.in","r",stdin);
freopen("convey.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<n;i++) scanf("%lf",&num[i]);
for(int i=1;i<=m;i++)
{
scanf("%d%d%lf",&x,&y,&a);
d[x][y]=d[y][x]=1.00-a;
}
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
d[i][j]=max(d[i][k]*d[k][j],d[i][j]);
a=0.00;
for(int i=1;i<n;i++) a+=num[i]*d[i][n];
printf("%.2f",a);
return 0;
}
```
第三题很明显是不断更新的最小生成树，就是题解思想（时间复杂度O（n * m）），但是我打完后不断试，就发现了我的程序是直接把原来的最小生成树中最大的那个给拎出来改，但是后面发现会错，因为这条不一定是从a到b线路上的,就会导致这棵树断掉。所以就直接打了暴力，也就是当可以生成最小生成树时，每次直接求最小生成树就行了，我用的算法是Kruskal，所以算法复杂度为O（nmlog m）,其实prim的堆优化快一点，为O（nmlogn）但是n范围是500,m范围是2000,所以呢,都过得了,差不多。
代码：
```cpp
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<algorithm>
using namespace std;
struct node{
int x,y,num;double c;
}edge[2001];
bool operator <(const node z,const node zz)
{
return z.c<zz.c;
}
int fa[501],vis[501];
int jl,n,m;
double ans;
int find(int x)
{
if(fa[x]==x) return x;
return fa[x]=find(fa[x]);
}
inline void read(int &x)
{
x=0;char ch=getchar();
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
}
inline void check(int x,int y,double z,int a)
{
for(int i=1;i<=jl;i++)
if(edge[i].x==x&&edge[i].y==y)
{
if(edge[i].c>z)
{
ans=ans-edge[i].c+z;
edge[i].c=z;edge[i].num=a;
}
return;
}
}
inline void krus(int k)
{
for(int i=1;i<=n;i++) fa[i]=i;
sort(edge+1,edge+1+k);
int sum=0,i=0;ans=0;
while(sum<n-1)
{
i++;
if(find(edge[i].x)!=find(edge[i].y))
{
ans+=edge[i].c;
fa[find(edge[i].x)]=find(edge[i].y);
vis[++sum]=edge[i].num;
}
}
printf("%.1f ",ans);
for(int i=1;i<n;i++)
printf("%d ",vis[i]);
printf("\n");
}
int main()
{
freopen("Road.in","r",stdin);
freopen("Road.out","w",stdout);
int a,b;double c;
read(n);read(m);
for(int i=1;i<=n;i++) fa[i]=i;
for(int i=1;i<=m;i++)
{
read(a);read(b);scanf("%lf",&c);
if(a>b) swap(a,b);
c=c*0.5;
edge[i].num=i;edge[i].c=c;
edge[i].x=a;edge[i].y=b;
if(find(a)!=find(b))
{
fa[find(a)]=find(b);
ans+=c;
vis[++jl]=i;
if(jl!=n-1) putchar('0'),putchar('\n');
else
{
krus(i);
}
}
else
{
check(a,b,c,i);
if(jl!=n-1)
{
putchar('0'),putchar('\n');
continue;
}
else
{
krus(i);
}
}
}
return 0;
}
```
第四题先要注意它是单向边，不要被虚晃到了。然后就搜索就行了。本来打算用Dijkstra先算一算，预处理，但是时间有点仓促，就直接打了搜索，然后剪剪枝就交了，但是它过了……
代码：
```cpp
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<algorithm>
using namespace std;
int n,m,w,tot,ans=99999999;
int head[101];
struct node{
int nex,to,l,c;
}edge[10001];
bool vis[101][101];
void dfs(int x,int c,int l)
{
if(c>w) return;
if(l>=ans) return;
if(x==n)
{
ans=l;
return;
}
for(int i=head[x];i;i=edge[i].nex)
if(!vis[x][edge[i].to])
{
vis[x][edge[i].to]=1;
dfs(edge[i].to,c+edge[i].c,l+edge[i].l);
vis[x][edge[i].to]=0;
}
}
inline void read(int &x)
{
x=0;char ch=getchar();
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
}
inline void add(int u,int v,int w,int z)
{
edge[++tot].to=v;
edge[tot].l=w;
edge[tot].c=z;
edge[tot].nex=head[u];
head[u]=tot;
}
int main()
{
freopen("roads.in","r",stdin);
freopen("roads.out","w",stdout);
int s,d,l,t;
read(w);read(n);read(m);
for(int i=1;i<=m;i++)
{
read(s);read(d);read(l);read(t);
add(s,d,l,t);
}
dfs(1,0,0);
printf("%d",ans);
return 0;
}
```