NOIP模板2.zip

  • SAIWA
    了解作者
  • C/C++
    开发工具
  • 4KB
    文件大小
  • zip
    文件格式
  • 0
    收藏次数
  • 1 积分
    下载积分
  • 0
    下载次数
  • 2020-04-23 18:43
    上传日期
NOIP之前训练的时候用到的一些模板,上传一下给大家参考
NOIP模板2.zip
  • DFS求树的直径.cpp
    2.7KB
  • SPFA + 并查集.cpp
    2.5KB
  • Dijkstra + 堆.cpp
    2.4KB
  • 搞事的SPFA.cpp
    184B
内容介绍
/*Cow Marathon【树的直径模板】 题目背景 POJ1985 题目描述 After hearing about the epidemic of obesity in the USA, Farmer John wants his cows to get more exercise, so he has committed to create a bovine marathon for his cows to run. The marathon route will include a pair of farms and a path comprised of a sequence of roads between them. Since FJ wants the cows to get as much exercise as possible he wants to find the two farms on his map that are the farthest apart from each other (distance being measured in terms of total length of road on the path between the two farms). Help him determine the distances between this farthest pair of farms. 输入格式 * Line 1: Two space-separated integers: N and M. * Lines 2..M+1: Each line contains four space-separated entities, F1,F2,L,and D that describe a road.F1 and F2 are numbers of two farms connected by a road, L is its length, and D is a character that is either 'N', 'E', 'S', or 'W' giving the direction of the road from F1 to F2. 输出格式 * Line 1: An integer giving the distance between the farthest pair of farms. 样例数据 1 输入  [复制] 7 6 1 6 13 E 6 3 9 E 3 5 7 S 4 1 3 N 2 4 20 W 4 7 2 S 输出 52 备注 The longest marathon runs from farm 2 via roads 4, 1, 6 and 3 to farm 5 and is of length 20+3+13+9+7=52.*/ #include<cstdio> #include<cstdlib> #include<iostream> #include<iomanip> #include<cstring> #include<string> #include<algorithm rel='nofollow' onclick='return false;'> #include<ctime> using namespace std; const int kkk = 1000050; int n,k,x,u,v,val; int first[kkk]; struct node{int u,v,val,next;}side[2*kkk]; int cnt=0; void addedge(int u,int v,int val) { side[++cnt].u = u; side[cnt].v = v; side[cnt].val = val; side[cnt].next = first[u]; first[u] = cnt; } bool visit[kkk]; int head=0,tail=0; int p[kkk],dis[kkk]; int s1,t1,s[kkk],t[kkk]; void spfa() { memset(visit,0,sizeof(visit)); memset(dis,127,sizeof(dis)); for(int i=1;i<=s1;i++) { dis[s[i]]=0; p[++tail]=s[i]; visit[s[i]]=true; } while(head<tail) { head++; visit[p[head]]=false; for(int i=first[p[head]];i;i=side[i].next) { u = side[i].u; v = side[i].v; if(dis[v]>dis[u]+side[i].val) { dis[v] = dis[u]+side[i].val; if(!visit[v]) { tail++; p[tail]=v; visit[v]=true; } } } } } int main() //主程序,SPFA { cin >> n >> k; for(int i=1;i<=k;i++) { char c; cin >> u >> v >> val >> c; addedge(u,v,val); addedge(v,u,val); } s1=1; s[1]=1; spfa(); int jud=0; for(int i=1;i<=n;i++)if(dis[i]>jud) s[1]=i,jud=dis[i]; spfa(); int ans=0; for(int i=1;i<=n;i++)ans=max(ans,dis[i]); cout << ans << endl; return 0; }
评论
    相关推荐
    • NOIP.zip
      NOIP 2004 2008 2009 试题+答案
    • NOIP开发工具
      C++开发的工具,同时也是NOIP的开发工具,适合初级人员使用
    • ACM NOIP资料
      算法,acm大赛题,相关论文,算法竞赛入门经典训练指南,
    • NOIP2011数据
      noip2011复赛题目,数据,标程,解题报告。 DAY1.题目概况 铺地毯 选择客栈 mayan 游戏 DAY2.题目概况 计算系数 聪明的质监员 观光公交
    • NOIP算法讲解
      NOIP有关基础算法的详细讲解,适合于初学者
    • noip提高组试题
      NOIP2011)复赛 提高组 day2 1 页 共 4 页 全国信息学奥林匹克联赛(NOIP2011)复赛 提高组 day2 (请选手务必仔细阅读本页内容) 一.题目概况 中文题目名称 计算系数 聪明的质监员 观光公交 英文题目与子目录名 ...
    • NOIP模板4.zip
      NOIP之前训练的时候用到的一些模板,上传一下
    • NOIP模板3.zip
      NOIP之前训练的时候用到的一些模板,上传一下03
    • NOIP模板1.zip
      NOIP之前训练的时候用到的一些模板,上传一下
    • 迷宫求解问题.zip
      一次软件作业,迷宫的求解问题,有需要的可以直接下载,(c语言版)