P1064 （C++代码）

解题思路:





注意事项:





参考代码:

暴力枚举（其实就是普通算法的总称）

有超时的迹象，毕竟！

#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]);
}