首页    技术博客    PHP教程    数据库技术    前端开发   HTML5    Nginx    php论坛
新用户注册 | 会员登录
加入会员，解锁专属内容
取消
热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

[CQOI2015]网络吞吐量

作者：小白一枚 | 来源：互联网 | 2023-10-11 14:38
Description:给你一个图,每个点可以被经过\(a_i\)次,求有多少个人可以走最短路到n点Hint:\(n\le500\)Solution:极其水的一道题,就当做复习

Description:

给你一个图,每个点可以被经过\(a_i\)次,求有多少个人可以走最短路到n点

Hint:

\(n \le 500\)

Solution:

极其水的一道题,就当做复习最短路板子了

先跑最短路,然后把满足\(dis[v]=dis[u]+t[i].w\)的点连起来,拆个点就完事了

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define ls p<<1 
#define rs p<<1|1
using namespace std;
typedef long long ll;
const ll mxn=2e5+5,inf=1e18;
ll S,T,n,m,k,cnt,cnt1,ans,dis[mxn],vis[mxn],hd1[mxn],a[mxn],dep[mxn],cur[mxn],mp[500][500],hd[mxn];
ll dx[9]={1,1,-1,-1,3,3,-3,-3};
ll dy[9]={3,-3,3,-3,1,-1,1,-1};

inline ll read() {
    char c=getchar(); ll x=0,f=1;
    while(c>'9'||c<'0') {if(c=='-') f=-1;c=getchar();}
    while(c<='9'&&c>='0') {x=(x<<3)+(x<<1)+(c&15);c=getchar();}
    return x*f;
}
inline void chkmax(ll &x,ll y) {if(xy) x=y;}

struct ed {
    ll to,nxt,w;
}t[mxn<<1],t1[mxn<<1];

void add1(ll u,ll v,ll w) {
    t1[++cnt1]=(ed) {v,hd1[u],w}; hd1[u]=cnt1;
}

inline void add(ll u,ll v,ll w) {
    t[cnt]=(ed) {v,hd[u],w}; hd[u]=cnt++;
    t[cnt]=(ed) {u,hd[v],0}; hd[v]=cnt++;
}

ll bfs() {
    memset(dep,0,sizeof(dep)); queue q;
    q.push(S); dep[S]=1;
    for(ll i=0;i<=n*2+1;++i) cur[i]=hd[i];
    while(!q.empty()) {
        ll u=q.front(); q.pop();
        for(ll i=hd[u];i!=-1;i=t[i].nxt) {
            ll v=t[i].to;
            if(dep[v]==0&&t[i].w>0) 
                dep[v]=dep[u]+1,q.push(v);
        }
    }
    if(dep[T]==0) return 0;
    return 1;
}

ll dfs(ll u,ll f) {
    if(u==T) return f;
    for(ll &i=cur[u];i!=-1;i=t[i].nxt) {
        ll v=t[i].to;
        if(dep[v]==dep[u]+1&&t[i].w>0) {
            ll tp=dfs(v,min(f,t[i].w));
            if(tp>0) {
                t[i].w-=tp;
                t[i^1].w+=tp;
                return tp;
            }
        }
    }
    return 0;
}

void Dinic() {
    while(bfs())
        while(ll tp=dfs(S,inf)) 
            {ans+=tp;}
}

ll get(ll x,ll y) {
    return (x-1)*m+y;
}

priority_queue > q;

void Dij() {
    q.push(make_pair(0,1)); memset(dis,0x3f,sizeof(dis));
    dis[1]=0;
    while(!q.empty()) {
        ll u=q.top().second; q.pop(); 
        if(vis[u]) continue ;
        for(ll i=hd1[u];i;i=t1[i].nxt) {
            ll v=t1[i].to;
            if(vis[v]) continue ;
            if(dis[v]>dis[u]+t1[i].w) {
                dis[v]=dis[u]+t1[i].w; 
                q.push(make_pair(-dis[v],v));
            }
        }
    }
}

void init() {
    for(ll i=1;i<=n;++i) {
        for(ll j=hd1[i];j;j=t1[j].nxt) {
            ll v=t1[j].to;
            if(dis[v]==dis[i]+t1[j].w) add(i+n,v,inf);
        }
    }
}

int main()
{
    memset(hd,-1,sizeof(hd)); ll u,v,w; 
    n=read(); m=read(); T=2*n+1; add(S,1,inf); add(1,n+1,inf); add(n,n+n,inf);  add(n+n,T,inf);
    for(ll i=1;i<=m;++i) {
        u=read(); v=read(); w=read();
        add1(u,v,w); add1(v,u,w);
    }
    a[1]=read();
    for(ll i=2;i

推荐阅读
  • get

    [CF949D]Curfew 二分答案是个不错的开头，困难部分在于如何检查

    本文介绍了一个题目的解法，通过二分答案来解决问题，但困难在于如何进行检查。文章提供了一种逃逸方式，通过移动最慢的宿管来锁门时跑到更居中的位置，从而使所有合格的寝室都居中。文章还提到可以分开判断两边的情况，并使用前缀和的方式来求出在任意时刻能够到达宿管即将锁门的寝室的人数。最后，文章提到可以改成O(n)的直接枚举来解决问题。 ... [详细]
  • go

    差分约束系统求解House Man跳跃问题的思路与方法

    本文讨论了使用差分约束系统求解House Man跳跃问题的思路与方法。给定一组不同高度，要求从最低点跳跃到最高点，每次跳跃的距离不超过D，并且不能改变给定的顺序。通过建立差分约束系统，将问题转化为图的建立和查询距离的问题。文章详细介绍了建立约束条件的方法，并使用SPFA算法判环并输出结果。同时还讨论了建边方向和跳跃顺序的关系。 ... [详细]
  • go

    clone的fork与pthread_create创建线程有何不同

    本文讨论了clone的fork与pthread_create创建线程的不同之处。进程是一个指令执行流及其执行环境，其执行环境是一个系统资源的集合。在调用系统调用fork创建一个进程时，子进程只是完全复制父进程的资源，这样得到的子进程独立于父进程，具有良好的并发性。但是二者之间的通讯需要通过专门的通讯机制，另外通过fork创建子进程系统开销很大。因此，在某些情况下，使用clone或pthread_create创建线程可能更加高效。 ... [详细]
  • go

    如何使用PHP向系统日历中添加事件？

    本文介绍了如何使用PHP向系统日历中添加事件的方法，通过使用PHP技术可以实现自动添加事件的功能，从而实现全局通知系统和迅速记录工具的自动化。同时还提到了系统exchange自带的日历具有同步感的特点，以及使用web技术实现自动添加事件的优势。 ... [详细]
  • range

    电话号码的字母组合解题思路和代码示例

    电话号码的字母组合解题思路和代码示例
    本文介绍了力扣题目《电话号码的字母组合》的解题思路和代码示例。通过使用哈希表和递归求解的方法，可以将给定的电话号码转换为对应的字母组合。详细的解题思路和代码示例可以帮助读者更好地理解和实现该题目。 ... [详细]
  • range

    九度OnlineJudge之1002：Grading问题的解决方法

    本文介绍了九度OnlineJudge中的1002题目“Grading”的解决方法。该题目要求设计一个公平的评分过程，将每个考题分配给3个独立的专家，如果他们的评分不一致，则需要请一位裁判做出最终决定。文章详细描述了评分规则，并给出了解决该问题的程序。 ... [详细]
  • get

    Open judge C16H: Magical Balls 快速幂+逆元问题解析

    本文主要解析了Open judge C16H问题中涉及到的Magical Balls的快速幂和逆元算法，并给出了问题的解析和解决方法。详细介绍了问题的背景和规则，并给出了相应的算法解析和实现步骤。通过本文的解析，读者可以更好地理解和解决Open judge C16H问题中的Magical Balls部分。 ... [详细]
  • get

    油田地块的划分和计数方法

    本文介绍了一种划分和计数油田地块的方法。根据给定的条件，通过遍历和DFS算法，将符合条件的地块标记为不符合条件的地块，并进行计数。同时，还介绍了如何判断点是否在给定范围内的方法。 ... [详细]
  • 数组

    P1651 塔 (动态规划) 的最大高度计算方法

    本文介绍了P1651题目的描述和要求，以及计算能搭建的塔的最大高度的方法。通过动态规划和状压技术，将问题转化为求解差值的问题，并定义了相应的状态。最终得出了计算最大高度的解法。 ... [详细]
  • 数组

    二叉树层序创建问题的解决方法

    本文介绍了解决二叉树层序创建问题的方法。通过使用队列结构体和二叉树结构体，实现了入队和出队操作，并提供了判断队列是否为空的函数。详细介绍了解决该问题的步骤和流程。 ... [详细]
  • 数组

    UVALive6575 Odd and Even Zeroes 数位dp+找规律

    本文介绍了UVALive6575题目Odd and Even Zeroes的解法，使用了数位dp和找规律的方法。阶乘的定义和性质被介绍，并给出了一些例子。其中，部分阶乘的尾零个数为奇数，部分为偶数。 ... [详细]
  • go

    CF：3D City Model（小思维）问题解析和代码实现

    CF：3D City Model（小思维）问题解析和代码实现
    本文通过解析CF：3D City Model问题，介绍了问题的背景和要求，并给出了相应的代码实现。该问题涉及到在一个矩形的网格上建造城市的情景，每个网格单元可以作为建筑的基础，建筑由多个立方体叠加而成。文章详细讲解了问题的解决思路，并给出了相应的代码实现供读者参考。 ... [详细]
  • get

    Linux环境变量函数getenv、putenv、setenv和unsetenv详解

    Linux环境变量函数getenv、putenv、setenv和unsetenv详解
    本文详细解释了Linux中的环境变量函数getenv、putenv、setenv和unsetenv的用法和功能。通过使用这些函数，可以获取、设置和删除环境变量的值。同时给出了相应的函数原型、参数说明和返回值。通过示例代码演示了如何使用getenv函数获取环境变量的值，并打印出来。 ... [详细]
  • get

    Java学习笔记之面向对象编程（OOP）

    Java学习笔记之面向对象编程（OOP）
    本文介绍了Java学习笔记中的面向对象编程（OOP）内容，包括OOP的三大特性（封装、继承、多态）和五大原则（单一职责原则、开放封闭原则、里式替换原则、依赖倒置原则）。通过学习OOP，可以提高代码复用性、拓展性和安全性。 ... [详细]
  • get

    在类中定义数组时出错 - Error on defining arrays in class

    Iamtryingtomakeaclassthatwillreadatextfileofnamesintoanarray,thenreturnthatarra ... [详细]
author-avatar
小白一枚
这个家伙很懒，什么也没留下！
Tags | 热门标签
RankList | 热门文章
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有