乌鲁木齐网络赛J题(最小费用最大流模板)

2023-12-15 15:48

本文主要是介绍乌鲁木齐网络赛J题(最小费用最大流模板),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

ACM ICPC 乌鲁木齐网络赛 J. Our Journey of Dalian Ends

  243人阅读  评论(0)  收藏  举报
  分类:
Life is a journey, and the road we travel has twists and turns, which sometimes lead us to unexpected places and unexpected people.


Now our journey of Dalian ends. To be carefully considered are the following questions.


Next month in Xian, an essential lesson which we must be present had been scheduled.


But before the lesson, we need to attend a wedding in Shanghai.


We are not willing to pass through a city twice.


All available expressways between cities are known.


What we require is the shortest path, from Dalian to Xian, passing through Shanghai.


Here we go.


Input Format


There are several test cases.


The first line of input contains an integer tt which is the total number of test cases.


For each test case, the first line contains an integer m~(m\le 10000)m (m≤10000) which is the number of known expressways.


Each of the following mm lines describes an expressway which contains two string indicating the names of two cities and an integer indicating the length of the expressway.


The expressway connects two given cities and it is bidirectional.


Output Format


For eact test case, output the shortest path from Dalian to Xian, passing through Shanghai, or output -1−1 if it does not exist.


样例输入


3
2
Dalian Shanghai 3
Shanghai Xian 4
5
Dalian Shanghai 7
Shanghai Nanjing 1
Dalian Nanjing 3
Nanjing Xian 5
Shanghai Xian 8
3
Dalian Nanjing 6
Shanghai Nanjing 7
Nanjing Xian 8
样例输出


7
12

-1


每个城市拆成出点和入点,源点连西安和大连,汇点连上海,相当于求从西安到上海和从大连到上海最小距离之和,每个城市入点和出点之间连一条容量为1的边,但是注意,上海的容量必须是2,再根据给出的边,分别连接出点入点,存入相应花费,那么问题就可以转化成最小费用最大流了,如果流量不为2输出-1,否则输出最小花费。


[cpp]  view plain copy
  1. #include<stdio.h>  
  2. #include<algorithm>  
  3. #include<string.h>  
  4. #include<map>  
  5. #include<queue>  
  6. #include<string>  
  7. using namespace std;  
  8. #define ll long long  
  9. const ll maxm = 10005;  
  10. const ll INF = 1e18 + 7;  
  11. struct node  
  12. {  
  13.     ll u, v, flow, cost, next;  
  14. }edge[maxm * 10];  
  15. map<string, ll>p;  
  16. ll cnt, s, t, n, m, sum, FLOW;  
  17. ll head[maxm * 10], dis[maxm * 10], pre[maxm * 10];  
  18. char a[maxm], b[maxm];  
  19. void init()  
  20. {  
  21.     p.clear();  
  22.     cnt = 0, s = 0, t = n * 5 + 1, sum = 0, FLOW = 0;  
  23.     memset(head, -1, sizeof(head));  
  24. }  
  25. void add(ll u, ll v, ll flow, ll cost)  
  26. {  
  27.     edge[cnt].u = u, edge[cnt].v = v;  
  28.     edge[cnt].flow = flow, edge[cnt].cost = cost;  
  29.     edge[cnt].next = head[u], head[u] = cnt++;  
  30.     edge[cnt].u = v, edge[cnt].v = u;  
  31.     edge[cnt].flow = 0, edge[cnt].cost = -cost;  
  32.     edge[cnt].next = head[v], head[v] = cnt++;  
  33. }  
  34. ll bfs()  
  35. {  
  36.     queue<ll>q;  
  37.     for (ll i = 0;i <= t;i++) dis[i] = INF;  
  38.     memset(pre, -1, sizeof(pre));  
  39.     dis[s] = 0, q.push(s);  
  40.     ll rev = 0;  
  41.     while (!q.empty())  
  42.     {  
  43.         ll u = q.front();q.pop();  
  44.         for (ll i = head[u];i != -1;i = edge[i].next)  
  45.         {  
  46.             ll v = edge[i].v;  
  47.             if (dis[v] > dis[u] + edge[i].cost&&edge[i].flow)  
  48.             {  
  49.                 dis[v] = dis[u] + edge[i].cost;  
  50.                 pre[v] = i, q.push(v);  
  51.             }  
  52.         }  
  53.     }  
  54.     if (dis[t] == INF) return 0;  
  55.     return 1;  
  56. }  
  57. ll MCMF()  
  58. {  
  59.     ll ans = 0, minflow;  
  60.     while (bfs())  
  61.     {  
  62.         minflow = INF;  
  63.         for (ll i = pre[t];i != -1;i = pre[edge[i].u])  
  64.             minflow = min(minflow, edge[i].flow);  
  65.         for (ll i = pre[t];i != -1;i = pre[edge[i].u])  
  66.             edge[i].flow -= minflow, edge[i ^ 1].flow += minflow;  
  67.         ans += dis[t] * minflow;  
  68.         FLOW += minflow;  
  69.     }  
  70.     return ans;  
  71. }  
  72. int main()  
  73. {  
  74.     ll i, j, k, T, c;  
  75.     scanf("%lld", &T);  
  76.     while (T--)  
  77.     {  
  78.         scanf("%lld", &n);  
  79.         init();  
  80.         ll nn = n * 2;  
  81.         for (i = 1;i <= n;i++)  
  82.         {  
  83.             scanf("%s%s%lld", a, b, &c);  
  84.             if (p[a] == 0)  
  85.             {  
  86.                 p[a] = ++sum, k = 1;  
  87.                 if (strcmp(a, "Shanghai") == 0) k = 2;  
  88.                 add(p[a], p[a] + nn, k, 0);  
  89.             }  
  90.             if (p[b] == 0)  
  91.             {  
  92.                 p[b] = ++sum, k = 1;  
  93.                 if (strcmp(b, "Shanghai") == 0) k = 2;  
  94.                 add(p[b], p[b] + nn, k, 0);  
  95.             }  
  96.             ll u = p[a], v = p[b];  
  97.             add(u + nn, v, INF, c);  
  98.             add(v + nn, u, INF, c);  
  99.         }  
  100.         ll u = p["Dalian"];  
  101.         add(s, u, 1, 0);  
  102.         u = p["Xian"];  
  103.         add(s, u, 1, 0);  
  104.         u = p["Shanghai"];  
  105.         add(u + nn, t, 2, 0);  
  106.         ll ans = MCMF();  
  107.         if (FLOW == 2) printf("%lld\n", ans);  
  108.         else printf("-1\n");  
  109.     }  
  110.     return 0;  
  111. }  

这篇关于乌鲁木齐网络赛J题(最小费用最大流模板)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/496991

相关文章

Linux系统配置NAT网络模式的详细步骤(附图文)

《Linux系统配置NAT网络模式的详细步骤(附图文)》本文详细指导如何在VMware环境下配置NAT网络模式,包括设置主机和虚拟机的IP地址、网关,以及针对Linux和Windows系统的具体步骤,... 目录一、配置NAT网络模式二、设置虚拟机交换机网关2.1 打开虚拟机2.2 管理员授权2.3 设置子

揭秘Python Socket网络编程的7种硬核用法

《揭秘PythonSocket网络编程的7种硬核用法》Socket不仅能做聊天室,还能干一大堆硬核操作,这篇文章就带大家看看Python网络编程的7种超实用玩法,感兴趣的小伙伴可以跟随小编一起... 目录1.端口扫描器:探测开放端口2.简易 HTTP 服务器:10 秒搭个网页3.局域网游戏:多人联机对战4.

SpringBoot使用OkHttp完成高效网络请求详解

《SpringBoot使用OkHttp完成高效网络请求详解》OkHttp是一个高效的HTTP客户端,支持同步和异步请求,且具备自动处理cookie、缓存和连接池等高级功能,下面我们来看看SpringB... 目录一、OkHttp 简介二、在 Spring Boot 中集成 OkHttp三、封装 OkHttp

Linux系统之主机网络配置方式

《Linux系统之主机网络配置方式》:本文主要介绍Linux系统之主机网络配置方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、查看主机的网络参数1、查看主机名2、查看IP地址3、查看网关4、查看DNS二、配置网卡1、修改网卡配置文件2、nmcli工具【通用

使用Python高效获取网络数据的操作指南

《使用Python高效获取网络数据的操作指南》网络爬虫是一种自动化程序,用于访问和提取网站上的数据,Python是进行网络爬虫开发的理想语言,拥有丰富的库和工具,使得编写和维护爬虫变得简单高效,本文将... 目录网络爬虫的基本概念常用库介绍安装库Requests和BeautifulSoup爬虫开发发送请求解

C++中函数模板与类模板的简单使用及区别介绍

《C++中函数模板与类模板的简单使用及区别介绍》这篇文章介绍了C++中的模板机制,包括函数模板和类模板的概念、语法和实际应用,函数模板通过类型参数实现泛型操作,而类模板允许创建可处理多种数据类型的类,... 目录一、函数模板定义语法真实示例二、类模板三、关键区别四、注意事项 ‌在C++中,模板是实现泛型编程

如何通过海康威视设备网络SDK进行Java二次开发摄像头车牌识别详解

《如何通过海康威视设备网络SDK进行Java二次开发摄像头车牌识别详解》:本文主要介绍如何通过海康威视设备网络SDK进行Java二次开发摄像头车牌识别的相关资料,描述了如何使用海康威视设备网络SD... 目录前言开发流程问题和解决方案dll库加载不到的问题老旧版本sdk不兼容的问题关键实现流程总结前言作为

基于Java实现模板填充Word

《基于Java实现模板填充Word》这篇文章主要为大家详细介绍了如何用Java实现按产品经理提供的Word模板填充数据,并以word或pdf形式导出,有需要的小伙伴可以参考一下... Java实现按模板填充wor编程d本文讲解的需求是:我们需要把数据库中的某些数据按照 产品经理提供的 word模板,把数据

SSID究竟是什么? WiFi网络名称及工作方式解析

《SSID究竟是什么?WiFi网络名称及工作方式解析》SID可以看作是无线网络的名称,类似于有线网络中的网络名称或者路由器的名称,在无线网络中,设备通过SSID来识别和连接到特定的无线网络... 当提到 Wi-Fi 网络时,就避不开「SSID」这个术语。简单来说,SSID 就是 Wi-Fi 网络的名称。比如

Java实现任务管理器性能网络监控数据的方法详解

《Java实现任务管理器性能网络监控数据的方法详解》在现代操作系统中,任务管理器是一个非常重要的工具,用于监控和管理计算机的运行状态,包括CPU使用率、内存占用等,对于开发者和系统管理员来说,了解这些... 目录引言一、背景知识二、准备工作1. Maven依赖2. Gradle依赖三、代码实现四、代码详解五