解题思路:
注意事项:
参考代码:
暴力枚举(其实就是普通算法的总称)
有超时的迹象,毕竟!
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int oo=0x3f3f3f3f; struct edge { int f,t,w; bool operator < (const edge & ee) const { return w<ee.w; } } g[5010]; int fa[310],m,n,dp[310],k,t,v,q,xx[30010],yy[30010],t1[30010],t2[30010],ban[310][310],clo; int find(int x) { return x==fa[x]?x:fa[x]=find(fa[x]); } int kru(int L,int R) { int i,j,cnt=0,ret=0,u,v; clo++; for (i=1;i<=q;i++) if ((t1[i]>=L&&t1[i]<=R)||(t2[i]>=L&&t2[i]<=R)||(L>=t1[i]&&L<=t2[i])||(R>=t1[i]&&R<=t2[i])) ban[xx[i]][yy[i]]=ban[yy[i]][xx[i]]=clo; for (i=1;i<=n;i++) fa[i]=i; for (i=1;i<=m;i++) { if (ban[g[i].f][g[i].t]==clo) continue; u=find(g[i].f); v=find(g[i].t); if (u!=v) { fa[u]=v; cnt++; ret+=g[i].w; if (cnt==n-1) break; } } if (cnt==n-1) return ret; else return oo;} int main() { int i,j,p,x,y,z; scanf("%d%d%d%d%d",&n,&m,&t,&v,&k); for (i=1;i<=m;i++) scanf("%d%d%d",&g[i].f,&g[i].t,&g[i].w); scanf("%d",&q); for (i=1;i<=q;i++) scanf("%d%d%d%d",&xx[i],&yy[i],&t1[i],&t2[i]); sort(g+1,g+m+1); memset(dp,0x3f,sizeof(dp)); dp[0]=0; for (i=1;i<=t;i++) for (j=0;j<i;j++) dp[i]=min(dp[i],dp[j]+k+kru(j+1,i)*(i-j)*v); printf("%d\n",dp[t]); }
0.0分
2 人评分
printf基础练习2 (C语言代码)浏览:943 |
C语言程序设计教程(第三版)课后习题6.7 (C语言代码)浏览:520 |
A+B for Input-Output Practice (IV) (C语言代码)浏览:456 |
【金明的预算方案】 (C++代码)浏览:940 |
IP判断 (C语言描述,蓝桥杯)浏览:1095 |
复数求和 (C语言代码)浏览:929 |
上车人数 (C语言代码)浏览:713 |
生日日数 (C语言代码)浏览:1502 |
快速排序算法1浏览:885 |
1074题 初学者,求帮忙看下,不知道哪错了浏览:291 |