ZOJ2760-最大流问题

作者：mobiledu2502909493 | 来源：互联网 | 2024-11-26 01:33

题目链接：HowManyShortestPaths。题目描述：给定一个包含n个节点的有向图，通过一个n*n的矩阵来表示。矩阵中的a[i][j]值为-1表示从节点i到节点j无直接路径；否则，该值表示从i到j的路径长度。输入起点vs和终点vt，计算从vs到vt的所有不共享任何边的最短路径数量。如果起点和终点相同，则输出无穷大。

题目链接：How Many Shortest Paths

题目描述：给定一个包含n个节点的有向图，通过一个n*n的矩阵来表示。矩阵中的a[i][j]值为-1表示从节点i到节点j无直接路径；否则，该值表示从i到j的路径长度。输入起点vs和终点vt，计算从vs到vt的所有不共享任何边的最短路径数量。如果起点和终点相同，则输出无穷大。

解题思路：首先使用Floyd算法计算任意两点之间的最短路径距离。然后构建一个新的图，其中只有满足条件的边（即dis[vs][i] + a[i][j] + dis[j][vt] == dis[vs][vt]）才会被加入新图中，边的权重设为1以确保每条边仅能被使用一次。最后利用Dinic算法计算最大流，从而得到从vs到vt的不共享边的最短路径数量。

#pragma comment(linker, "/STACK:1024000000,1024000000")#include <>
#include <>
#include <>
#include <>
#include <>
#include <>
#include <>
#include <>
#include <>
#include <>
#include <>
#include <>
#include <>
#define LL long long
#define mod 100000000
#define inf 0x3f3f3f3f
#define eps 1e-6
#define N 300
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define PII pair
using namespace std;
inline int read()
{
    char ch=getchar();
    int x=0,f=1;
    while (ch>'9' || ch<'0') {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch<='9' && ch>='0') {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}
int n,cnt,vs,vt,tot;
int dis[N][N],a[N][N];
int head[N],q[N],cur[N],d[N];
struct edge
{
    int v,w,next;
    edge() {}
    edge(int v, int w, int next) : v(v), w(w), next(next) {}
} e[N*N];
void addedge(int u, int v, int w)
{
    e[tot]=edge(v,w,head[u]);
    head[u]=tot++;
}
void init()
{
    memset(dis, 0x3f, sizeof(dis));
    memset(head, -1, sizeof(head));
    tot=0;
}
int bfs()
{
    int hd=0, tail=1;
    memset(d, -1, sizeof(d));
    q[0]=vs;
    d[vs]=0;
    while (hd!=tail) {
        int u=q[hd++];
        for (int i=head[u]; ~i; i=e[i].next) {
            int v=e[i].v, w=e[i].w;
            if (w && d[v]==-1) {
                d[v]=d[u]+1;
                q[tail++]=v;
            }
        }
    }
    return d[vt]!=-1;
}
int dfs(int u, int flow)
{
    if (u==vt) return flow;
    int used=0;
    for (int i=cur[u]; ~i; i=e[i].next) {
        int v=e[i].v, w=e[i].w;
        if (d[v]==d[u]+1) {
            w=dfs(v, min(flow-used, w));
            e[i].w-=w;
            e[i^1].w+=w;
            if (e[i].w) cur[u]=i;
            used+=w;
            if (used==flow) return flow;
        }
    }
    if (!used) d[u]=-1;
    return used;
}
int dinic()
{
    int res=0;
    while (bfs()) {
        for (int i=1; i<=n; i++) cur[i]=head[i];
        res+=dfs(vs, inf);
    }
    return res;
}
void floyd()
{
    for (int k=1; k<=n; k++)
        for (int i=1; i<=n; i++)
            for (int j=1; j<=n; j++)
                dis[i][j]=min(dis[i][j], dis[i][k]+dis[k][j]);
}
void build()
{
    for (int i=1; i<=n; i++)
        for (int j=1; j<=n; j++)
            if (a[i][j]!=-1 && dis[vs][i]+dis[j][vt]+a[i][j]==dis[vs][vt])
                addedge(i, j, 1), addedge(j, i, 0);
}
int main()
{
    while (scanf("%d", &n)>0) {
        init();
        for (int i=1; i<=n; i++)
            for (int j=1; j<=n; j++) {
                a[i][j]=read();
                if (a[i][j]!=-1) dis[i][j]=a[i][j];
                if (i==j) dis[i][j]=0;
            }
        vs=read()+1;
        vt=read()+1;
        if (vs==vt) {
            puts("inf");
            continue;
        }
        floyd();
        build();
        printf("%d\n", dinic());
    }
    return 0;
}

查看代码

推荐阅读

input
扫描线三巨头 hdu1928hdu 1255 hdu 1542 [POJ 1151]

学习链接：http:blog.csdn.netlwt36articledetails48908031学习扫描线主要学习的是一种扫描的思想，后期可以求解很 ... [详细]

蜡笔小新 2024-12-26 20:04:36
int
UNP 第9章：主机名与地址转换

本章探讨了用于在主机名和数值地址之间进行转换的函数，如gethostbyname和gethostbyaddr。此外，还介绍了getservbyname和getservbyport函数，用于在服务器名和端口号之间进行转换。 ... [详细]

蜡笔小新 2024-12-27 11:26:39
int
火星商店问题：线段树分治与持久化Trie树的应用

本题涉及编号为1至n的火星商店，每个商店有一个永久商品价值v。操作包括每天在指定商店增加一个新商品，以及查询某段时间内某些商店中所有商品（含永久商品）与给定密码值的最大异或结果。通过线段树分治和持久化Trie树来高效解决此问题。 ... [详细]

蜡笔小新 2024-12-27 21:23:11
int
USACO 2014 Jan - Moolympics区间记录优化算法

题目描述：给定n个半开区间[a, b)，要求使用两个互不重叠的记录器，求最多可以记录多少个区间。解决方案采用贪心算法，通过排序和遍历实现最优解。 ... [详细]

蜡笔小新 2024-12-27 18:14:31
int
Weight the Tree（树形dp）

题目Link题目学习link1题目学习link2题目学习link3%%%受益匪浅！－－－－－&# ... [详细]

蜡笔小新 2024-12-26 15:55:56
int
深入理解KMP算法中的next数组：北大OJ 2406题解

本文详细探讨了KMP算法中next数组的构建及其应用，重点分析了未改良和改良后的next数组在字符串匹配中的作用。通过具体实例和代码实现，帮助读者更好地理解KMP算法的核心原理。 ... [详细]

蜡笔小新 2024-12-28 11:30:01
int
使用Objective-C和dispatch库实现并发素数计算

本文介绍如何使用Objective-C结合dispatch库进行并发编程，以提高素数计数任务的效率。通过对比纯C代码与引入并发机制后的代码，展示dispatch库的强大功能。 ... [详细]

蜡笔小新 2024-12-28 08:44:35
int
MyBatis 动态 SQL 详解与应用

本文深入探讨 MyBatis 中动态 SQL 的使用方法，包括 if/where、trim 自定义字符串截取规则、choose 分支选择、封装查询和修改条件的 where/set 标签、批量处理的 foreach 标签以及内置参数和 bind 的用法。 ... [详细]

蜡笔小新 2024-12-27 16:20:10
int
C++: 实现基于类的四面体体积计算

本文介绍如何使用C++编程语言，通过定义类和方法来计算由四个三维坐标点构成的四面体体积。文中详细解释了四面体体积的数学公式，并提供了两种不同的实现方式。 ... [详细]

蜡笔小新 2024-12-27 14:31:39
int
组合数学问题：棋盘上的组合数计算

本文探讨了如何在模运算下高效计算组合数C(n, m)，并详细介绍了乘法逆元的应用。通过扩展欧几里得算法求解乘法逆元，从而实现除法取余的计算。 ... [详细]

蜡笔小新 2024-12-26 21:41:44
int
寻找满足特定条件的整数N的最大和(a+b)

本文探讨了如何在给定整数N的情况下，找到两个不同的整数a和b，使得它们的和最大，并且满足特定的数学条件。 ... [详细]

蜡笔小新 2024-12-26 19:26:18
int
Splay Tree 区间操作优化

本文详细介绍了使用Splay Tree进行区间操作的实现方法，包括插入、删除、修改、翻转和求和等操作。通过这些操作，可以高效地处理动态序列问题，并且代码实现具有一定的挑战性，有助于编程能力的提升。 ... [详细]

蜡笔小新 2024-12-26 18:47:12
int
长春大学软件工程：二叉排序树实验报告

本实验主要探讨了二叉排序树（BST）的基本操作，包括创建、查找和删除节点。通过具体实例和代码实现，详细介绍了如何使用递归和非递归方法进行关键字查找，并展示了删除特定节点后的树结构变化。 ... [详细]

蜡笔小新 2024-12-26 15:32:56
int
使用 NSTimer 实现倒计时功能

本文介绍如何使用 NSTimer 实现倒计时功能，详细讲解了初始化方法、参数配置以及具体实现步骤。通过示例代码展示如何创建和管理定时器，确保在指定时间间隔内执行特定任务。 ... [详细]

蜡笔小新 2024-12-26 19:08:19
input
Python学习笔记：使用pydoc工具查询文档

本文介绍了在Windows环境下使用pydoc工具的方法，并详细解释了如何通过命令行和浏览器查看Python内置函数的文档。此外，还提供了关于raw_input和open函数的具体用法和功能说明。 ... [详细]

蜡笔小新 2024-12-26 17:05:56

mobiledu2502909493

这个家伙很懒，什么也没留下！

Tags | 热门标签

RankList | 热门文章