Tricks Device (hdu 5294 最短路+最大流)

Tricks Device (hdu 5294 最短路+最大流)

大家好,又见面了,我是全栈君。

Tricks Device

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 124    Accepted Submission(s): 27

Problem Description
Innocent Wu follows Dumb Zhang into a ancient tomb. Innocent Wu’s at the entrance of the tomb while Dumb Zhang’s at the end of it. The tomb is made up of many chambers, the total number is N. And there are M channels connecting the chambers. Innocent Wu wants to catch up Dumb Zhang to find out the answers of some questions, however, it’s Dumb Zhang’s intention to keep Innocent Wu in the dark, to do which he has to stop Innocent Wu from getting him. Only via the original shortest ways from the entrance to the end of the tomb costs the minimum time, and that’s the only chance Innocent Wu can catch Dumb Zhang.

Unfortunately, Dumb Zhang masters the art of becoming invisible(奇门遁甲) and tricks devices of this tomb, he can cut off the connections between chambers by using them. Dumb Zhang wanders how many channels at least he has to cut to stop Innocent Wu. And Innocent Wu wants to know after how many channels at most Dumb Zhang cut off Innocent Wu still has the chance to catch Dumb Zhang.

 

Input
There are multiple test cases. Please process till EOF.

For each case,the first line must includes two integers, N(<=2000), M(<=60000). N is the total number of the chambers, M is the total number of the channels.

In the following M lines, every line must includes three numbers, and use ai、bi、li as channel i connecting chamber ai and bi(1<=ai,bi<=n), it costs li(0<li<=100) minute to pass channel i.

The entrance of the tomb is at the chamber one, the end of tomb is at the chamber N.

 

Output
Output two numbers to stand for the answers of Dumb Zhang and Innocent Wu’s questions.
 

Sample Input
   
   
8 9 1 2 2 2 3 2 2 4 1 3 5 3 4 5 4 5 8 1 1 6 2 6 7 5 7 8 1

 

Sample Output
   
   
2 6

 

Source

Recommend

题意:n个点m条无向边,如果从起点0到终点n-1的最短路距离为dist,求最少删除多少条边使得图中不再存在最短路。最多删除多少条边使得图中仍然存在最短路。

思路:先用spfa求一次最短路,开一个road数组,road[i]表示从起点走到i点最短路径所经过的最少边数,然后第二问就是m-road[n-1];再依据最短路的dist数组推断哪些边是最短路上的,用它们又一次构图。跑一遍网络流求最小割。比赛的时候没有在最短路上建边,直接用的原图。果断TLE,又坑了队友=-=

代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <string>
#include <map>
#include <stack>
#include <vector>
#include <set>
#include <queue>
#pragma comment (linker,"/STACK:102400000,102400000")
#define pi acos(-1.0)
#define eps 1e-6
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
#define FRE(i,a,b)  for(i = a; i <= b; i++)
#define FREE(i,a,b) for(i = a; i >= b; i--)
#define FRL(i,a,b)  for(i = a; i < b; i++)
#define FRLL(i,a,b) for(i = a; i > b; i--)
#define mem(t, v)   memset ((t) , v, sizeof(t))
#define sf(n)       scanf("%d", &n)
#define sff(a,b)    scanf("%d %d", &a, &b)
#define sfff(a,b,c) scanf("%d %d %d", &a, &b, &c)
#define pf          printf
#define DBG         pf("Hi\n")
typedef long long ll;
using namespace std;

#define INF 0x3f3f3f3f
#define mod 1000000009
const int MAXN = 2005;
const int MAXM = 200005;
const int N = 1005;

int n,m;

struct EDGE
{
    int u,v,len,next;
}e[MAXM];

struct Edge
{
    int to,next,cap,flow;
}edge[MAXM];

int tol;
int head[MAXN];

void init()
{
    tol=0;
    memset(head,-1,sizeof(head));
}

void add(int u,int v,int len)
{
    e[tol].u=u;
    e[tol].v=v;
    e[tol].len=len;
    e[tol].next=head[u];
    head[u]=tol++;
    e[tol].u=v;
    e[tol].v=u;
    e[tol].len=len;
    e[tol].next=head[v];
    head[v]=tol++;
}

void addedge(int u,int v,int w,int rw=0)
{
    edge[tol].to=v;
    edge[tol].cap=w;
    edge[tol].flow=0;
    edge[tol].next=head[u];
    head[u]=tol++;

    edge[tol].to=u;
    edge[tol].cap=rw;
    edge[tol].flow=0;
    edge[tol].next=head[v];
    head[v]=tol++;
}

int Q[MAXN];
int dep[MAXN],cur[MAXN],sta[MAXN];

bool bfs(int s,int t,int n)
{
    int front=0,tail=0;
    memset(dep,-1,sizeof(dep[0])*(n+1));
    dep[s]=0;
    Q[tail++]=s;
    while (front<tail)
    {
        int u=Q[front++];
        for (int i=head[u];i!=-1;i=edge[i].next)
        {
            int v=edge[i].to;
            if (edge[i].cap>edge[i].flow && dep[v]==-1)
            {
                dep[v]=dep[u]+1;
                if (v==t) return true;
                Q[tail++]=v;
            }
        }
    }
    return false;
}

int dinic(int s,int t,int n)
{
    int maxflow=0;
    while (bfs(s,t,n))
    {
        for (int i=0;i<n;i++) cur[i]=head[i];
        int u=s,tail=0;
        while (cur[s]!=-1)
        {
            if (u==t)
            {
                int tp=INF;
                for (int i=tail-1;i>=0;i--)
                    tp=min(tp,edge[sta[i]].cap-edge[sta[i]].flow);
                maxflow+=tp;
                for (int i=tail-1;i>=0;i--)
                {
                    edge[sta[i]].flow+=tp;
                    edge[sta[i]^1].flow-=tp;
                    if (edge[sta[i]].cap-edge[sta[i]].flow==0)
                        tail=i;
                }
                u=edge[sta[tail]^1].to;
            }
            else if (cur[u]!=-1 && edge[cur[u]].cap > edge[cur[u]].flow &&dep[u]+1==dep[edge[cur[u]].to])
            {
                sta[tail++]=cur[u];
                u=edge[cur[u]].to;
            }
            else
            {
                while (u!=s && cur[u]==-1)
                    u=edge[sta[--tail]^1].to;
                cur[u]=edge[cur[u]].next;
            }
        }
    }
    return maxflow;
}

int dist[MAXN];
int vis[MAXN];
int road[MAXN];

void SPFA()
{
    memset(vis,0,sizeof(vis));
    memset(dist,INF,sizeof(dist));
    memset(road,INF,sizeof(road));
    dist[0]=0;
    road[0]=0;
    vis[0]=1;
    queue<int>Q;
    Q.push(0);
    while (!Q.empty())
    {
        int u=Q.front();
        Q.pop();
        vis[u]=0;
        for (int i=head[u];~i;i=e[i].next)
        {
            int v=e[i].v;
            if (dist[v]>dist[u]+e[i].len)
            {
                dist[v]=dist[u]+e[i].len;
                road[v]=road[u]+1;
                if (!vis[v])
                {
                    vis[v]=1;
                    Q.push(v);
                }
            }
            else if (dist[v]==dist[u]+e[i].len)
            {
                if (road[v]>road[u]+1)
                {
                    road[v]=road[u]+1;
                    if (!vis[v])
                    {
                        vis[v]=1;
                        Q.push(v);
                    }
                }
            }
        }
    }
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("C:/Users/lyf/Desktop/IN.txt","r",stdin);
#endif
    int i,j,u,v,w;
    while (~sff(n,m))
    {
        init();
        for (i=0;i<m;i++)
        {
            sfff(u,v,w);
            if (u==v) continue;
            u--;v--;
            add(u,v,w);
        }
        SPFA();
        int cnt=tol;
        init();
        for (i=0;i<cnt;i++)
        {
            u=e[i].u;
            v=e[i].v;
            if (dist[v]==dist[u]+e[i].len)
                addedge(u,v,1);
        }
        int ans=dinic(0,n-1,n);
        pf("%d %d\n",ans,m-road[n-1]);
    }
    return 0;
}

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/115451.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • DayDayUp:2020,再见了,不平凡的一年,让我懂得了珍惜,让我明白了越努力越幸运[通俗易懂]

    DayDayUp:2020,再见了,不平凡的一年,让我懂得了珍惜,让我明白了越努力越幸运[通俗易懂]DayDayUp:2020,再见了,不平凡的一年,让我懂得了珍惜,让我明白了越努力越幸运导读:2020年的开篇,开的太意外,无论以什么样的眼光去回顾2020,它一定是载入史册的一年。突然起来的疫情,打得人们措手不及!人生的确不易,每个人都在负重前行,致敬那些可爱的人,感谢钟院士,感谢医护人员,感谢我们这这个强大的国家。2020年,太特殊,特殊的就像一场梦,无数的关键词涌入了记忆的心头:新冠,武汉,没毕业照,科比……前几天看到这样的一段话:2020年,最大的收获是一身伤,一身债,半条命、还活.

  • python系列文章(基础,应用,后端,运维,自动化测试,爬虫,数据分析,可视化,机器学习,深度学习系列内容)

    python基础教程python基础系列教程——Python的安装与测试:python解释器、PyDev编辑器、pycharm编译器python基础系列教程——Python库的安装与卸载python基础系列教程——Python3.x标准模块库目录python基础系列教程——Python中的编码问题,中文乱码问题python基础系列教程——python基础语法全解python…

  • IDEA汉化教程(一分钟即可)「建议收藏」

    IDEA汉化教程(一分钟即可)「建议收藏」Idea汉化教程(简单,一分钟即可)步骤打开idea点击左上角的File,然后点击Settings(如下图)进去后点击Plugins,然后点击Marketplace,然后再搜索框搜索chinese然后搜索出东西,点击下面标注的,点击安装然后下载好后再点击右侧的安装(由于我已经安装了,所以才有中文跟显示以安装)。安装完后重启就可以看到idea被汉化了…

  • Js的长轮询[通俗易懂]

    Js的长轮询[通俗易懂]长轮询是与服务器保持持久连接的最简单的方式,它不使用任何特定的协议,例如WebSocket或者ServerSentEvent。它很容易实现,在很多场景下也很好用。

    2022年10月15日
  • sftp端口改了ssh受影响吗_sftp端口号怎么查

    sftp端口改了ssh受影响吗_sftp端口号怎么查1.修改两个配置文件,添加一行vi/etc/ssh/ssh_configport端口号vi/etc/ssh/sshd_configport端口号2.重启sshd服务systemctlrestartsshd

  • linux文件属性644到755,linux系统文件夹数字权限设置详解644、755、777

    linux文件属性644到755,linux系统文件夹数字权限设置详解644、755、777linux系统文件夹数字权限设置详解644、755、777,左至右,第一位数字代表文件所有者的权限,第二位数字代表同组用户的权限,第三位数字代表其他用户的权限。而具体的权限是由数字来表示的,读取的权限等于4,用r表示;写入的权限等于2,用w表示;执行的权限等于1,用x表示;通过4、2、1的组合,得到以下几种权限:0(没有权限);4(读取权限);5(4+1|读取+执行);6(4+2|读取+…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号