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

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;
}
查看代码

推荐阅读
author-avatar
mobiledu2502909493
这个家伙很懒，什么也没留下！
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社区 版权所有